Java数据结构之Deque
引题
进入本文之前，我们先看一段代码
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直接设置为8
elements = 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;
//再计算tail
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
//扩容
doubleCapacity();
}
从这里我们很明显可以看出，两个方法的区别在于：
addFirst是
先计算出head的位置
，然后
存放元素
，head指向的地方是
存储了元素的
。
而addLast是
先存储元素
，再计算
tail的值
，tail指向的地方为
null
。
简单思考2
如果将
addLast
方法的执行顺序改为：
先计算tail值，再存储元素
。按照
简单思考 1
，请问插入第几个元素时扩容？并且
扩容时
数组内部
是否有元素为null
？答案可以评论区留言哦。
线程并不安全
我们可以看到，ArrayDeque中的方法都没有加
synchronized
的关键字，故而其是
线程不安全
的。