摘要：棧隊列雙端隊列都是非常經典的數據結構。結合了棧和隊列的特點。因此，在中，有棧的使用需求時，使用代替。迭代器之前源碼源碼之與字段中分析過，容器的實現中，所有修改過容器結構的操作都需要修改字段。

棧、隊列、雙端隊列都是非常經典的數據結構。和鏈表、數組不同，這三種數據結構的抽象層次更高。它只描述了數據結構有哪些行為，而并不關心數據結構內部用何種思路、方式去組織。
本篇博文重點關注這三種數據結構在java中的對應設計，并且對ArrayDeque的源碼進行分析。

先來簡單回顧下大學時的數據結構知識。

什么是棧？數據排成一個有序的序列，只能從一個口彈出數據或加入數據。即后進先出（LIFO）。

什么是隊列？數據同樣排成一個有序的序列，數據只能在隊尾加入，在隊頭彈出。即先進先出（FIFO）。

什么是雙端隊列？數據同樣排成一個有序的序列，只能從前后兩個口插入或刪除數據。結合了棧和隊列的特點。

這三樣東西都可以通過數組或鏈表來實現。從這種表述就能發現，似乎鏈表和數組比這三個更“偏底層”。
仔細思考不難發現，棧、隊列、雙端隊列僅僅是描述了接口行為，是一種抽象數據類型；而數組、鏈表則描述的是數據的具體在內存中的組織方式。

public
class Stack extends Vector {
    /* */
}

java的確有一個叫做Stack的類，它繼承自Vector。
個人以為，jdk的這種設計不是很妥當。前面分析過，Stack從概念上是一種抽象數據類型，可以有多種實現方式。因此，將其設計為接口更為合適。
jdk的這種設計導致：

Stack只有數組這一種實現方式，沒有辦法改用其它的實現方式。

Stack繼承自Vector，耦合太緊，同時擁有Vector的大量不屬于Stack模型的方法，破壞隱藏。

此外，Vector本身現在已經不建議使用了。

而且，jdk自己也說了，Stack這個類，設計的不好，不推薦使用：

 * 
A more complete and consistent set of LIFO stack operations is
 * provided by the {@link Deque} interface and its implementations, which
 * should be used in preference to this class.  For example:
 *   Deque stack = new ArrayDeque();}

好在Deque像是棧和隊列的組合，也能當棧使用。因此，在java中，有棧的使用需求時，使用Deque代替。

而且，偶然間在jdk中看到這樣一個工具函數Collections.asLifoQueue：

public static  Queue asLifoQueue(Deque deque) {
    return new AsLIFOQueue<>(deque);
}

它將Deque包裝成一個Lifo的隊列。LIFO？那不就是棧么！也就是說，得到的雖然是Queue接口，但是行為是LIFO。

public interface Queue extends Collection {
    /* ... */
}

jdk中隊列的設計沒有什么問題，是一個接口。
雖然名字叫Queue，但是這個jdk中Queue接口指代的范圍更廣。從它的子接口及實現類來看，有這樣幾種含義：

FIFO隊列。也就是數據結構中的先進先出隊列。

優先隊列。也就是數據結構中的大頂堆或小頂堆。

阻塞隊列。也是隊列，只不過某些方法在沒有元素時或隊滿時會阻塞，并發中使用的一種結構。

再來看它的幾種實現：

FIFO隊列。FIFO隊列的實現其實是按照Deque實現的了，有LinkedList和ArrayDeque。

優先隊列。PriorityQueue。

阻塞隊列。這個和并發關系更大，這里先不談。

雙端隊列的定義也是接口：

public interface Deque extends Queue {
    /* ... */
}

Deque也是Queue，Deque也能當Queue用，沒有太多額外開銷。所以jdk沒有多帶帶實現Queue。

Deque有兩種實現類：

LinkedList。也就是鏈表，java的鏈表同時實現了Deque。

ArrayDeque。Deque的數組實現。為什么不在ArrayList中一把實現Deque接口？

也很簡單，實現方式不同。

Deque也有阻塞隊列版本的實現，這里也先不談。

我先來總結下ArrayDeque的實現思路。

首先，ArrayDeque內部是擁有一個內部數組用于存儲數據。
其次，假設采用簡單的方案，即隊列數組按順序在數組里排開，那么：

由于ArrayDeque的兩端都能增刪數據，那么把數據插入到隊列頭部也就是數組頭部，會造成O(N)的時間復雜度。

假設只再隊尾加入而只從隊頭刪除，隊頭就會空出越來越多的空間。

那么該怎么實現？也很簡單。將物理上的連續數組回繞，形成邏輯上的一個 環形結構。即a[size - 1]的下一個位置是a[0].
之后，使用頭尾指針標識隊列頭尾，在隊列頭尾增刪元素，反映在頭尾指針上就是這兩個指針繞著環賽跑。

這個是大體思路，具體的還有一些細節，后面代碼里分析：

head和tail的具體概念是如何界定？

如果判斷隊滿和隊空？

數組滿了怎么辦？

先來看內部屬性。elements域就是存儲數據的原生數組。
head和tail分別分別為頭尾指針。

    transient Object[] elements; // non-private to simplify nested class access

    transient int head;

    transient int tail;

    public ArrayDeque() {
        elements = new Object[16];
    }

    public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }

    private void allocateElements(int numElements) {
        elements = new Object[calculateSize(numElements)];
    }

如果沒有指定內部數組的初始大小，默認為16.

如果指定了內部數組的初始大小，則通過calculateSize函數二次計算出大小。

來看calculateSize函數：

    private static final int MIN_INITIAL_CAPACITY = 8;

    private static int calculateSize(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
        }
        return initialCapacity;
    }

如果小于8，那么大小就為8.

如果大于等于8，則按照2的冪對齊。

看兩個入隊方法：

    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();
    }

addFirst是從隊頭插入，addLast是從隊尾插入。

從該代碼能夠分析出head和tail指針的含義：

head指針指向的是隊頭元素的位置，除非隊列為空。

tail指針指向的是隊尾元素后一格的位置，即尾后指針。

因此：

如果隊列沒有滿，tail指向的是空位置，head指向的是隊頭元素，永遠不可能一樣。

但是當隊列滿時，tail回繞會追上head，當tail等于head時，表示隊列滿了。

理清楚了這一點，上面的代碼也就十分容易理解了：

對應位置插入位置，移動指針。

當tail和head相等時，擴容。

最后，這句：

(head - 1) & (elements.length - 1)

曾經在《源碼|jdk源碼之HashMap分析(二)》中分析過，假如被余數是2的冪次方，那么模運算就能夠優化成按位與運算。
也即相當于：

(head - 1) % elements.length

    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;
    }

出隊的代碼很顯然，不多解釋。

    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;
        // 擴容后的大小小于0（溢出），也即隊列最大應該是2的30次方
        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;
    }

擴容的實現為按 兩倍 擴容原數組，將原數倍拷貝過去。
其中值得注意的是對數組大小溢出的處理。

之前《源碼|jdk源碼之LinkedList與modCount字段》中分析過，
容器的實現中，所有修改過容器結構的操作都需要修改modCount字段。
這樣迭代器迭代過程中，通過前后比對該字段來判斷容器是否被動過，及時拋出異常終止迭代以免造成不可預測的問題。

不過，在ArrayDeque的插入方法中并沒有修改modeCount字段。從ArrayDeque的迭代器的實現中可以看出來：

    private class DeqIterator implements Iterator {
        /**
         * Index of element to be returned by subsequent call to next.
         */
        private int cursor = head;

        /**
         * Tail recorded at construction (also in remove), to stop
         * iterator and also to check for comodification.
         */
        private int fence = tail;
    }

原來，ArrayDeque直接使用了head和tail頭尾指針，就能判斷出迭代過程中是否發生了變化。