引言
队列、栈是最基础的数据结构中的两种，非常简单，但也很重要。队列的规则是：先进先出（First In First Out, FIFO）；栈的规则是：先进后出(First In Last Out, FILO)。而在其它方面几乎没有差别，所以java中就有一个类同时实现了它们的功能，即：ArrayDeque，直译一下应该可以叫基于数组的双端队列。
成员变量:
transient Object[] elements; // 数据载体，长度始终为2的幂
transient int head;//头指针
transient int tail;//尾指针
这里要注意的是：
- 这个队列不允许元素为空；
- 数组至少有一个位置是空的；
- head跟tail之间没有绝对的大小关系；
从它的设计上来看，我们可以把它看成一个循环数组，数组里存放的元素下标区间因head与tail的关系而异，具体如下：
- head < tail:
[head : tail-1] - head > tail:
[head : elements.length()-1] + [0, tail-1] - head == tail:
队列为空，也就是没有存放任何元素
两个构造方法：
public ArrayDeque() {
elements = new Object[16];
}
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
第一个很简单，就是预申请长度为16的数组；
再看第二个，numElements是指用户指定的队列长度，它调用了allocateElements(int numElements)：
private void allocateElements(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// Find the best power of two to hold elements.
// Tests "<=" because arrays aren't kept full.
if (numElements >= initialCapacity) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
}
elements = new Object[initialCapacity];
}
前面几句很好理解，如果numElements太小，那么队列长度就取默认初始化长度；
后面一坨代码的意思：如果numElements大于默认初始化长度，就取最小的n使得：n = 2^k(k为整数), 且n > numElements。
求n的方法有很多：从小到大枚举k、二分k等等；可能作者觉得这些方法都太low了，又熟练掌握二进制运算技巧，于是才有了这几行代码。
下面简单分析一下代码的运算过程，注：">>>"代表按位右移：
假设a=1xxxxxxxxxxxx...(base 2, x代表该位任意为0或1)
首先a |= (a >>> 1)之后，a => 11xxxxxxxx...(最高两位是1)
然后a |= (a>>> 2): a => 1111xxxxxxxxx...（最高四位是1）
再a |= (a>>> 4): a => 11111111xxxxxxx...（最高八位是1）
........
最终，a的所有低位也都变成了1，即11111111...111(全是1)
再a++ 就变成了10000000000...000(加一之后进位，比原来的二进制串多了一位，且第一位是1，其它位都是0)，这个算法不仅时间效率高，而且只用到了一个变量，真可谓是短小精悍，在HashMap里也可以看到这个算法的身影。
两个添加方法：
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
前面代码很简洁，刚开始做元素非空检测；加到头部时，head自减并对数组长度取余，然后将元素存在head位置；加到尾部时，将元素存放在tail，再执行tail自增并对数组长度取余。最后再检查队列空间是否已满，若已满调用doubleCapacity()将容量扩增为原先的两倍:
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // number of elements to the right of 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);
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}
这里主要做了这么几件事：
- 先做各种合法性校验；
- 申请新数组（长度扩大一倍）；
- 根据head和tail推算出元素的逻辑顺序；
- 保持元素原来顺序拷贝到新数组里；
- 重置头尾指针。
这里稍微解释一下代码里的取余逻辑：
记mod = elements.length = 2^k, a为[-1,mod]之间的一个整数，那么有：
- a == -1:
a & (mod-1) == mod - 1; - 0 <= a < mod:
a & (mod - 1) == a; - a == mod:
a & (mod - 1) == 0
两个取首/尾元素并删除的方法：
public E pollFirst() {
int h = head;
@SuppressWarnings("unchecked")
E result = (E) elements[h];
// Element is null if deque empty
if (result == null)
return null;
elements[h] = null; // Must null out slot
head = (h + 1) & (elements.length - 1);
return result;
}
public E pollLast() {
int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
E result = (E) elements[t];
if (result == null)
return null;
elements[t] = null;
tail = t;
return result;
}
它们分别就是从数组中取指定下标的元素，并修改首/尾指针，最后返回。
再看两个比较低效并且不怎么用的方法：
- removeFirst/LastOccurrence(Object o)方法：
public boolean removeFirstOccurrence(Object o) {
if (o == null)
return false;
int mask = elements.length - 1;
int i = head;
Object x;
while ( (x = elements[i]) != null) {
if (o.equals(x)) {
delete(i);
return true;
}
i = (i + 1) & mask;
}
return false;
}
public boolean removeLastOccurrence(Object o) {
if (o == null)
return false;
int mask = elements.length - 1;
int i = (tail - 1) & mask;
Object x;
while ( (x = elements[i]) != null) {
if (o.equals(x)) {
delete(i);
return true;
}
i = (i - 1) & mask;
}
return false;
}
从首/尾部开始遍历，一直到找到相同的元素为止，再调用delete(int i)将其删除。delete方法里没有太多技术含量的代码，就不赘述了。
ArrayDeque里还有一些比如Iterator（比较简单），Spliterator（没用过）的代码，这边就不分析了。
总结
总体上来说，ArrayDeque的效率还是非常高的，大部分操作如从首尾插入或者读取都是O(1)的；但是队列的容量必须为2的幂这一点可能会构成很大的浪费。
比如，假设我要用的队列里元素最多的时候数量为2k，无论我们怎么努力，它会申请2(k+1)的长度，足足浪费了一半。这与ArrayList大不相同。个人认为，数组长度必须为2的幂，它所带来唯一的好处可能就是在取余的时候可以直接用位运算(&)来替代原本的取余操作(%)，提高一点运算效率，不知道今后的jdk会不会对其进行优化。
