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

棧、隊(duì)列、雙端隊(duì)列都是非常經(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)部用何種思路、方式去組織。
本篇博文重點(diǎn)關(guān)注這三種數(shù)據(jù)結(jié)構(gòu)在java中的對(duì)應(yīng)設(shè)計(jì)，并且對(duì)ArrayDeque的源碼進(jìn)行分析。

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

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

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

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

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

public
class Stack extends Vector {
    /* */
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

雙端隊(duì)列的定義也是接口：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如果判斷隊(duì)滿和隊(duì)空？

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

先來看內(nèi)部屬性。elements域就是存儲(chǔ)數(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ù)組的初始大小，默認(rèn)為16.

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

來看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的冪對(duì)齊。

看兩個(gè)入隊(duì)方法：

    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是從隊(duì)頭插入，addLast是從隊(duì)尾插入。

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

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

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

因此：

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

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

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

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

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

最后，這句：

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

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

出隊(duì)的代碼很顯然，不多解釋。

    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;
        // 擴(kuò)容后的大小小于0（溢出），也即隊(duì)列最大應(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;
    }

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

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

不過，在ArrayDeque的插入方法中并沒有修改modeCount字段。從ArrayDeque的迭代器的實(shí)現(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ā)生了變化。