摘要：棧隊列雙端隊列都是非常經(jīng)典的數(shù)據(jù)結(jié)構(gòu)。結(jié)合了棧和隊列的特點。因此，在中，有棧的使用需求時，使用代替。迭代器之前源碼源碼之與字段中分析過，容器的實現(xiàn)中，所有修改過容器結(jié)構(gòu)的操作都需要修改字段。

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

先來簡單回顧下大學(xué)時的數(shù)據(jù)結(jié)構(gòu)知識。

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

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

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

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

public
class Stack extends Vector {
    /* */
}

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

Stack只有數(shù)組這一種實現(xiàn)方式，沒有辦法改用其它的實現(xiàn)方式。

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

此外，Vector本身現(xiàn)在已經(jīng)不建議使用了。

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

 * 
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像是棧和隊列的組合，也能當(dāng)棧使用。因此，在java中，有棧的使用需求時，使用Deque代替。

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

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

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

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

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

FIFO隊列。也就是數(shù)據(jù)結(jié)構(gòu)中的先進先出隊列。

優(yōu)先隊列。也就是數(shù)據(jù)結(jié)構(gòu)中的大頂堆或小頂堆。

阻塞隊列。也是隊列，只不過某些方法在沒有元素時或隊滿時會阻塞，并發(fā)中使用的一種結(jié)構(gòu)。

再來看它的幾種實現(xiàn)：

FIFO隊列。FIFO隊列的實現(xiàn)其實是按照Deque實現(xiàn)的了，有LinkedList和ArrayDeque。

優(yōu)先隊列。PriorityQueue。

阻塞隊列。這個和并發(fā)關(guān)系更大，這里先不談。

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

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

Deque也是Queue，Deque也能當(dāng)Queue用，沒有太多額外開銷。所以jdk沒有多帶帶實現(xiàn)Queue。

Deque有兩種實現(xiàn)類：

LinkedList。也就是鏈表，java的鏈表同時實現(xiàn)了Deque。

ArrayDeque。Deque的數(shù)組實現(xiàn)。為什么不在ArrayList中一把實現(xiàn)Deque接口？

也很簡單，實現(xiàn)方式不同。

Deque也有阻塞隊列版本的實現(xiàn)，這里也先不談。

我先來總結(jié)下ArrayDeque的實現(xiàn)思路。

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

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

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

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

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

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

如果判斷隊滿和隊空？

數(shù)組滿了怎么辦？

先來看內(nèi)部屬性。elements域就是存儲數(shù)據(jù)的原生數(shù)組。
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)];
    }

如果沒有指定內(nèi)部數(shù)組的初始大小，默認為16.

如果指定了內(nèi)部數(shù)組的初始大小，則通過calculateSize函數(shù)二次計算出大小。

來看calculateSize函數(shù)：

    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指向的是隊頭元素，永遠不可能一樣。

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

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

對應(yīng)位置插入位置，移動指針。

當(dāng)tail和head相等時，擴容。

最后，這句：

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

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

(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（溢出），也即隊列最大應(yīng)該是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;
    }

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

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

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

    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頭尾指針，就能判斷出迭代過程中是否發(fā)生了變化。