ArrayDeque

Deque接口的大小可變數(shù)組的實(shí)現(xiàn)。

特性：

• 底層實(shí)現(xiàn)時循環(huán)數(shù)組
• 沒有容量限制，在數(shù)組元素裝滿時自動擴(kuò)容
• 禁止插入null元素
• 作為Stack和Queue時比LinkedList實(shí)現(xiàn)更好（前提是減少頻繁的擴(kuò)容和remove數(shù)組移動操作）
• 不是線程安全的

結(jié)構(gòu)：

public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable

所有方法：

arraydeque_1.png

主要字段：

// 存儲元素?cái)?shù)組大小是2的冪  
transient Object[] elements;

// head指針指向當(dāng)前元素并插入時由后向前移動
transient int head;

// tail指針指向下個添加元素的位置。插入由前往后
transient int tail;

// 數(shù)組的最小長度
private static final int MIN_INITIAL_CAPACITY = 8;

循環(huán)數(shù)組

循環(huán)數(shù)組通過保持?jǐn)?shù)組頭部head和尾部tail兩個元素指針按對應(yīng)的插入順序訪問元素。類似與鏈表的訪問

插入

初始化后，tail和head指針都指向數(shù)組下標(biāo)0。

addFirst將元素插入數(shù)組尾部(head-1) & length，插入后head指向當(dāng)前最近訪問元素，插入時需要將head指針向前移動一位head-1。

addLast將元素插入到數(shù)組頭部tail & length，插入后tail指向下一個插入位置(tail + 1) & length，插入時直接在tail位置插入，不需要移動。

插入圖示：

arraydeque_4.png

擴(kuò)容

當(dāng)tail==head時觸發(fā)擴(kuò)容操作。在插入數(shù)組最后一個空位時，相應(yīng)指針會移動一位使得tail == head。

將數(shù)組容量擴(kuò)大一倍，并將元素復(fù)制到新數(shù)組中。將 head部分移動到新數(shù)組前邊 ，tail部分移動到head部分后面，擴(kuò)大新增的數(shù)組部分在最后面，這樣保證head像新數(shù)組中由后往前<--移動，tail指針由前往后-->移動

擴(kuò)容圖示：

arraydeque_3.png

刪除

刪除兩端元素十分簡單，這里解釋循環(huán)數(shù)組中任意位置的刪除

刪除指定位置有2種情況

• 刪除位置i更靠近head位置，根據(jù)刪除位置i是否與head在同一端分為head <= i（同端）和head > i（異端）
• 刪除位置i更靠近tail位置，根據(jù)刪除位置i是否與tail在同一端分為tail >= i（同端）和tail < i（異端）

這里的同一端指都在循環(huán)數(shù)組的尾部或頭部

下面以head與刪除位置i的情況舉例，tail的刪除與head同理：

注意：此時front <= back 即刪除位置i更接近head ，應(yīng)該結(jié)合刪除的源代碼理解

同端（head <= i）

同端即head和刪除位置i在同一部分尾部或頭部，此時只需要將 刪除位置左邊的頭部元素右移覆蓋刪除位置 即可

arraydeque_7.png

另一種形式仍然是同端的刪除：

arraydeque_8.png

異端（head > i）

異端即head與刪除位置i分開在尾部和頭部（順序不定），由于head和刪除位置i在數(shù)組前端和后端（順序不定），刪除該位置需要將 刪除位置i前元素右移覆蓋刪除位置和將head部分右移一位 即可

1. 刪除位置i前的所有元素右移一位覆蓋刪除位置i
2. 將數(shù)組位置0使用head部分?jǐn)?shù)組末位元素替換
3. 移動head部分到數(shù)組末端并將head的元素置為null

arraydeque_6.png

delete源碼

    /**
     * Removes the element at the specified position in the elements array,
     * adjusting head and tail as necessary.  This can result in motion of
     * elements backwards or forwards in the array.
     *
     * <p>This method is called delete rather than remove to emphasize
     * that its semantics differ from those of {@link List#remove(int)}.
     *
     * @return true if elements moved backwards
     */
    /*
     * 刪除指定位置的元素。如果指定位置元素為null即刪除null時無論那種情況都不會報(bào)錯，而且能夠正常工作
     * 這個指定的null元素會被數(shù)組元素移動覆蓋。
     * 注意??！該方法返回值不表示刪除是否失?。?！返回false表示右移覆蓋刪除，返回true表示左移覆蓋刪除
     */
    private boolean delete(int i) {
        // assert 檢查
        checkInvariants();
        final Object[] elements = this.elements;
        final int mask = elements.length - 1;
        final int h = head;
        final int t = tail;
        // 刪除元素下標(biāo)i與head間隔front個，如：h=10,i=12,2&mask=2或h=8,i=2,t=3.-6&mask=10
        // 注意tail往左<--數(shù)組,head往右走-->
        final int front = (i - h) & mask;
        // 下標(biāo)i與tail間隔長度back如：h=8,i=2,t=3.1&mask=1
        final int back  = (t - i) & mask;

        // Invariant: head <= i < tail mod circularity
        // t-h&mask表示數(shù)組中含有這個多元素如16中t=3,h=8,共11個元素。3-8 & 15 = 11
        if (front >= ((t - h) & mask))
            throw new ConcurrentModificationException();

        // Optimize for least element motion
        // 刪除元素位置i更接近與head指針
        if (front < back) {
            // head和i在同一端  將[head...i-1]這些元素往后移動一位
            if (h <= i) {
                System.arraycopy(elements, h, elements, h + 1, front);
            } 
            // head和i不在同一端，需要移動i之前的元素后再移動head端的元素
            else { // Wrap around
                // 刪除位置i前的所有元素右移一位覆蓋i
                System.arraycopy(elements, 0, elements, 1, i);
                // 數(shù)組末位元素替換移動后的重復(fù)索引1位置的索引0的元素
                elements[0] = elements[mask];
                // 移動head部分即數(shù)組head到末端右移一位 
                System.arraycopy(elements, h, elements, h + 1, mask - h);
            }
            // 將移動后的head位置元素刪除
            elements[h] = null;
            // 更新head位置
            head = (h + 1) & mask;
            // 注意！??！這個false不是表示刪除失敗，而是表示通過右移覆蓋刪除
            return false;
        } 
        // 刪除位置更接近tail位置
        else {
            // 刪除位置與tail在同一端
            if (i < t) { // Copy the null tail as well
                // 將刪除位置i后面的tial部分元素左移一位覆蓋刪除位置
                System.arraycopy(elements, i + 1, elements, i, back);
                tail = t - 1;
            } 
            // 刪除位置與tail不在同一端
            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;
            }
            // 注意tail端不需要置tail位置為null，因?yàn)閠ail本為null,移動后用null覆蓋前面的位置了
            // 注意?。?！這個true不是表示刪除成功，而是表示通過左移覆蓋刪除
            return true;
        }
    }

總結(jié)

• 在數(shù)組中刪除元素都是移動元素覆蓋該位置。無論時同端還是異端都是將刪除位置前的元素移動一位覆蓋刪除位置，只不過由于異端時移動不能連續(xù)而已
• 指定位置靠近head時通過右移覆蓋刪除，指定位置靠近tail時通過左移覆蓋刪除

指針位置

在ArrayDeque為空時有head == tail，head != tail時ArrayDeque一定存在元素（在add時可能有短暫的head==tail觸發(fā)擴(kuò)容操作）

讀取時 head指針指向最近插入的head元素。tail指針指向下一個插入的tai元素位置即指向null，在addX插入擴(kuò)容時短暫與head相等而不指向null。

插入時 head需要向前移動一位插入新元素并置為head-1。tail直接插入當(dāng)前位置并指向下一個空位置

插入

在插入時必定tail <= head

刪除

刪除時tail和head的位置大小無法確定，哪一種都有可能

tail < head，指針head或tail都沒有過界，head仍然在尾部，tail在頭部

tail > head，指針head或tail有一個過界，head可能刪除到了頭部，或tail刪除到了尾部。不存在同時過界

tail == head，所有元素全部刪除完時tail == head，此時指針可能在數(shù)組任何位置

典型的指針位置圖示：

arraydeque_5.png

擴(kuò)容

分配空間

    /**
     * Allocates empty array to hold the given number of elements.
     *
     * @param numElements  the number of elements to hold
     */
    // 將指定數(shù)量numElements置為接近2^n如：numElements=56 被置為64.
    private void allocateElements(int numElements) {
        // 默認(rèn)數(shù)組最小長度為8
        int initialCapacity = MIN_INITIAL_CAPACITY;
        // Find the best power of two to hold elements.
        // Tests "<=" because arrays aren't kept full.
        // 如果是1<<30傳入進(jìn)來，最后所有30位都是1，++后就為2<<31溢出，溢出就取最大值2<<30
        if (numElements >= initialCapacity) {
            initialCapacity = numElements;
            initialCapacity |= (initialCapacity >>>  1);
            initialCapacity |= (initialCapacity >>>  2);
            initialCapacity |= (initialCapacity >>>  4);
            initialCapacity |= (initialCapacity >>>  8);
            initialCapacity |= (initialCapacity >>> 16);
            initialCapacity++;
            //溢出就取最大值2<<30
            if (initialCapacity < 0)   // Too many elements, must back off
                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
        }
        elements = new Object[initialCapacity];
    }

注意

• allocateElements使用位操作將指定元素?cái)?shù)量置為剛好大于該數(shù)量的2的次冪

下面是使用8bit模擬上面的過程

0100 1010       // numElements=74

0100 1010 
0010 0101   |   =>  0110 1111   //  >>>1

0110 1111
0001 1011   |   =>  0111 1111   //  >>>2

0111 1111
0000 0111   |   =>  0111 1111   //  >>>4

0111 1111   +1  =>  1000 0000   // initialCapacity=128

• 如果使用2的次冪指定ArrayDeque的大小仍然會將增大一倍。如指定為new ArrayDeque<>(16) ==> elements.length=32 即等價(jià)與new ArrayDeque<>(31)

    // 在源代碼包中創(chuàng)建才能調(diào)用private elements[]
    static void deleteTest() {
        ArrayDeque<String> deque = new ArrayDeque<>(8);
        deque.addFirst("d");
        deque.addFirst("e");
        
        deque.addLast("a");
        deque.addLast("r");
        deque.addLast("r");
        deque.addLast("a");
        deque.addLast("y");
        // 輸出：elements.length=16
        System.out.println("elements.length=" + deque.elements.length);
        // 輸出：[a, r, r, a, y, null, null, null, null, null, null, null, null, null, e, d]
        System.out.println(Arrays.toString(deque.elements));
    }

下面以指定大小參數(shù)為8分配后容量為16的過程：

numElements=8       initialCapacity=8   // 

0000 1000
0000 0100   |   =>  0000 1100   // >>>1

0000 1100
0000 0011   |   =>  0000 1111   // >>>2

0000 1111
0000 0000   |   =>  0000 1111   // >>>4

0000 1111   +1  =>  0001 0000   // initialCapacity=16

雙倍擴(kuò)容

    /**
     * Doubles the capacity of this deque.  Call only when full, i.e.,
     * when head and tail have wrapped around to become equal.
     */
    // 僅當(dāng)數(shù)組裝滿元素才擴(kuò)大一倍
    private void doubleCapacity() {
        // 檢查只有head與tail相等時才允許擴(kuò)容
        assert head == tail;
        int p = head;
        int n = elements.length;
        // p的右邊的元素個數(shù)
        int r = n - p; // number of elements to the right of p
        // 容量擴(kuò)大一倍
        int newCapacity = n << 1;
        // 2<<30溢出
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        // 右邊head開始到原數(shù)組最后r個元素復(fù)制到新數(shù)組0開始到r-1
        System.arraycopy(elements, p, a, 0, r);
        // head左邊的從0開始p個元素賦值到新數(shù)組從r開始到最后
        System.arraycopy(elements, 0, a, r, p);
        elements = a;
        head = 0;
        tail = n;
    }

注意

• ArrayDeque的擴(kuò)容只有在head==tail時即插入數(shù)組最后一個空位置時執(zhí)行擴(kuò)容操作，使得數(shù)組擴(kuò)大一倍。擴(kuò)容后的新數(shù)組與初始化時一樣，head指針由后往前，tail指針由原length位置往后
• ArrayDeque指定容量大小為2的次冪，如果不是2的次冪，會將指定容量提高為當(dāng)前最接近的2次冪
• 不應(yīng)該指定容量為2的次冪，ArrayDeque仍然會擴(kuò)大一次2的次冪，會增大一倍容量，如果已經(jīng)考慮過最大容量，那么這樣的設(shè)置將會增大一倍的空間浪費(fèi)

構(gòu)造器

    /**
     * Constructs an empty array deque with an initial capacity
     * sufficient to hold 16 elements.
     */
    public ArrayDeque() {
        elements = new Object[16];
    }
    /**
     * Constructs an empty array deque with an initial capacity
     * sufficient to hold the specified number of elements.
     *
     * @param numElements  lower bound on initial capacity of the deque
     */
    public ArrayDeque(int numElements) {
        // 取num的2次冪
        allocateElements(numElements);
    }
    
    /**
     * Constructs a deque containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.  (The first element returned by the collection's
     * iterator becomes the first element, or <i>front</i> of the
     * deque.)
     *
     * @param c the collection whose elements are to be placed into the deque
     * @throws NullPointerException if the specified collection is null
     */
    public ArrayDeque(Collection<? extends E> c) {
        allocateElements(c.size());
        addAll(c);
    }

注意

• 默認(rèn)的ArrayDeque構(gòu)造器創(chuàng)建的數(shù)組長度為16，而ArrayDeque能創(chuàng)建的最小數(shù)組長度即為16。根據(jù)allocateElements()與MIN_INITIAL_CAPACITY=8當(dāng)capacity<=8時仍然會調(diào)用allocateElements導(dǎo)致使用8增加一倍16。

隊(duì)列Queue

插入

• boolean add(E e)

    /**
     * Inserts the specified element at the end of this deque.
     *
     * <p>This method is equivalent to {@link #addLast}.
     *
     * @param e the element to add
     * @return {@code true} (as specified by {@link Collection#add})
     * @throws NullPointerException if the specified element is null
     */
    public boolean add(E e) {
        addLast(e);
        return true;
    }

• boolean offer(E e)

    /**
     * Inserts the specified element at the end of this deque.
     *
     * <p>This method is equivalent to {@link #offerLast}.
     *
     * @param e the element to add
     * @return {@code true} (as specified by {@link Queue#offer})
     * @throws NullPointerException if the specified element is null
     */
    public boolean offer(E e) {
        return offerLast(e);
    }

注意

• 與LinkedList一樣屬于無界隊(duì)列，不存在因?yàn)槿萘肯拗贫砑邮。詀ddX和offerX系列的方法本質(zhì)都是一樣的，但是作為queue使用時仍然應(yīng)該區(qū)分這兩種形式的api。

offer和add底層調(diào)用為addLast(E e)，但是在這兩個方法中一個前者可以返回false(實(shí)際仍然不可offerLast)，后者返回固定值true。在需要使用true/false驗(yàn)證時可以使用推薦offer方法

刪除

• E remove()

    /**
     * Retrieves and removes the head of the queue represented by this deque.
     *
     * This method differs from {@link #poll poll} only in that it throws an
     * exception if this deque is empty.
     *
     * <p>This method is equivalent to {@link #removeFirst}.
     *
     * @return the head of the queue represented by this deque
     * @throws NoSuchElementException {@inheritDoc}
     */
    public E remove() {
        return removeFirst();
    }

• E poll()

    /**
     * Retrieves and removes the head of the queue represented by this deque
     * (in other words, the first element of this deque), or returns
     * {@code null} if this deque is empty.
     *
     * <p>This method is equivalent to {@link #pollFirst}.
     *
     * @return the head of the queue represented by this deque, or
     *         {@code null} if this deque is empty
     */
    public E poll() {
        return pollFirst();
    }

注意

• remove和poll方法在隊(duì)列為空時前者拋出異常而后者返回null。底層實(shí)現(xiàn)均調(diào)用pollFirst()，區(qū)別在于前者判斷為null時拋出異常而后者返回null

檢查

• E element()

    /**
     * Retrieves, but does not remove, the head of the queue represented by
     * this deque.  This method differs from {@link #peek peek} only in
     * that it throws an exception if this deque is empty.
     *
     * <p>This method is equivalent to {@link #getFirst}.
     *
     * @return the head of the queue represented by this deque
     * @throws NoSuchElementException {@inheritDoc}
     */
    public E element() {
        return getFirst();
    }

• E peek()

    /**
     * Retrieves, but does not remove, the head of the queue represented by
     * this deque, or returns {@code null} if this deque is empty.
     *
     * <p>This method is equivalent to {@link #peekFirst}.
     *
     * @return the head of the queue represented by this deque, or
     *         {@code null} if this deque is empty
     */
    public E peek() {
        return peekFirst();
    }

注意

• element和peek方法底層實(shí)現(xiàn)都是返回head指針位置的數(shù)組元素，區(qū)別在于當(dāng)隊(duì)列為空時前者拋出異常而后者返回null

總結(jié)

• 將ArrayDeque作為隊(duì)列實(shí)現(xiàn)比LinkedList更好，因?yàn)槠浣共迦雗ull和有更好的性能

鏈表在訪問時不容易緩存命中，且需要更大的內(nèi)存，作為隊(duì)列唯一的好處是在迭代時更容易刪除。

ArrayDeque作為隊(duì)列針對與數(shù)組兩端add/remove操作時要快于LinkedList，而且數(shù)組訪問速度更快

但是，ArrayDeque在刪除時需要移動復(fù)制數(shù)組，所以盡量避免在迭代中刪除數(shù)組元素。另外需要減少在add時擴(kuò)容操作，所以在創(chuàng)建ArrayDeque時應(yīng)該指定容量

參考： Why is ArrayDeque better than LinkedList

堆棧Stack

入棧

    /**
     * Pushes an element onto the stack represented by this deque.  In other
     * words, inserts the element at the front of this deque.
     *
     * <p>This method is equivalent to {@link #addFirst}.
     *
     * @param e the element to push
     * @throws NullPointerException if the specified element is null
     */
    public void push(E e) {
        addFirst(e);
    }

出棧

    /**
     * Pops an element from the stack represented by this deque.  In other
     * words, removes and returns the first element of this deque.
     *
     * <p>This method is equivalent to {@link #removeFirst()}.
     *
     * @return the element at the front of this deque (which is the top
     *         of the stack represented by this deque)
     * @throws NoSuchElementException {@inheritDoc}
     */
    public E pop() {
        return removeFirst();
    }

檢查

    /**
     * Retrieves, but does not remove, the head of the queue represented by
     * this deque, or returns {@code null} if this deque is empty.
     *
     * <p>This method is equivalent to {@link #peekFirst}.
     *
     * @return the head of the queue represented by this deque, or
     *         {@code null} if this deque is empty
     */
    public E peek() {
        return peekFirst();
    }

雙端隊(duì)列Deque

插入

• void addFirst(E e)

    /**
     * Inserts the specified element at the front of this deque.
     *
     * @param e the element to add
     * @throws NullPointerException if the specified element is null
     */
    public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        // 對head指針取余，如head=0時，-1&15=15,14&15=14，將head指針從數(shù)組后面開始
        // 從head=e.length-1開始
        elements[head = (head - 1) & (elements.length - 1)] = e;
        // 擴(kuò)容
        if (head == tail)
            doubleCapacity();
    }

• void addLast(E e)

    /**
     * Inserts the specified element at the end of this deque.
     *
     * <p>This method is equivalent to {@link #add}.
     *
     * @param e the element to add
     * @throws NullPointerException if the specified element is null
     */
    public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        // 直接插入tail位置
        elements[tail] = e;
        // 將tail只想后一個位置 判斷tail == head就擴(kuò)容
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }

• boolean offerFirst(E e)

    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }

• public boolean offerLast(E e)

    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

注意

• addX和offerX在存在容量限制時插入失敗前者拋出異常，后者返回false。但ArrayDeque不存在容量限制因此兩者并無本質(zhì)區(qū)別
• addFirst與addLast在插入時使用位操作代替取余操作提高速度

ArrayDeque的底層數(shù)組大小為2的次冪，這樣可以使用位操作提高取余的速度

下面是使用8bit(最高位為符號位)進(jìn)行addFirst的取余操作過程：

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

head = 0        elements.length = 16    // 初始化時的設(shè)置
// 第一次插入
1111 1111       // (complement) head-1 =-1 
0000 1111   &   // elements.length - 1=15
0000 1111       // -1 & 15 = 15
// 第二次插入
0000 1110       // (complement) head(15)-1 = 14
0000 1111   &   // elements.length - 1 = 15
0000 1110       // 14 & 15 = 14

• 所有的插入方法都不允許插入null元素，否則拋出異常
• head指針指向最近插入頭部的元素，tail指針指向最近插入尾部元素的下一個空位置

刪除

• E removeFirst()

    /**
     * @throws NoSuchElementException {@inheritDoc}
     */
    public E removeFirst() {
        E x = pollFirst();
        if (x == null)
            throw new NoSuchElementException();
        return x;
    }

• E removeLast()

    /**
     * @throws NoSuchElementException {@inheritDoc}
     */
    public E removeLast() {
        E x = pollLast();
        if (x == null)
            throw new NoSuchElementException();
        return x;
    }

• E pollFirst()

    // 移除head指針元素并指向head+1
    public E pollFirst() {
        int h = head;
        @SuppressWarnings("unchecked")
        E result = (E) elements[h];
        // Element is null if deque empty
        if (result == null)
            return null;
        // 移除當(dāng)前頭部元素
        elements[h] = null;     // Must null out slot
        // head指針往前移動一位，指向新的頭部元素
        head = (h + 1) & (elements.length - 1);
        return result;
    }

• E pollLast()

    // 移除尾部元素
    public E pollLast() {
        // 將tail指針向前移動一位為刪除元素位置
        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;
    }

注意

• removeX和pollX方法都是移除雙端元素，底層方法也一致，區(qū)別在于當(dāng)隊(duì)列為空時前者拋出異常，后者返回null。
• 雙端隊(duì)列Deque是對兩端元素的移除，不會對隊(duì)列中的元素移除，所以不需要進(jìn)行數(shù)組元素移動的操作

檢查

• E getFirst()

    /**
     * @throws NoSuchElementException {@inheritDoc}
     */
    public E getFirst() {
        @SuppressWarnings("unchecked")
        E result = (E) elements[head];
        if (result == null)
            throw new NoSuchElementException();
        return result;
    }

• E getLast()

    /**
     * @throws NoSuchElementException {@inheritDoc}
     */
    public E getLast() {
        @SuppressWarnings("unchecked")
        E result = (E) elements[(tail - 1) & (elements.length - 1)];
        if (result == null)
            throw new NoSuchElementException();
        return result;
    }

• E peekFirst()

    @SuppressWarnings("unchecked")
    public E peekFirst() {
        // elements[head] is null if deque empty
        return (E) elements[head];
    }

• E peekLast()

    @SuppressWarnings("unchecked")
    public E peekLast() {
        return (E) elements[(tail - 1) & (elements.length - 1)];
    }

注意

• getX和peekX方法都是返回兩端元素，底層均為讀取數(shù)組元素，區(qū)別在于當(dāng)隊(duì)列為空時前者拋出異常，后者返回null
• First使用head指針，讀取時head指針指向頭部元素，Last使用tail指針，讀取時需要往前移動到尾部元素

移除內(nèi)部元素

• boolean removeFirstOccurrence(Object o)

    /**
     * Removes the first occurrence of the specified element in this
     * deque (when traversing the deque from head to tail).
     * If the deque does not contain the element, it is unchanged.
     * More formally, removes the first element {@code e} such that
     * {@code o.equals(e)} (if such an element exists).
     * Returns {@code true} if this deque contained the specified element
     * (or equivalently, if this deque changed as a result of the call).
     *
     * @param o element to be removed from this deque, if present
     * @return {@code true} if the deque contained the specified element
     */
    public boolean removeFirstOccurrence(Object o) {
        // ArrayDeque不允許null元素 直接返回false
        if (o == null)
            return false;
        // 掩碼   對head以后的下標(biāo)取余運(yùn)算
        int mask = elements.length - 1;
        int i = head;
        Object x;
        // 從頭部元素head開始遍歷整個隊(duì)列(到尾部元素完為止)
        while ( (x = elements[i]) != null) {
            if (o.equals(x)) {
                delete(i);
                return true;
            }
            i = (i + 1) & mask;
        }
        return false;
    }

• boolean removeLastOccurrence(Object o)

    /**
     * Removes the last occurrence of the specified element in this
     * deque (when traversing the deque from head to tail).
     * If the deque does not contain the element, it is unchanged.
     * More formally, removes the last element {@code e} such that
     * {@code o.equals(e)} (if such an element exists).
     * Returns {@code true} if this deque contained the specified element
     * (or equivalently, if this deque changed as a result of the call).
     *
     * @param o element to be removed from this deque, if present
     * @return {@code true} if the deque contained the specified element
     */
    public boolean removeLastOccurrence(Object o) {
        if (o == null)
            return false;
        int mask = elements.length - 1;
        // 從tail開始遍歷
        int i = (tail - 1) & mask;
        Object x;
        while ( (x = elements[i]) != null) {
            if (o.equals(x)) {
                // 刪除元素
                delete(i);
                return true;
            }
            i = (i - 1) & mask;
        }
        return false;
    }

注意

• delete相關(guān)源碼在循環(huán)數(shù)組部分已經(jīng)給出詳細(xì)解釋

集合Collection

添加

• boolean add(E e)

    /**
     * Inserts the specified element at the end of this deque.
     *
     * <p>This method is equivalent to {@link #addLast}.
     *
     * @param e the element to add
     * @return {@code true} (as specified by {@link Collection#add})
     * @throws NullPointerException if the specified element is null
     */
    public boolean add(E e) {
        addLast(e);
        return true;
    }

• boolean addAll(Collection<? extends E> c)

抽象類AbstractCollection的實(shí)現(xiàn)，通過c的迭代器調(diào)用add方法添加到arraydeque

移除

• void clear()

    /**
     * Removes all of the elements from this deque.
     * The deque will be empty after this call returns.
     */
    public void clear() {
        int h = head;
        int t = tail;
        // 驗(yàn)證當(dāng)前ArrayDeque是否為空  
        // 注意如果arraydeque不為空則head!=tail成立(在add時可能短暫的相等)
        if (h != t) { // clear all cells
            head = tail = 0;
            int i = h;
            int mask = elements.length - 1;
            // 按照head--tail指針遍歷移除元素  避免遍歷整個數(shù)組
            do {
                elements[i] = null;
                i = (i + 1) & mask;
            } while (i != t);
        }
    }

• boolean remove(Object o)

    /**
     * Removes a single instance of the specified element from this deque.
     * If the deque does not contain the element, it is unchanged.
     * More formally, removes the first element {@code e} such that
     * {@code o.equals(e)} (if such an element exists).
     * Returns {@code true} if this deque contained the specified element
     * (or equivalently, if this deque changed as a result of the call).
     *
     * <p>This method is equivalent to {@link #removeFirstOccurrence(Object)}.
     *
     * @param o element to be removed from this deque, if present
     * @return {@code true} if this deque contained the specified element
     */
    public boolean remove(Object o) {
        return removeFirstOccurrence(o);
    }

詳情參考Deque部分的移除內(nèi)部元素內(nèi)容

• boolean removeAll(Collection<?> c)

由抽象類AbstractCollection實(shí)現(xiàn)。使用在arraydeque的迭代器中將元素包含在c中的調(diào)用iterator.remove刪除

• boolean retainAll(Collection<?> c)

有抽象類AbstractCollection實(shí)現(xiàn)，與removeAll僅有的區(qū)別為不包含的調(diào)用iterator.remove刪除

注意

• 數(shù)組的移除需要移動數(shù)組元素，代價(jià)高昂
• clear()操作仍然保留底層數(shù)組，而且只在head--tail之中移除已設(shè)置的元素為null，不用遍歷完整的數(shù)組

查詢

• boolean contains(Object o)

    /**
     * Returns {@code true} if this deque contains the specified element.
     * More formally, returns {@code true} if and only if this deque contains
     * at least one element {@code e} such that {@code o.equals(e)}.
     *
     * @param o object to be checked for containment in this deque
     * @return {@code true} if this deque contains the specified element
     */
    public boolean contains(Object o) {
        if (o == null)
            return false;
        int mask = elements.length - 1;
        int i = head;
        Object x;
        // 由head開始遍歷 直到遇到與指定對象相等的元素或找不到相等元素
        while ( (x = elements[i]) != null) {
            if (o.equals(x))
                return true;
            i = (i + 1) & mask;
        }
        return false;
    }

• boolean containsAll(Collection<?> c)

由抽象類AbstractCollection實(shí)現(xiàn)，使用c的迭代器在每個元素上調(diào)用contains()

• boolean isEmpty()

    /**
     * Returns {@code true} if this deque contains no elements.
     *
     * @return {@code true} if this deque contains no elements
     */
    public boolean isEmpty() {
        return head == tail;
    }

• int size()

    /**
     * Returns the number of elements in this deque.
     *
     * @return the number of elements in this deque
     */
    public int size() {
        // 如：0 -- tail=3 -- head=7-- length=8 即tail-head=-4 & 7 = 4
        return (tail - head) & (elements.length - 1);
    }

比較和哈希

抽象類AbstractCollection使用Object類的默認(rèn)實(shí)現(xiàn)

迭代器

• Iterator<E> iterator()

    /**
     * Returns an iterator over the elements in this deque.  The elements
     * will be ordered from first (head) to last (tail).  This is the same
     * order that elements would be dequeued (via successive calls to
     * {@link #remove} or popped (via successive calls to {@link #pop}).
     *
     * @return an iterator over the elements in this deque
     */
    public Iterator<E> iterator() {
        return new DeqIterator();
    }

• Iterator<E> descendingIterator()

    public Iterator<E> descendingIterator() {
        return new DescendingIterator();
    }

    // 該類是DeqIterator類的鏡像，用tail代替head操作
    private class DescendingIterator implements Iterator<E> {
        /*
         * This class is nearly a mirror-image of DeqIterator, using
         * tail instead of head for initial cursor, and head instead of
         * tail for fence.
         */
        private int cursor = tail;
        private int fence = head;
        private int lastRet = -1;

        public boolean hasNext() {
            return cursor != fence;
        }

        public E next() {
            if (cursor == fence)
                throw new NoSuchElementException();
            cursor = (cursor - 1) & (elements.length - 1);
            @SuppressWarnings("unchecked")
            E result = (E) elements[cursor];
            if (head != fence || result == null)
                throw new ConcurrentModificationException();
            lastRet = cursor;
            return result;
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            if (!delete(lastRet)) {
                cursor = (cursor + 1) & (elements.length - 1);
                fence = head;
            }
            lastRet = -1;
        }
    }

并行迭代器

不熟悉暫不討論

實(shí)現(xiàn)

    private class DeqIterator implements Iterator<E> {
        /**
         * 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.
         */
        // 用于迭代完成檢查和結(jié)構(gòu)修改檢查
        private int fence = tail;

        /**
         * Index of element returned by most recent call to next.
         * Reset to -1 if element is deleted by a call to remove.
         */
        private int lastRet = -1;

        public boolean hasNext() { 
            // 是否迭代到tail位置 即完成迭代
            return cursor != fence;
        }

        public E next() {
            // 迭代完成 沒有元素了
            if (cursor == fence)
                throw new NoSuchElementException();
            @SuppressWarnings("unchecked")
            E result = (E) elements[cursor];
            // This check doesn't catch all possible comodifications,
            // but does catch the ones that corrupt traversal
            // 如果有其他線程修改了結(jié)構(gòu)  僅能保證正確的遍歷
            if (tail != fence || result == null)
                throw new ConcurrentModificationException();
            lastRet = cursor;
            // 下一個元素位置
            cursor = (cursor + 1) & (elements.length - 1);
            return result;
        }

        public void remove() {
            if (lastRet < 0) 
                throw new IllegalStateException();
            // 如果是左移 導(dǎo)致下一個元素移動到刪除位置lastRet即cursor-1上，類似與刪除數(shù)組上一個元素，需要將當(dāng)前cursor-1使在next能夠讀取到
            if (delete(lastRet)) { // if left-shifted, undo increment in next()
                // 設(shè)置為上一個位置 原cursor表示的元素被移動到cursor-1位置了
                cursor = (cursor - 1) & (elements.length - 1);
                // tail被改變 -1
                fence = tail;
            }// 如果時右移 不會影響當(dāng)前cursor位置上的元素，類似刪除數(shù)組下一個元素，保持當(dāng)前cursor  雖然head改變了 但是不影響cursor繼續(xù)遍歷
            lastRet = -1;
        }

        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            Object[] a = elements;
            int m = a.length - 1, f = fence, i = cursor;
            // 調(diào)用foreachremaining方法后不能在調(diào)用next方法
            cursor = f;
            // 從當(dāng)前位置cursor開始遍歷直到fence即tail為止
            while (i != f) {
                @SuppressWarnings("unchecked") E e = (E)a[i];
                i = (i + 1) & m;
                if (e == null)
                    throw new ConcurrentModificationException();
                action.accept(e);
            }
        }
    }

注意

• 循環(huán)數(shù)組的迭代有點(diǎn)類似與鏈表迭代，都是從head開始都tail結(jié)束，不同是循環(huán)數(shù)組的下一個元素需要用取余操作實(shí)現(xiàn)。
• 循環(huán)數(shù)組與鏈表在迭代的唯一劣勢就是remove()，因?yàn)閿?shù)組刪除元素需要移動數(shù)組元素。在循環(huán)數(shù)組中還需要考慮左移開始右移來判斷下一個位置元素是否被替換，左移被替換后需要更新當(dāng)前cursor為cursor-1

這里要說一個坑了，由于方法private boolean delete(int i)返回一個boolean值，最初沒有在意，以為表示是否刪除成功，當(dāng)我寫看到注釋This method is called delete rather than remove to emphasize that its semantics differ from those ofList.remove(int).什么叫強(qiáng)調(diào)與List.remove()不同，然后就忘記了這回事，等我寫完循環(huán)數(shù)組的刪除時，沒什么感覺，腦殼昏，沒有注意到front<back是返回false。然后在看迭代器時發(fā)現(xiàn)在remove()中if(delete(lastRet))，還能刪除失敗嗎，回去看了一眼，臥槽，front<back居然返回false，但是不對啊，指定元素都已經(jīng)被覆蓋了，刪除成功了啊，再回去看一下原來是表示右移，臥了個槽，還好還好，要是我當(dāng)時看到返回false，我估計(jì)直接崩潰，為什么要返回false。。。

delete的注釋中可能是想說，這個方法語義和remove不同，即執(zhí)行delete操作而已。

轉(zhuǎn)換數(shù)組

• Object[] toArray()

    /**
     * Returns an array containing all of the elements in this deque
     * in proper sequence (from first to last element).
     *
     * <p>The returned array will be "safe" in that no references to it are
     * maintained by this deque.  (In other words, this method must allocate
     * a new array).  The caller is thus free to modify the returned array.
     *
     * <p>This method acts as bridge between array-based and collection-based
     * APIs.
     *
     * @return an array containing all of the elements in this deque
     */
    public Object[] toArray() {
        return copyElements(new Object[size()]);
    }

• T[] toArray(T[] a)

    /**
     * Returns an array containing all of the elements in this deque in
     * proper sequence (from first to last element); the runtime type of the
     * returned array is that of the specified array.  If the deque fits in
     * the specified array, it is returned therein.  Otherwise, a new array
     * is allocated with the runtime type of the specified array and the
     * size of this deque.
     *
     * <p>If this deque fits in the specified array with room to spare
     * (i.e., the array has more elements than this deque), the element in
     * the array immediately following the end of the deque is set to
     * {@code null}.
     *
     * <p>Like the {@link #toArray()} method, this method acts as bridge between
     * array-based and collection-based APIs.  Further, this method allows
     * precise control over the runtime type of the output array, and may,
     * under certain circumstances, be used to save allocation costs.
     *
     * <p>Suppose {@code x} is a deque known to contain only strings.
     * The following code can be used to dump the deque into a newly
     * allocated array of {@code String}:
     *
     *  <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
     *
     * Note that {@code toArray(new Object[0])} is identical in function to
     * {@code toArray()}.
     *
     * @param a the array into which the elements of the deque are to
     *          be stored, if it is big enough; otherwise, a new array of the
     *          same runtime type is allocated for this purpose
     * @return an array containing all of the elements in this deque
     * @throws ArrayStoreException if the runtime type of the specified array
     *         is not a supertype of the runtime type of every element in
     *         this deque
     * @throws NullPointerException if the specified array is null
     */
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        int size = size();
        // 指定數(shù)組長度小于deque元素個數(shù)  創(chuàng)建長度為size的新數(shù)組
        if (a.length < size)
            a = (T[])java.lang.reflect.Array.newInstance(
                    a.getClass().getComponentType(), size);
        copyElements(a);
        // 指定數(shù)組長度過大，將a[size]置為null 后面的位置不影響
        if (a.length > size)
            a[size] = null;
        return a;
    }

實(shí)現(xiàn)

    /**
     * Copies the elements from our element array into the specified array,
     * in order (from first to last element in the deque).  It is assumed
     * that the array is large enough to hold all elements in the deque.
     *
     * @return its argument
     */
    // 復(fù)制elements數(shù)組到指定數(shù)組。需要指定數(shù)組長度至少為deque的元素個數(shù)
    private <T> T[] copyElements(T[] a) {
        // 即刪除head或tail到數(shù)組另一端
        // 如果循環(huán)數(shù)組是連續(xù)的一段head在tail前:[0--head--tail--e.length-1]
        if (head < tail) {
            System.arraycopy(elements, head, a, 0, size());
        }
        // 循環(huán)數(shù)組不是連續(xù)的一段，tail在head前面:[0--tail--head--e.length-1]
        else if (head > tail) {
            // head到數(shù)組末端的長度
            int headPortionLen = elements.length - head;
            // 先復(fù)制head右邊的元素head--length-1到數(shù)組a從0-headPortionLen-1
            System.arraycopy(elements, head, a, 0, headPortionLen);
            // 再復(fù)制tail左邊的元素從elements的0--tail
            System.arraycopy(elements, 0, a, headPortionLen, tail);
        }
        return a;
    }

注意

• toArray()無參方法與其余實(shí)現(xiàn)一樣，底層數(shù)組為Object[]，無法轉(zhuǎn)換為原來的類型，應(yīng)該盡量使用toArray(T[])，并且指定數(shù)組的大小推薦為deque.size()

參考：

• ArrayDeque源碼
• https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/4-Stack%20and%20Queue.md