前面我們介紹了隊列Queue的兩個實現類LinkedList和PriorityQueue，LinkedList還實現了雙端隊列接口Deque，Java容器類中還有一個雙端隊列的實現類ArrayDeque，它是基於數組實現的。
我們知道，一般而言，由於需要移動元素，數組的插入和刪除效率比較低，但ArrayDeque的效率卻非常高，它是怎麼實現的呢？本節我們就來詳細探討。
我們首先來看ArrayDeque的用法，然後來分析其實現原理，最後總結分析其特點。
用法
ArrayDeque實現了Deque接口，同LinkedList一樣，它的隊列長度也是沒有限制的，在LinkedList一節我們介紹過Deque接口，這裡簡要回顧一下。
Deque擴展了Queue，有隊列的所有方法，還可以看做棧，有棧的基本方法push/pop/peek，還有明確的操作兩端的方法如addFirst/removeLast等。
ArrayDeque有如下構造方法：
public ArrayDeque() public ArrayDeque(int numElements) public ArrayDeque(Collection<? extends E> c)
numElements表示元素個數，初始分配的空間會至少容納這麼多元素，但空間不是正好numElements這麼大，待會我們會看其實現細節。
ArrayDeque可以看做一個先進先出的隊列，比如：
Queue<String> queue = new ArrayDeque<>();
queue.offer("a");
queue.offer("b");
queue.offer("c");
while(queue.peek()!=null){
System.out.print(queue.poll() +" ");
}
輸出為：
a b c
也可以將ArrayDeque看做一個先進後出、後進先出的棧，比如：
Deque<String> stack = new ArrayDeque<>();
stack.push("a");
stack.push("b");
stack.push("c");
while(stack.peek()!=null){
System.out.print(stack.pop()+" ");
}
輸出為：
c b a
還可以使用其通用的操作兩端的方法，比如：
Deque<String> deque = new ArrayDeque<>();
deque.addFirst("a");
deque.offerLast("b");
deque.addLast("c");
deque.addFirst("d");
System.out.println(deque.getFirst()); //d
System.out.println(deque.peekLast()); //c
System.out.println(deque.removeFirst()); //d
System.out.println(deque.pollLast()); //c
ArrayDeque的用法是比較簡單的，下面我們來看其實現原理。
實現原理
內部組成
ArrayDeque內部主要有如下實例變量：
private transient E[] elements; private transient int head; private transient int tail;
elements就是存儲元素的數組。ArrayDeque的高效來源於head和tail這兩個變量，它們使得物理上簡單的從頭到尾的數組變為了一個邏輯上循環的數組，避免了在頭尾操作時的移動。我們來解釋下循環數組的概念。
循環數組
對於一般數組，比如arr，第一個元素為arr[0]，最後一個為arr[arr.length-1]。但對於ArrayDeque中的數組，它是一個邏輯上的循環數組，所謂循環是指元素到數組尾之後可以接著從數組頭開始，數組的長度、第一個和最後一個元素都與head和tail這兩個變量有關，具體來說：
我們來看一些圖示。
第一種情況，數組為空，head和tail相同，如下所示：
第二種情況，tail大於head，如下所示，都包含三個元素：
第三種情況，tail為0，如下所示：
第四情況，tail不為0，且小於head，如下所示：
理解了循環數組的概念，我們來看ArrayDeque一些主要操作的代碼，先來看構造方法。
構造方法
默認構造方法的代碼為：
public ArrayDeque() {
elements = (E[]) new Object[16];
}
分配了一個長度為16的數組。
如果有參數numElements，代碼為：
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
不是簡單的分配給定的長度，而是調用了allocateElements，代碼為：
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];
}
這段代碼看上去比較復雜，但主要就是在計算應該分配的數組的長度initialCapacity，計算邏輯是這樣的：
為什麼要為2的冪次數呢？我們待會會看到，這樣會使得很多操作的效率很高。
為什麼要嚴格大於numElements呢？因為循環數組必須時刻至少留一個空位，tail變量指向下一個空位，為了容納numElements個元素，至少需要numElements+1個位置。
這段代碼的晦澀之處在於：
initialCapacity |= (initialCapacity >>> 1); initialCapacity |= (initialCapacity >>> 2); initialCapacity |= (initialCapacity >>> 4); initialCapacity |= (initialCapacity >>> 8); initialCapacity |= (initialCapacity >>> 16); initialCapacity++;
這究竟在干什麼？其實，它是在將initialCapacity左邊最高位的1復制到右邊的每一位，這種復制類似於病毒復制，是1傳2、2傳4、4傳8式的指數級復制，最後再執行initialCapacity++就可以得到比initialCapacity大且為2的冪次方的最小的數。我們在剖析包裝類(中)一節介紹過Integer的一些二進制操作，其中就有非常類似的代碼：
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}
算法描述都在Hacker's Delight這本書中。
看最後一個構造方法：
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
同樣調用allocateElements分配數組，隨後調用了addAll，而addAll只是循環調用了add，下面我們來看add的實現。
從尾部添加
add方法的代碼為：
public boolean add(E e) {
addLast(e);
return true;
}
addLast的代碼為：
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
將元素添加到tail處，然後tail指向下一個位置，如果隊列滿了，則調用doubleCapacity擴展數組。tail的下一個位置是：(tail + 1) & (elements.length - 1)，如果與head相同，則隊列就滿了。
需要進行與操作是要保證索引在正確范圍，與(elements.length - 1)相與就可以得到下一個正確位置，是因為elements.length是2的冪次方，(elements.length - 1)的後幾位全是1，無論是正數還是負數，與(elements.length - 1)相與都能得到期望的下一個正確位置。
比如說，如果elements.length為8，則(elements.length - 1)為7，二進制為0111，對於負數-1，與7相與，結果為7，對於正數8，與7相與，結果為0，都能達到循環數組中找下一個正確位置的目的。
這種位操作是循環數組中一種常見的操作，效率也很高，後續代碼中還會看到。
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 = (E[])a;
head = 0;
tail = n;
}
分配一個長度翻倍的新數組a，將head右邊的元素拷貝到新數組開頭處，再拷貝左邊的元素到新數組中，最後重新設置head和tail，head設為0，tail設為n。
我們來看一個例子，假設原長度為8，head和tail為4，現在開始擴大數組，擴大前後的結構如下圖所示：
add是在末尾添加，我們再看在頭部添加的代碼。
從頭部添加
addFirst方法的代碼為：
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
在頭部添加，要先讓head指向前一個位置，然後再賦值給head所在位置。head的前一個位置是：(head - 1) & (elements.length - 1)。剛開始head為0，如果elements.length為8，則(head - 1) & (elements.length - 1)的結果為7。比如說，執行如下代碼：
Deque<String> queue = new ArrayDeque<>(7);
queue.addFirst("a");
queue.addFirst("b");
執行完後，內部結構會如下圖所示：
介紹完了添加，下面來看刪除。
從頭部刪除
removeFirst方法的代碼為：
public E removeFirst() {
E x = pollFirst();
if (x == null)
throw new NoSuchElementException();
return x;
}
pollFirst的代碼為：
public E pollFirst() {
int h = head;
E result = 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;
}
代碼比較簡單，將原頭部位置置為null，然後head置為下一個位置，下一個位置為：(h + 1) & (elements.length - 1)。
從尾部刪除
removeLast方法的代碼為：
public E removeLast() {
E x = pollLast();
if (x == null)
throw new NoSuchElementException();
return x;
}
pollLast的代碼為：
public E pollLast() {
int t = (tail - 1) & (elements.length - 1);
E result = elements[t];
if (result == null)
return null;
elements[t] = null;
tail = t;
return result;
}
t為最後一個位置，result為最後一個元素，將該位置置為null，然後修改tail指向前一個位置，最後返回原最後一個元素。
查看長度
ArrayDeque沒有單獨的字段維護長度，其size方法的代碼為：
public int size() {
return (tail - head) & (elements.length - 1);
}
通過該方法即可計算出size。
檢查給定元素是否存在
contains方法的代碼為：
public boolean contains(Object o) {
if (o == null)
return false;
int mask = elements.length - 1;
int i = head;
E x;
while ( (x = elements[i]) != null) {
if (o.equals(x))
return true;
i = (i + 1) & mask;
}
return false;
}
就是從head開始遍歷並進行對比，循環過程中沒有使用tail，而是到元素為null就結束了，這是因為在ArrayDeque中，有效元素不允許為null。
toArray方法
toArray方法的代碼為：
public Object[] toArray() {
return copyElements(new Object[size()]);
}
copyElements的代碼為：
private <T> T[] copyElements(T[] a) {
if (head < tail) {
System.arraycopy(elements, head, a, 0, size());
} else if (head > tail) {
int headPortionLen = elements.length - head;
System.arraycopy(elements, head, a, 0, headPortionLen);
System.arraycopy(elements, 0, a, headPortionLen, tail);
}
return a;
}
如果head小於tail，就是從head開始拷貝size()個，否則，拷貝邏輯與doubleCapacity方法中的類似，先拷貝從head到末尾的部分，然後拷貝從0到tail的部分。
原理小結
以上就是ArrayDeque的基本原理，內部它是一個動態擴展的循環數組，通過head和tail變量維護數組的開始和結尾，數組長度為2的冪次方，使用高效的位操作進行各種判斷，以及對head和tail的維護。
ArrayDeque特點分析
ArrayDeque實現了雙端隊列，內部使用循環數組實現，這決定了它有如下特點：
ArrayDeque和LinkedList都實現了Deque接口，應該用哪一個呢？如果只需要Deque接口，從兩端進行操作，一般而言，ArrayDeque效率更高一些，應該被優先使用，不過，如果同時需要根據索引位置進行操作，或者經常需要在中間進行插入和刪除，則應該選LinkedList。
小結
本節介紹了ArrayDeque的用法和實現原理，用法上，它實現了雙端隊列接口，可以作為隊列、棧、或雙端隊列使用，相比LinkedList效率要更高一些，實現原理上，它采用動態擴展的循環數組，使用高效率的位操作。
至此，關於隊列相關的容器類就介紹完了，我們介紹了LinkedList, PriorityQueue和ArrayDeque。PriorityQueue和ArrayDeque都是基於數組的，但都不是簡單的數組，通過一些特殊的約束、輔助成員和算法，它們都能高效的解決一些特定的問題，這大概是計算機程序中使用數據結構和算法的一種藝術吧。
關於Map和Set，我們介紹了兩種實現，一種基於哈希：HashMap/HashSet，另外一種基於樹：TreeMap/TreeSet，下面兩節，我們再來介紹兩種實現，它們有什麼特點呢？
----------------
未完待續，查看最新文章，敬請關注微信公眾號“老馬說編程”(掃描下方二維碼)，從入門到高級，深入淺出，老馬和你一起探索Java編程及計算機技術的本質。用心原創，保留所有版權。
