队列
聊起队列，你一定会联想到一个与队列相似的数据结构:栈。
为了更好的理解什么是队列，我们将它和栈来比较一下：
队列的特点是：先进先出，如下图，1先进，1就先出。
图1：队列的图解
栈的特点是：先进后出，如下图，1先进，1却最后出。
图2：栈的图解
为了让你更好的区分与理解队列与栈，你只记住这个口诀：吃多了拉就是队列，吃多了吐就是栈。
哈哈哈，千万不要告诉别人这是我告诉你的....
数组实现队列，难在哪？
数组实现队列，乍一看，很贴合的一种方式去实现队列。仔细推敲一下你会发现并不简单。
为了更看清数组存在什么问题，我先new一个size为4的数组：
图3：大小为4的数组
下一步，向数组中入列4个元素，数组按照0、1、2、3的下标被填充：
图4：队列写满
继续，消费两个元素，我们按照先进先出的原则，消费掉下标为0、1的元素，如图：
图5：从队列消费2个元素
如果继续入列，你会发现：最大的下标3已经被占用，而数组依然存在空间。无法入列，造成空间浪费！
数组队列如何解决困难？
思维活跃的程序员，不可能因为遇到困难而畏惧！更不可能存在空间，而无法使用。就像饥肠辘辘，食物摆在眼前，却不知道如何吃掉它！
方案一：扩
了解过ArrayList、HashMap的朋友肯定知道空间不够，那就扩。当发现空间不够用，我们是否可以将空间扩成原来的2倍？,像下图这样：
图6：数组扩容
是办法，但是不是最好的办法。因为下标为0和1的空间，无法利用和回收，造成浪费！，不妥！也不可取！有人说无所谓，钱不是问题，金主直接return~
方案二：移
既然存在空间无法利用，那发现数组空间满了之后，是否可以将元素进行挪动呢？如图：
图7：数组元素移动
是办法，是比方案一更好的办法，但依然不是最好的办法。那这又为什么呢？想想，两个数据的挪动，貌似没有什么成本，但是如果是1万甚至更多元素挪动，会带来什么呢？对！更高的时间复杂度，即o(n)。
除了扩和移，真的没有其他的办法？有的，今天给大家介绍一个新玩法：循环队列。
循环数组队列
说起循环，大家肯定脑海中呈现出头尾相连的一个环，就是循环。是的！循环数组队列就是这样的结构，将你认知的连续的长长的数组，抽象成一个环,就是下图：
图8：循环数组队列
在图5数组队列的基础上，继续入列一个元素，如下图：
图9：循环数组队列追加元素
入列后的数组，你试着把它想象成一个环状，如果再继续入列元素，会放到下标为1的位置。
因此循环数组队列很好地解决了之前两种方案的缺点：
1.空间浪费无法充分利用
2.数据迁移导致的o(n)的时间复杂度
如何实现循环数组队列
属性定义&说明
实现循环数组队列，需要定义几个关键的属性，以帮助我们更好地代码实现:
-
capicity
队列的容量大小 -
items
定义的数组，容纳元素 -
head
出列的头部数组下标，指向下次出列的位置 -
tail
入列的尾部数组下标，指向下次入列的位置 -
size
队列入列的元素个数
代码实现
<pre class="custom" data-tool="mdnice编辑器" style="margin-top: 10px; margin-bottom: 10px; border-radius: 5px; box-shadow: rgba(0, 0, 0, 0.55) 0px 2px 10px;">`public class LoopQueue<T> {
// 容量
private int capicity;
// 队列元素
private Object[] items;
// 头部位置
private int head = 0;
// 尾部位置
private int tail = 0;
// 大小
private int size = 0;
public LoopQueue(int capicity) {
this.capicity = capicity;
this.items = new Object[capicity];
}
public boolean enqueue(T t) {
// 如果超出容量，直接返回入列失败
if (size >= capicity) {
return false;
}
// 到尾部了，但是还没有满，tail重置
if (tail == capicity) {
tail = 0;
}
// 数组tail位置放置元素，并将tail自增
this.items[tail++] = t;
// 大小累加
size++;
return true;
}
public T dequeue() {
// 队列无元素，直接返回空
if (size <= 0) {
return null;
}
// 到尾部了，但是还没有满，head重置
if (head == capicity) {
head = 0;
}
// size自减少
size--;
// 获取元素并自增head
return (T) this.items[head++];
}
public static void main(String[] args) {
LoopQueue<Integer> queue = new LoopQueue<Integer>(6);
for (int i = 0; i < 7; i++) {
System.out.println(queue.enqueue(i));
}
for (int i = 0; i < 7; i++) {
System.out.println(queue.dequeue());
}
}
}` </pre>
上述代码，已经增加了注释，你可以直接拷贝试验下。
main方法中可直接运行测试:定义容量为6的数组队列，入列7次后，出列7次，运行结果如图：
图10：循环数组运行结果
-
位置1因为空间已满，无法入列,返回false -
位置2因为队列已空，出列的元素为空
ArrayBlockingQueue解密
为了研究下数组队列在JDK中如何实现的，我特地看了下ArrayBlockingQueue的源码：
- put方法入口，当空间满了，
阻塞：
图11：put方法
- 如果空间没有满，进入第2步，
enqueue方法，实现逻辑也采用的循环数组队列：
图12：enqueue方法
写在最后
数组队列用了较长的篇幅在讨论，采用循环的思路很优雅地解决了空间利用问题。
不知道你有没有发现一个问题，JDK中的ArrayBlockingQueue的构造函数全部都需要初始化capacity:
图13：ArrayBlockingQueue构造函数
因为使用数组需要初始化空间，所以需要初始化capacity。
留一道思考题：有没有实现无限空间的队列的方法呢？
不妨打开JDK寻找下答案~
我是公众号【面试怪圈】的keaizhuzhu，关注我~
