准备知识
因为ArrayDeque使用了循环队列，所以首先要了解循环队列数据结构的原理。
https://www.jianshu.com/p/5fa1d2234045
属性
// 存储E类型元素的数组
private transient E[] elements;
// 循环队列的头元素索引
private transient int head;
// 循环队列的尾元素索引
private transient int tail;
// 循环队列的初始化最小容量为8
private static final int MIN_INITIAL_CAPACITY = 8;
构造方法
// 构造一个空的数组循环队列，初始化Object数组长度为16
public ArrayDeque() {
elements = (E[]) new Object[16];
}
// 构造一个指定长度的数组循环队列
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
// 分配指定元素长度的Object数组
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 = (E[]) new Object[initialCapacity];
}
// 构造一个包含指定 collection 的元素的循环队列
public ArrayDeque(Collection<? extends E> c) {
// 先分配集合c那么长的空间
allocateElements(c.size());
// 将c中的元素插入到双端队列中
addAll(c);
}
/**
* 插入集合c中的所有元素，设置标记位modified代表是否插入元素。
* 如果插入元素了就返回标记位为true。
*/
public boolean addAll(Collection<? extends E> c) {
boolean modified = false;
for (E e : c)
if (add(e))
modified = true;
return modified;
}
// 在队列的尾部插入元素e
public boolean add(E e) {
addLast(e);
return true;
}
public void addLast(E e) {
// 如果插入的元素为空，那么就抛出空指针异常
if (e == null)
throw new NullPointerException();
// 在队列的尾部插入元素
elements[tail] = e;
/**
* 按照循环队列的特点，队满时采用(tail+1)%elements.length==head,而在此处使用了与位运算来代替取余运算，由于位运算速度快，所以这种方式效率高。
* 而此处代码的意思是如果循环队列已经达到了队满的状态，那么就进行扩容操作、并且赋值。
*/
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
// 将队列扩充原来的2倍，并且将元素复制到扩充的数组中。
private void doubleCapacity() {
assert head == tail;
// 设置暂时变量p，如果直接操作head，那么就会修改head。而本意是操作head而不修改head。
int p = head;
int n = elements.length;
// head右边元素的个数
int r = n - p; // number of elements to the right of p
// 设置新容量，左移一位就相当于扩充为原来的2倍。
int newCapacity = n << 1;
// 如果新容量的小于0,那么就会抛出非法状态异常。
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
// 创建新容量的Object数组
Object[] a = new Object[newCapacity];
// 将elements元素复制到数组a中，从elements数组的p开始，数组a从0开始，复制的长度为r
System.arraycopy(elements, p, a, 0, r);
// 将elements元素复制到数组a中，从elements数组的0开始，数组a从r开始，复制的长度为p
System.arraycopy(elements, 0, a, r, p);
// 将新数组a赋值给elements
elements = (E[])a;
// 然后设置新数组的头索引为0.尾索引为n
head = 0;
tail = n;
}
方法
addFirst方法：在队列的头部插入元素e。
public void addFirst(E e) {
// 如果插入元素为空，那么就抛出空指针异常
if (e == null)
throw new NullPointerException();
// 与位运算代替取余运算，计算出新的头索引的值，进行插入元素e
elements[head = (head - 1) & (elements.length - 1)] = e;
// 如果头索引和尾索引重合，达到了循环队列的队满状态，就进行扩容赋值操作
if (head == tail)
doubleCapacity();
}
remove方法：获取并移除此双端队列所表示的队列的头。
public E remove() {
return removeFirst();
}
/**
* @throws NoSuchElementException {@inheritDoc}
*/
public E removeFirst() {
E x = pollFirst();
if (x == null)
throw new NoSuchElementException();
return x;
}
public E pollFirst() {
int h = head;
E result = elements[h];
// 如果头索引下标对应的元素为空，那么就返回空
if (result == null)
return null;
// 将头索引处的元素设置为空
elements[h] = null;
// 将头索引对应的空元素，与运算计算出新的索引值
head = (h + 1) & (elements.length - 1);
return result;
}
总结
1. ArrayDeque采用循环队列数据结构设计的。（所以增加、删除、判断队空、判断队满都是循环队列的套路）
2. ArrayDeque增加元素，如果循环队列容量不够，那么就扩容为原来的2倍。
3. ArrayDeque采用与位运算来代替求余运算，提高了效率。（用在判断队满的时候）
