引题

进入本文之前，我们先看一段代码

 Deque<Integer> que = new ArrayDeque<>();

上面的代码是否感觉到熟悉？前面的接口Deque有没有感觉与Queue–队列看起来有点像，都是que结尾。后面的ArrayDeque看着眼熟？是不是跟ArrayList有点像。但这个接口描述的到底是怎样的数据结构呢？我们现在就去源码里一探究竟吧。

Deque接口分析

我们按住ctrl+左键点进去看看Deque接口的源码就能明白这个类的作用是什么了？

Deque的注释

先看接口上面的注释，这里就不放英文了，我直接上一段百度翻译的原文。

支持两端元素插入和移除的线性集合。
deque是“双端队列”的缩写，通常发音为“deck”。
大多数Deque实现对它们可能包含的元素数量没有固定的限制，
但是这个接口支持容量限制的Deque以及那些没有固定大小限制的Deque。这个接口定义了访问deque容器两端元素的方法。
提供了插入、删除和检查元素的方法。
这些方法以两种形式存在:一个在操作失败时抛出异常，
另一个返回特殊值(null或false，取决于操作)。
插入操作的后一种形式是专门为使用容量受限的Deque实现而设计的;
在大多数实现中，插入操作不会失败。

抓住关键词：支持两端元素插入和移除的线性集合、双端队列、包含的元素数量没有固定的限制、访问deque容器两端元素的方法。

然后接着往下看注释：

表示该接口中的12个方法，其实从方法名称中我们就可以看出，这个数据结构可以从两端进行插入、取出、删除数据。

与Queue的联系

该接口扩展了Queue接口。
当deque被用作队列时，会产生FIFO (First-In-First-Out)行为。
在deque容器的末尾添加元素，并从开头删除元素。

也就是说Deque是Queue的子类，可以把它当作队列来使用。
但还记得上面的关键词吗？支持两端元素插入和移除的线性集合。
也就是Deque可以在两边都操作元素：新增、删除、访问元素等。
而Queque 只能在队首 对元素进行操作。

还在使用Stack？你OUT啦！

Deque也可以用作LIFO(后进先出)堆栈。
这个接口应该优先于旧的Stack类使用。
当一个队列被用作堆栈时，元素从队列的开始被推入和弹出
。堆栈方法完全等同于Deque方法。

所以以后需要使用Stack的情况时候，要记得优先使用Deque哦。

peek方法更方便

注意，当一个deque用作队列或堆栈时，peek方法同样工作良好；
在这两种情况下，元素都是从队列的开头开始绘制的。

虽然有get方法获取元素，但官方表示：peek方法，你值得拥有！

与List的不同

与List接口不同，该接口不支持对元素的索引访问。

与null说goodbye

虽然不严格要求Deque实现禁止空元素的插入，但是强烈建议这样做。
强烈建议任何允许null元素的Deque实现的用户不要利用插入null的能力。
这是因为null被各种方法用作特殊的返回值，以指示deque为空。

因为null被各种方法作为特殊的返回值，所以建议不要存储null值。

子类ArrayDeque.class分析

Deque接口的实现类很多，这里就不一一分析了，以下只分析其中的的一个子类ArrayDeque。

基本结构

官方的代码

    /*** The array in which the elements of the deque are stored.* The capacity of the deque is the length of this array, which is* always a power of two. The array is never allowed to become* full, except transiently within an addX method where it is* resized (see doubleCapacity) immediately upon becoming full,* thus avoiding head and tail wrapping around to equal each* other.  We also guarantee that all array cells not holding* deque elements are always null.*/transient Object[] elements; // non-private to simplify nested class access/*** The index of the element at the head of the deque (which is the* element that would be removed by remove() or pop()); or an* arbitrary number equal to tail if the deque is empty.*/transient int head;/*** The index at which the next element would be added to the tail* of the deque (via addLast(E), add(E), or push(E)).*/transient int tail;/*** The minimum capacity that we'll use for a newly created deque.* Must be a power of 2.*/private static final int MIN_INITIAL_CAPACITY = 8;

上述代码的注释中已经将各个属性的作用描述的很清楚了，这里就直接翻译下。

/*存储deque容器元素的数组。deque的容量是数组的长度，总是2的幂。数组永远不允许被填满，除非在一个addX方法中，数组在被填满后立即被调整大小(参见doubleCapacity)，从而避免头尾绕成相等。我们还保证所有不包含deque元素的数组单元格始终为空。
*/transient Object[] elements;//非私有以简化嵌套类访问/*deque容器头部元素的索引(即将被remove()或pop()移除的元素);或者如果deque为空，则等于tail的任意数。 -- elements的头部
*/transient int head;
/*下一个元素将被添加到deque容器尾部的索引(通过addLast(E)， add(E)，或push(E))。 -- 可以理解为elements的末端
*/transient int tail;/*我们将用于新创建deque的最小容量。一定是2的幂。 最小的初始化容量*/private static final int MIN_INITIAL_CAPACITY = 8;

值得注意的是transient 关键字是指，该数据只能在内存中使用，而无法保存到本地的文件中,这文章比较详细：Java中transient关键字的详细总结.

图解数据存储过程

从下图初始化的Deque结构中很明显可以看出为什么我们不能插入null。因为实例后各个元素的默认值就是null。从而插入null的话会造成以下情况：下次在该位置插入元素时无法确定该位置是否存在元素。

从尾部插入两个元素，注意头（head）尾（tail）指针的位置

如果从头部插入数据,注意头（head）尾（tail）指针的位置

注意head和tail指向的地方是否有数据存储

简单思考 1

如果先后从头尾分别插入一个数据，请问插入第几个数据时扩容（假设当head = tail 时扩容）？答案可以评论区留言哦。

部分代码的分析

关于初始容量

初始容量默认为8，如果小于8则设为8，大于8则取大于该数的2次幂的整数.

private void allocateElements(int numElements) {int initialCapacity = MIN_INITIAL_CAPACITY;//默认最小为8 如果大于8则取大于该数的2次幂的整数if (numElements >= initialCapacity) {initialCapacity = numElements;// |= 做一个向右移位后的或运算// >>>n 无符号右移n位 高位用0补齐// |= 就是 initialCapacity  = initialCapacity |  (initialCapacity >>>  1)initialCapacity |= (initialCapacity >>>  1);initialCapacity |= (initialCapacity >>>  2);initialCapacity |= (initialCapacity >>>  4);initialCapacity |= (initialCapacity >>>  8);initialCapacity |= (initialCapacity >>> 16);initialCapacity++;if (initialCapacity < 0) initialCapacity >>>= 1;//直接给你分配 2 ^ 30 容量的元素 一般都直接爆炸}//小于8直接设置为8elements = new Object[initialCapacity];}

关于扩容

直接扩展为双倍容量

    private void doubleCapacity() {assert head == tail;int p = head;int n = elements.length;int r = n - p;int newCapacity = n << 1;//直接移位变成两倍if (newCapacity < 0)throw new IllegalStateException("Sorry, deque too big");Object[] a = new Object[newCapacity]; //新的对象数组System.arraycopy(elements, p, a, 0, r);//写入 p - n 位置的数据到新的对象数组中(不包含第n号元素)System.arraycopy(elements, 0, a, r, p); //写入 0 - p 位置的数据到新数组中 （不包含第p号元素）elements = a;//替换对象数组的地址head = 0;tail = n;}

System.arraycopy(elements, 0, a, r, p)；
这一行代码的意思就是：从elements数组的p号位置开始，复制r个元素（包含p），到a数组中，从0开始。

代码中的&运算

以在队列首部增加元素方法addFirst为例，源码如下

public void addFirst(E e) {if (e == null)throw new NullPointerException();//先计算head 再存值elements[head = (head - 1) & (elements.length - 1)] = e;if (head == tail)//扩容doubleCapacity();
}

注意以下代码

 elements[head = (head - 1) & (elements.length - 1)] = e;//上面的代码可以看成以下两行head = (head - 1) & (elements.length - 1);elements[head] = e;

上述代码作用：将head往前移动一位，用来确定该插入元素存放的位置

head =  (head - 1) & (elements.length - 1)

上述的与(&)操作，可以理解为一个取余。
与取余不同的是当head - 1的结果为负数时，如当head = 0时，上面的赋值语句为：head = -1 & (elements.length - 1)，结果是-1。
而&运算的结果是：head = (elements.length - 1）
即&操作，使得head的取值永远在[0 ， elements.length - 1]中。
而且&操作由于是二进制操作，所以相较于取余运行速度更快，效率更高。

与之相对的addLast方法

public void addLast(E e) {if (e == null)throw new NullPointerException();//先存值 elements[tail] = e;//再计算tailif ( (tail = (tail + 1) & (elements.length - 1)) == head)//扩容doubleCapacity();
}

从这里我们很明显可以看出，两个方法的区别在于：

addFirst是先计算出head的位置，然后存放元素，head指向的地方是存储了元素的。

而addLast是先存储元素，再计算tail的值，tail指向的地方为null。

简单思考2

如果将addLast方法的执行顺序改为：先计算tail值，再存储元素。按照简单思考 1，请问插入第几个元素时扩容？并且扩容时数组内部是否有元素为null？答案可以评论区留言哦。

线程并不安全

我们可以看到，ArrayDeque中的方法都没有加synchronized的关键字，故而其是线程不安全的。