4 Queue队列
前面几篇，我们介绍了Java集合中常用到的对象。本篇中，我们再来说说Queue队列的故事。
对于Queue，或许你跟我一样，并不会将其与集合框架联系到一起，更多时候是将其归属到数据结构中。
尤其是查找集合相关的教程时，大多都是List、Set、Map，讲解Queue队列的很少出现。
但，当你真正去了解、看源码时，会发现Queue是Collection的一个子接口，与List、Set同一级别；
题外话说多了，到底什么是Queue，让我们来看！
1. Queue
Queue是Java集合框架中的一员，继承于Collection接口。
与List、Set相同的是，Queue也实现了一种数据结构，这就是队列（这也是Queue经常出现在数据结构相关文章中的主要原因）。
所以，要想明白Queue集合，首先得知道队列是什么！
队列是计算机中的一种数据结构，保存在其中的数据具有“先进先出（FIFO,First In First Out）”的特性。
如果，你不明白“先进先出”是什么，试想下排队的场景，最先进来的人解决完问题后，最早离开---这就叫“先进先出”；
当队伍中有新来的人时，需要排在队伍的末端；而当队伍中有人解决完问题时，会从队伍的前端离开。
在队列中，我们管队伍的末端叫做“队尾”，管队伍的前端叫“队头”；新来的人，称之为“入队”。而离开的人，称之为“出队”；
稍有不同的是，在数据结构中，队列不支持从队伍的中间插入和离开，只能从头尾进行。而真实生活中，我们的队伍可没有这么和谐！！！！
还有一点是，当没有人在排队时，我们称之为“空队”，也就是队列为空的情况。
通过介绍排队的场景，让我们对队列有了一个初步的概念。那么，在Java中的队列究竟如何实现呢？
1.1 队列的两种形式
在Java中，队列分为2种形式，一种是单队列，一种是循环队列；
通常，都是使用数组来实现队列，假定数组的长度为6，也就是队列的长度为6；
- 来看单队列情况：
第一步，创建一个空数组，有两个变量，分别为front、rear，代表着头指针、尾指针；
第二步，向队列中插入数据；
第三步，移除队头中的数据；
第四步，再次向队列中插数据（此时rear指针指向了一个不存在的角标）；
此时，单队列发生了“假溢出”情况，尾指针指向了一个不存在的数组角标。
如果，要解决该情况的发生，有两种方式-----一，无限扩充数组大小；二，引入循环队列；
- 来看循环队列情况：
当尾指针超过了数组角标大小，此时我们会判断队列的头部是否有剩余的空间，如果有就把尾指针指向队列的头部；
此时，循环队列就产生了。
其实，循环队列就是将单队列的首位进行相连，形成了一个圆圈，这样就不会发生角标越界的情况了（distruptor实现）；
网友评论