ArrayDeque 數組迴圈隊列，這個數據結構設計的挺有意思的。據說此類很可能在用作堆棧時快於 Stack，在用作隊列時快於 LinkedList。一、容量 1.1預設容量是8=2^3 1.2指定初始化容容量此方法是給數組分配初始容量，初始容量並不是numElements，而是大於指定長度的 ...

ArrayDeque

數組迴圈隊列，這個數據結構設計的挺有意思的。據說此類很可能在用作堆棧時快於 Stack，在用作隊列時快於 LinkedList。

一、容量

1.1預設容量是8=2^3

1.2指定初始化容容量

    public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }
    private void allocateElements(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY;
        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 = new Object[initialCapacity];
    }

此方法是給數組分配初始容量，初始容量並不是numElements，而是大於指定長度的最小的2的冪正數所以ArrayDeque的容量一定是2的冪整數計算的方法是用或運算

1.3或運算的特點：

得到的結果大於等於任意一個操作數結果有趨向每個位都為1的趨勢所以這樣運算下來，運算得到的結果的二進位一定是每個位都是1,再加一個，就剛好是2的整數冪了

1.4擴展容量

當頭尾指針相遇，則數組存滿了 clipboard

此時要擴展容量，會調用

    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;//bit count faster
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);//copy the right of head(include head)
        System.arraycopy(elements, 0, a, r, p);//copy the left of the tail(exclude tail)
        elements = a;
        head = 0;
        tail = n;
    }

1.5細說doubleCapacity

註意看： 1.求兩本容量，n<<1，使用位運算要快於四則運算，因為這更貼近運算器電路的設計 2.複製原來的數組到目標數組要註意順序！可以看到，複製分兩次複製進行，第一次複製head指針右邊的元素（包括head指針指向的那個），第二次複製left指針左邊的元素（不包括tail指針指向的那個）擴展為原來兩本的容量，結果還是2的冪整數為什麼容量一定要是2的冪整數呢？待會說

二、頭尾指針

一開始，頭尾指針都在下標為0的地方，如果向隊頭插入數據，頭指針向左移，向隊尾插入數據，尾指針向右移 tail指針所在的位置，不存儲數據，代表下一次addLast存儲的地方

三、add

隊列提供增加到隊首和隊尾的兩種方法，註意看怎麼處理指針臨界狀態和指針迴圈

3.1addLast

    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+1了之後，超過數組長度，用與運算可以起到迴圈指針的效果，相當於(tail+1%elements.length) 因為elements.length一定是2的整數冪，當-1了之後每一位一定是1，當tile+1超過數組長度的時候，剛好是2的整數冪，則是10***00這種形式，所以與運算了之後，一定等於0

3.2addFirst

    public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
            doubleCapacity();
    }

當head-1<0的時候，用與運算可以得到絕對值，並且迴圈指針因為當head超過數組，head-1剛好是-1，則二進位每個都是1，與運算了之後，一定是111***111的正數，剛好是數組的最後一個位置

四、指針相遇

當tail == head的時候，首尾指針重合，此時隊列已滿，需要擴展隊列，調用doubleCapacity

五、利用空間局部性

在方法中需要多次調用的全局變數，最好創建一個局部變數來訪問因為全局變數是在靜態存儲區中的，局部變數是放在棧中的，和方法的指令中同一個區域，所以訪問會更快，提高程式性能就像下麵這樣

    public boolean removeFirstOccurrence(Object o) {
        if (o == null)
            return false;
        int mask = elements.length - 1;
        int i = head;
        Object x;
        while ( (x = elements[i]) != null) {
            if (o.equals(x)) {
                delete(i);
                return true;
            }
            i = (i + 1) & mask;
        }
        return false;
    }

創建了一個mask，來存放elements.length-1

6.優化刪除策略

    private boolean delete(int i) {
        checkInvariants();
        final Object[] elements = this.elements;
        final int mask = elements.length - 1;
        final int h = head;
        final int t = tail;
        final int front = (i - h) & mask;
        final int back  = (t - i) & mask;

        // Invariant: head <= i < tail mod circularity if (front >= ((t - h) & mask))
            throw new ConcurrentModificationException();

        // Optimize for least element motion
        //最優化刪除策略
        if (front < back) {//如果要刪除的元素在前半段
            if (h <= i) {//如果head在要刪除元素的前面
                System.arraycopy(elements, h, elements, h + 1, front);//將要刪除元素的前繼元素往後移動一格
            } else { // Wrap around
                System.arraycopy(elements, 0, elements, 1, i);//把i前面的元素往後挪一格
                elements[0] = elements[mask];
                System.arraycopy(elements, h, elements, h + 1, mask - h);//head-數組末端(不包括數組末端) 都往後移一格
            }
            elements[h] = null;//幫助垃圾收集
            head = (h + 1) & mask;//頭指針回退一格
            return false;
        } else {
            if (i < t) { // Copy the null tail as well
                System.arraycopy(elements, i + 1, elements, i, back);
                tail = t - 1;
            } else { // Wrap around
                System.arraycopy(elements, i + 1, elements, i, mask - i);
                elements[mask] = elements[0];
                System.arraycopy(elements, 1, elements, 0, t);
                tail = (t - 1) & mask;
            }
            return true;
        }
    }

這段源碼我覺得很值得一看，他用了最優刪除策略，都適用與數組實現的數據結構當刪除的時候，先計算刪除點是在隊列的上半段還是下半段如果是上半段，則上半段移動一格這樣子可以達到最少的元素移動！對於這種迴圈隊列，需要註意刪除元素的位置，有兩種特殊位置

6.1第一種特殊位置

此時刪除節點在隊列的上半段，但是上半段是斷開的這個時候要移動上半段的話，要分兩次移動第一次移動刪除元素前面的，第二次移動頭指針到數組末端

6.2第二種特殊位置

查看原文：http://blog.zswlib.com/2016/10/27/jdk%e6%ba%90%e7%a0%81%e5%88%86%e6%9e%90arraydeque/

jdk源碼分析ArrayDeque