引言：
ArrayDeque，被稱為「雙端隊列」，可以從兩端進行插入或刪除操作，當需要使用棧時，Java已不推薦使用Stack，而是推薦使用更高效的ArrayDeque，當需要使用隊列時也可以使用ArrayDeque。
ArrayDeque類簡介：
Deque的含義是「double ended queue」，即雙端隊列。它可以實現棧和隊列的功能，存在以下這些方法的關係：
隊列方法 雙端隊列方法
add(e) addLast(e)
offer(e) offerLast(e)
remove() removeFirst()
poll() pollFirst()
element() getFirst()
peek() peekFirst()
棧方法 雙端隊列方法
push(e) addFirst(e)
pop() removeFirst()
peek() peekFirst()
很明顯的，ArrayDeque類就是一個實現了兩頭插入刪除的隊列。
ArrayDeque類屬性：
主要屬性如下所示，為存放元素的數組elements，頭的索引位置head，尾的索引位置tail。
transient Object[] elements;
transient int head;
transient int tail;
ArrayDeque類的具體結構如下圖所示：
ArrayDeque結構
ArrayDeque的數組是循環數組，就是可以head在後，tail在前。
ArrayDeque類的數組容量：
如下源碼所示，ArrayDeque的數組容量由構造函數中調用allocateElements獲取，而allocateElements方法的邏輯如下：
-1. 如果傳入的容量參數numElements小於8，則使用8作為默認的容量。
-2.如果numElements>=8(且numElements<2的30次方)，則取numElements的下一個2的指數的值作為容量。
-3.如果numElements>=2的30次，則取2的30次作為容量。
舉個慄子：
numElements=9,
二進位為00000000 00000000 00000000 00001001
語句1後，結果為
00000000 00000000 00000000 00001101
語句2後，結果為
00000000 00000000 00000000 00001111
語句3，4，5執行後結果還是這個，就是15，再++就是16。
而numElements>=2的30次，則得到的結果為initialCapacity為-1，就是10000000 00000000 00000000 00000000，則右移一位，就是結果：01000000 00000000 00000000 00000000，2的30次。
private static final int MIN_INITIAL_CAPACITY = 8;
private void allocateElements(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
if (numElements >= initialCapacity) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> 1);//1
initialCapacity |= (initialCapacity >>> 2);//2
initialCapacity |= (initialCapacity >>> 4);//3
initialCapacity |= (initialCapacity >>> 8);//4
initialCapacity |= (initialCapacity >>> 16);//5
initialCapacity++;
if (initialCapacity < 0)
initialCapacity >>>= 1;
}
elements = new Object[initialCapacity];
}
總結：ArrayDeque的容量總為2的指數，默認是8，構造函數時不必刻意傳入2的指數，會自動計算。
如果傳入的值>=2的30次，則使用最大容量2的30次。
ArrayDeque類的元素插入操作：
如下代碼所示，為插入元素的操作，主要注意的是下標不能為越界。
這裡使用(head - 1) & (elements.length - 1) 這樣的方式來防止越界，elements.length - 1為低位全為1的二進位，與head-1做與運算，得到結果即可。
尾部插入操作也類似，都比較簡單。
如下圖所示：
addFirst操作
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
ArrayDeque類的擴容操作：
如下代碼所示，擴容操作主要分兩部分，容量申請為原來的兩倍，將head右邊的數據複製，將head左邊的數據複製。
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;
}
ArrayDeque類已基本介紹完畢，後續還有許多java容器的類，下次介紹。