ArrayDeque

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

特性：

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

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

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

所有方法：

arraydeque_1.png

主要字段：

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

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

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

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

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

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

插入

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

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

addLast將元素插入到數(shù)組頭部tail & length，插入后tail指向下一個(gè)插入位置(tail + 1) & length剿骨，插入時(shí)直接在tail位置插入代芜，不需要移動(dòng)。

插入圖示：

arraydeque_4.png

擴(kuò)容

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

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

擴(kuò)容圖示：

arraydeque_3.png

刪除

刪除兩端元素十分簡(jiǎn)單牙甫，這里解釋循環(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同理：

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

同端（head <= i）

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

arraydeque_7.png

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

arraydeque_8.png

異端（head > i）

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

1. 刪除位置i前的所有元素右移一位覆蓋刪除位置i
2. 將數(shù)組位置0使用head部分?jǐn)?shù)組末位元素替換
3. 移動(dòng)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時(shí)無(wú)論那種情況都不會(huì)報(bào)錯(cuò)，而且能夠正常工作
     * 這個(gè)指定的null元素會(huì)被數(shù)組元素移動(dòng)覆蓋阿蝶。
     * 注意ｖǚ妗！該方法返回值不表示刪除是否失斚劢唷ｇ韫！返回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個(gè)辛蚊，如：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間隔長(zhǎng)度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ù)組中含有這個(gè)多元素如16中t=3,h=8,共11個(gè)元素。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]這些元素往后移動(dòng)一位
            if (h <= i) {
                System.arraycopy(elements, h, elements, h + 1, front);
            } 
            // head和i不在同一端真仲，需要移動(dòng)i之前的元素后再移動(dòng)head端的元素
            else { // Wrap around
                // 刪除位置i前的所有元素右移一位覆蓋i
                System.arraycopy(elements, 0, elements, 1, i);
                // 數(shù)組末位元素替換移動(dòng)后的重復(fù)索引1位置的索引0的元素
                elements[0] = elements[mask];
                // 移動(dòng)head部分即數(shù)組head到末端右移一位 
                System.arraycopy(elements, h, elements, h + 1, mask - h);
            }
            // 將移動(dòng)后的head位置元素刪除
            elements[h] = null;
            // 更新head位置
            head = (h + 1) & mask;
            // 注意Ｓ恕！举农！這個(gè)false不是表示刪除失敗蔫浆，而是表示通過(guò)右移覆蓋刪除
            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,移動(dòng)后用null覆蓋前面的位置了
            // 注意Ｈ硖洹Ｉ５！這個(gè)true不是表示刪除成功祸挪，而是表示通過(guò)左移覆蓋刪除
            return true;
        }
    }

總結(jié)

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

指針位置

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

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

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

插入

在插入時(shí)必定tail <= head

刪除

刪除時(shí)tail和head的位置大小無(wú)法確定悄蕾，哪一種都有可能

tail < head票顾，指針head或tail都沒(méi)有過(guò)界，head仍然在尾部帆调，tail在頭部

tail > head奠骄，指針head或tail有一個(gè)過(guò)界，head可能刪除到了頭部番刊，或tail刪除到了尾部含鳞。不存在同時(shí)過(guò)界

tail == head，所有元素全部刪除完時(shí)tail == head芹务，此時(shí)指針可能在數(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ù)組最小長(zhǎng)度為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)來(lái)蝉绷，最后所有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模擬上面的過(guò)程

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的大小仍然會(huì)將增大一倍熔吗。如指定為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的過(guò)程：

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相等時(shí)才允許擴(kuò)容
        assert head == tail;
        int p = head;
        int n = elements.length;
        // p的右邊的元素個(gè)數(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開(kāi)始到原數(shù)組最后r個(gè)元素復(fù)制到新數(shù)組0開(kāi)始到r-1
        System.arraycopy(elements, p, a, 0, r);
        // head左邊的從0開(kāi)始p個(gè)元素賦值到新數(shù)組從r開(kāi)始到最后
        System.arraycopy(elements, 0, a, r, p);
        elements = a;
        head = 0;
        tail = n;
    }

注意

• ArrayDeque的擴(kuò)容只有在head==tail時(shí)即插入數(shù)組最后一個(gè)空位置時(shí)執(zhí)行擴(kuò)容操作辆床，使得數(shù)組擴(kuò)大一倍。擴(kuò)容后的新數(shù)組與初始化時(shí)一樣桅狠，head指針由后往前讼载，tail指針由原length位置往后
• ArrayDeque指定容量大小為2的次冪，如果不是2的次冪中跌，會(huì)將指定容量提高為當(dāng)前最接近的2次冪
• 不應(yīng)該指定容量為2的次冪咨堤，ArrayDeque仍然會(huì)擴(kuò)大一次2的次冪，會(huì)增大一倍容量漩符，如果已經(jīng)考慮過(guò)最大容量一喘，那么這樣的設(shè)置將會(huì)增大一倍的空間浪費(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ù)組長(zhǎng)度為16，而ArrayDeque能創(chuàng)建的最小數(shù)組長(zhǎng)度即為16嗜暴。根據(jù)allocateElements()與MIN_INITIAL_CAPACITY=8當(dāng)capacity<=8時(shí)仍然會(huì)調(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一樣屬于無(wú)界隊(duì)列，不存在因?yàn)槿萘肯拗贫砑邮∽粕耍詀ddX和offerX系列的方法本質(zhì)都是一樣的触徐，但是作為queue使用時(shí)仍然應(yīng)該區(qū)分這兩種形式的api咪鲜。

offer和add底層調(diào)用為addLast(E e)狐赡，但是在這兩個(gè)方法中一個(gè)前者可以返回false(實(shí)際仍然不可offerLast)，后者返回固定值true疟丙。在需要使用true/false驗(yàn)證時(shí)可以使用推薦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ì)列為空時(shí)前者拋出異常而后者返回null颖侄。底層實(shí)現(xiàn)均調(diào)用pollFirst()，區(qū)別在于前者判斷為null時(shí)拋出異常而后者返回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ì)列為空時(shí)前者拋出異常而后者返回null

總結(jié)

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

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

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

但是苔咪，ArrayDeque在刪除時(shí)需要移動(dòng)復(fù)制數(shù)組锰悼，所以盡量避免在迭代中刪除數(shù)組元素。另外需要減少在add時(shí)擴(kuò)容操作团赏，所以在創(chuàng)建ArrayDeque時(shí)應(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();
        // 對(duì)head指針取余箕般，如head=0時(shí)，-1&15=15,14&15=14舔清，將head指針從數(shù)組后面開(kāi)始
        // 從head=e.length-1開(kāi)始
        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只想后一個(gè)位置 判斷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在存在容量限制時(shí)插入失敗前者拋出異常丝里，后者返回false曲初。但ArrayDeque不存在容量限制因此兩者并無(wú)本質(zhì)區(qū)別
• addFirst與addLast在插入時(shí)使用位操作代替取余操作提高速度

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

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

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

head = 0        elements.length = 16    // 初始化時(shí)的設(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指針指向最近插入尾部元素的下一個(gè)空位置

刪除

• 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指針往前移動(dòng)一位，指向新的頭部元素
        head = (h + 1) & (elements.length - 1);
        return result;
    }

• E pollLast()

    // 移除尾部元素
    public E pollLast() {
        // 將tail指針向前移動(dòng)一位為刪除元素位置
        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ì)列為空時(shí)前者拋出異常，后者返回null纷捞。
• 雙端隊(duì)列Deque是對(duì)兩端元素的移除痢虹，不會(huì)對(duì)隊(duì)列中的元素移除，所以不需要進(jìn)行數(shù)組元素移動(dòng)的操作

檢查

• 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ì)列為空時(shí)前者拋出異常，后者返回null
• First使用head指針糜值，讀取時(shí)head指針指向頭部元素丰捷，Last使用tail指針，讀取時(shí)需要往前移動(dòng)到尾部元素

移除內(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;
        // 掩碼   對(duì)head以后的下標(biāo)取余運(yùn)算
        int mask = elements.length - 1;
        int i = head;
        Object x;
        // 從頭部元素head開(kāi)始遍歷整個(gè)隊(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開(kāi)始遍歷
        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)寂汇，通過(guò)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時(shí)可能短暫的相等)
        if (h != t) { // clear all cells
            head = tail = 0;
            int i = h;
            int mask = elements.length - 1;
            // 按照head--tail指針遍歷移除元素  避免遍歷整個(gè)數(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ù)組的移除需要移動(dòng)數(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開(kāi)始遍歷 直到遇到與指定對(duì)象相等的元素或找不到相等元素
        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的迭代器在每個(gè)元素上調(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() {
            // 迭代完成 沒(méi)有元素了
            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;
            // 下一個(gè)元素位置
            cursor = (cursor + 1) & (elements.length - 1);
            return result;
        }

        public void remove() {
            if (lastRet < 0) 
                throw new IllegalStateException();
            // 如果是左移 導(dǎo)致下一個(gè)元素移動(dòng)到刪除位置lastRet即cursor-1上，類似與刪除數(shù)組上一個(gè)元素扒磁，需要將當(dāng)前cursor-1使在next能夠讀取到
            if (delete(lastRet)) { // if left-shifted, undo increment in next()
                // 設(shè)置為上一個(gè)位置 原cursor表示的元素被移動(dòng)到cursor-1位置了
                cursor = (cursor - 1) & (elements.length - 1);
                // tail被改變 -1
                fence = tail;
            }// 如果時(shí)右移 不會(huì)影響當(dāng)前cursor位置上的元素庆揪，類似刪除數(shù)組下一個(gè)元素，保持當(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開(kāi)始遍歷直到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開(kāi)始都tail結(jié)束缸榛，不同是循環(huán)數(shù)組的下一個(gè)元素需要用取余操作實(shí)現(xiàn)。
• 循環(huán)數(shù)組與鏈表在迭代的唯一劣勢(shì)就是remove()兰伤，因?yàn)閿?shù)組刪除元素需要移動(dòng)數(shù)組元素内颗。在循環(huán)數(shù)組中還需要考慮左移開(kāi)始右移來(lái)判斷下一個(gè)位置元素是否被替換，左移被替換后需要更新當(dāng)前cursor為cursor-1

這里要說(shuō)一個(gè)坑了医清，由于方法private boolean delete(int i)返回一個(gè)boolean值起暮，最初沒(méi)有在意，以為表示是否刪除成功，當(dāng)我寫(xiě)看到注釋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()不同负懦，然后就忘記了這回事筒捺，等我寫(xiě)完循環(huán)數(shù)組的刪除時(shí)，沒(méi)什么感覺(jué)纸厉，腦殼昏系吭，沒(méi)有注意到front<back是返回false。然后在看迭代器時(shí)發(fā)現(xiàn)在remove()中if(delete(lastRet))颗品，還能刪除失敗嗎肯尺，回去看了一眼，臥槽躯枢，front<back居然返回false则吟，但是不對(duì)啊，指定元素都已經(jīng)被覆蓋了锄蹂，刪除成功了啊氓仲，再回去看一下原來(lái)是表示右移，臥了個(gè)槽得糜，還好還好敬扛，要是我當(dāng)時(shí)看到返回false，我估計(jì)直接崩潰朝抖，為什么要返回false啥箭。。治宣。

delete的注釋中可能是想說(shuō)急侥，這個(gè)方法語(yǔ)義和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ù)組長(zhǎng)度小于deque元素個(gè)數(shù)  創(chuàng)建長(zhǎng)度為size的新數(shù)組
        if (a.length < size)
            a = (T[])java.lang.reflect.Array.newInstance(
                    a.getClass().getComponentType(), size);
        copyElements(a);
        // 指定數(shù)組長(zhǎng)度過(guò)大缆巧，將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ù)組長(zhǎng)度至少為deque的元素個(gè)數(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ù)組末端的長(zhǎng)度
            int headPortionLen = elements.length - head;
            // 先復(fù)制head右邊的元素head--length-1到數(shù)組a從0-headPortionLen-1
            System.arraycopy(elements, head, a, 0, headPortionLen);
            // 再?gòu)?fù)制tail左邊的元素從elements的0--tail
            System.arraycopy(elements, 0, a, headPortionLen, tail);
        }
        return a;
    }

注意

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

參考：

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