概述
首先解释下，Queue（队列），队列是一种先进先出的数据结构（First In First Out，FIFO），经常和栈一起讨论，而栈是一种先进后出的数据结构（FILO）。队列有头指针head和尾指针tail，数据从队尾入队，从队头出队。费尽心力，画了一张图，真是灵魂画手。
而Deque被称为双端队列，队列的原则是只能一头入队，一头出队，而双端队列则是两端都可以入队和出队的队列。队列和栈两者很像，所以像我们今天要学习的这个ArrayDeque，就同时实现了它们两个的功能，可以称为是一种基于数组的双端队列。
我们可以先看下文档：
https://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeque.html
通过文档和我们实际使用，我们大概知道ArrayDeque队列有以下性质：
- 首先该类是JDK1.6才引入的，算引入的比较晚了，在以前版本的话，要使用队列的功能，一般要用LinkedList，或者自己封装实现；
- 队列不是线程安全的，并且不允许元素为空；
- 当用作堆栈时，这个类的速度可能比堆栈快，当用作队列时，它比LinkedList更快；
- 队列底层是由数组来实现的，没有容量限制，并且数组容量可以自动进行扩容。
- 队列有两个指针，头指针和尾指针，我们对队列进行的操作一般都是通过操作这两个指针进行的。
- 为了满足可以同时在数组两端进行插入和移除操作，该数组还必须是一个循环的数组，也就是说数组的任何一点都可以看作起点和终点。
继承结构和属性
public interface Deque<E> extends Queue<E> {
}
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable {
// 队列中存放数据的数组
transient Object[] elements;
// 头指针，或头索引
transient int head;
// 尾指针，或尾索引
transient int tail;
// 最小初始化数组容量
private static final int MIN_INITIAL_CAPACITY = 8;
}
从继承结构我们可以看出，Deque是继承自Queue的。
构造方法
/**
* 默认构造方法，初始容量为16
*/
public ArrayDeque() {
elements = new Object[16];
}
/**
* 用户指定数组容量
*/
public ArrayDeque(int numElements) {
allocateElements(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];
}
其中allocateElements方法是计算实际所需容量的。首先，numElements是用户指定的队列大小，allocateElements中这么多无符号右移运算操作，只是为了计算离numElements最近的且大于numElements的2的次方。比如，用户指定队列是15，那最终计算的结果就是2的4次方16。因为ArrayDeque规定，数组容量大小必须是2的幂。
The capacity of the deque is the length of this array, which is always a power of two.
首先，我们不妨想一下，对于用户指定的大小numElements，那离它最近的且大于numElements的2的次方应该是多少呢。
仔细想了之后，我们就会发觉，这个值应该是我们就将numElements转为二进制后，该二进制所有位都是1，然后再加1的值。比如numElements是10001，那距离它最近的那个值就将是11111 + 1。
initialCapacity |= (initialCapacity >>> 1);这里是将高2位设置为1；initialCapacity |= (initialCapacity >>> 2);这里是将高4位设置为1；initialCapacity |= (initialCapacity >>> 4);这里是将高8位设置为1；initialCapacity |= (initialCapacity >>> 8);这里是将高16位设置为1；initialCapacity |= (initialCapacity >>> 16);这里是将高32位，也就是int的全部位设置为1。- 这样，最终所有的位都变为了1，然后再加1就是2的次幂了。
addFirst和addLast
分别在头部和尾部插入元素：
/**
* 在队列头部插入元素，也就是在head之前位置插入元素
*/
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
// 如果两者相等，说明数组已经放满了元素，需要扩容
if (head == tail)
doubleCapacity();
}
/**
* 在队列尾部插入元素，也就是在tail位置插入元素
*/
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自减之后然后进行位与操作。因为elements.length一直是2的次幂，所以elements.length-1之后的二进制全是1，所以这里就相当于进行的是取余操作。而在尾部插入的话，其实和头部类似，只不过是直接插入到了尾部，然后tail加1。添加完之后，两个方法都会检测数组是否已满，如果满了，则进行扩容操作。这里判断是否已满的条件是head == 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;
}
这里，大概分以下几个步骤：
- 检测tail是否等于head；
- 创建一个原数组容量2倍的新数组；
3 将原数组从head位置一分为二，分别拷贝到新数组中；比如数组容量16，head位置是7，则先将原数组下标从7开始，拷贝16-7个元素到新的下标从0开始，元素个数为16-7的数组中。然后将原数组下标从0开始到7的元素拷贝到新数组下标从（16-7）开始，元素个数是7的数组中。这么做的目的就是为了拷贝到新数组的时候保持元素原来的顺序。- 重新确定头尾指针的位置。
与之相关联的两个方法 offerFirst 和 offerLast 方法，和addFirst，addLast唯一不同的是提供了是否添加成功的返回值。当然，都是返回的true。
pollFirst和pollLast
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，removeLast 这两个方法也是移除并返回元素，和pollFirst不同的是该接口会判断返回的值是否为null，如果为null，就抛出异常。也就是说，该方法不允许要移除的元素为null。
还有两个方法，peekFirst，peekLast也是返回头元素或尾元素，只是不移除元素。
remove，removeFirstOccurrence方法
public boolean remove(Object o) {
return removeFirstOccurrence(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;
}
- remove方法是删除队列中的指定元素，内部调用的是removeFirstOccurrence。这个方法是删除指定元素第一次出现的位置，该方法内部是通过遍历查询该元素，遍历的方向是从head下标到tail下标。
- 同样，和该方法类似的还有removeLastOccurrence方法，该方法是删除指定元素最后一次出现的位置，计算方式和removeFirstOccurrence恰好相反。
- 根据队列的定义，队列中一般不建议删除既非队头也非队尾的元素，要删除一般都是使用removeFirst或pollFirst就满足了，所以这两个方法并不经常用，并且这两个方法的查询都是线性时间。
size和isEmpty
/**
* 计算队列的长度
*/
public int size() {
return (tail - head) & (elements.length - 1);
}
/**
* 通过判断head是否等于tail来判断队列是否为空
*/
public boolean isEmpty() {
return head == tail;
}
至于getFirst，getLast，peekFirst，peekLast这些就是获取元素的方法，当然ArrayDeque还实现了队列Queue的各个方法。比如add，offer，remove等等，这些方法基本上都是调用以上Deque的方法实现的，没什么好说的。
ArrayDeque也提供了一些转换为数组的方法，底层是通过System.arraycopy实现的，不过这些都挺简单的，就不一一说了。
总结
- 一般情况下，ArrayDeque的效率还是挺高的，大多数方法都是在常数时间内运行，除了一些例如removeFirstOccurrence，removeLastOccurrence和一些批量操作是线性时间。
- 虽然LinkedList也提供了Deque的实现，不过官方还是建议我们使用ArrayDeque来实现队列的功能。所以如果我们有类似的功能，建议使用ArrayDeque来实现。
本文参考自：
ArrayDeque源码分析
https://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeque.html
