準(zhǔn)備知識(shí)

因?yàn)锳rrayDeque使用了循環(huán)隊(duì)列，所以首先要了解循環(huán)隊(duì)列數(shù)據(jù)結(jié)構(gòu)的原理。
http://www.itdecent.cn/p/5fa1d2234045

屬性

    // 存儲(chǔ)E類型元素的數(shù)組  
    private transient E[] elements;  
  
    // 循環(huán)隊(duì)列的頭元素索引  
    private transient int head;  
  
    // 循環(huán)隊(duì)列的尾元素索引   
    private transient int tail;  
  
    // 循環(huán)隊(duì)列的初始化最小容量為8   
    private static final int MIN_INITIAL_CAPACITY = 8;  

構(gòu)造方法

    // 構(gòu)造一個(gè)空的數(shù)組循環(huán)隊(duì)列，初始化Object數(shù)組長度為16  
    public ArrayDeque() {  
        elements = (E[]) new Object[16];  
    }  

    // 構(gòu)造一個(gè)指定長度的數(shù)組循環(huán)隊(duì)列
    public ArrayDeque(int numElements) {  
        allocateElements(numElements);  
    }  
  
    // 分配指定元素長度的Object數(shù)組  
    private void allocateElements(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  
        }  
        elements = (E[]) new Object[initialCapacity];  
    }  

    // 構(gòu)造一個(gè)包含指定 collection 的元素的循環(huán)隊(duì)列
    public ArrayDeque(Collection<? extends E> c) {  
        // 先分配集合c那么長的空間  
        allocateElements(c.size());  
        // 將c中的元素插入到雙端隊(duì)列中  
        addAll(c);  
    }  
      
    /**  
     * 插入集合c中的所有元素，設(shè)置標(biāo)記位modified代表是否插入元素。  
     * 如果插入元素了就返回標(biāo)記位為true。  
     */  
    public boolean addAll(Collection<? extends E> c) {  
        boolean modified = false;  
        for (E e : c)  
            if (add(e))  
                modified = true;  
        return modified;  
    }  
      
    // 在隊(duì)列的尾部插入元素e  
    public boolean add(E e) {  
        addLast(e);  
        return true;  
    }  
  
    public void addLast(E e) {  
        // 如果插入的元素為空，那么就拋出空指針異常  
        if (e == null)  
            throw new NullPointerException();  
        // 在隊(duì)列的尾部插入元素  
        elements[tail] = e;  
        /**  
         * 按照循環(huán)隊(duì)列的特點(diǎn)，隊(duì)滿時(shí)采用(tail+1)%elements.length==head,而在此處使用了與位運(yùn)算來代替取余運(yùn)算，由于位運(yùn)算速度快，所以這種方式效率高。  
         * 而此處代碼的意思是如果循環(huán)隊(duì)列已經(jīng)達(dá)到了隊(duì)滿的狀態(tài)，那么就進(jìn)行擴(kuò)容操作、并且賦值。  
         */  
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)  
            doubleCapacity();  
    }  
      
    // 將隊(duì)列擴(kuò)充原來的2倍，并且將元素復(fù)制到擴(kuò)充的數(shù)組中。
    private void doubleCapacity() {  
        assert head == tail;  
        // 設(shè)置暫時(shí)變量p，如果直接操作head，那么就會(huì)修改head。而本意是操作head而不修改head。  
        int p = head;  
        int n = elements.length;  
        // head右邊元素的個(gè)數(shù)  
        int r = n - p; // number of elements to the right of p  
        // 設(shè)置新容量，左移一位就相當(dāng)于擴(kuò)充為原來的2倍。  
        int newCapacity = n << 1;  
        // 如果新容量的小于0,那么就會(huì)拋出非法狀態(tài)異常。  
        if (newCapacity < 0)  
            throw new IllegalStateException("Sorry, deque too big");  
        // 創(chuàng)建新容量的Object數(shù)組  
        Object[] a = new Object[newCapacity];  
        // 將elements元素復(fù)制到數(shù)組a中，從elements數(shù)組的p開始，數(shù)組a從0開始，復(fù)制的長度為r  
        System.arraycopy(elements, p, a, 0, r);  
        // 將elements元素復(fù)制到數(shù)組a中，從elements數(shù)組的0開始，數(shù)組a從r開始，復(fù)制的長度為p  
        System.arraycopy(elements, 0, a, r, p);  
        // 將新數(shù)組a賦值給elements  
        elements = (E[])a;  
        // 然后設(shè)置新數(shù)組的頭索引為0.尾索引為n  
        head = 0;  
        tail = n;  
    }  

方法

addFirst方法：在隊(duì)列的頭部插入元素e。

    public void addFirst(E e) {  
        // 如果插入元素為空，那么就拋出空指針異常  
        if (e == null)  
            throw new NullPointerException();  
        // 與位運(yùn)算代替取余運(yùn)算，計(jì)算出新的頭索引的值，進(jìn)行插入元素e  
        elements[head = (head - 1) & (elements.length - 1)] = e;  
        // 如果頭索引和尾索引重合，達(dá)到了循環(huán)隊(duì)列的隊(duì)滿狀態(tài)，就進(jìn)行擴(kuò)容賦值操作  
        if (head == tail)  
            doubleCapacity();  
    }  

remove方法：獲取并移除此雙端隊(duì)列所表示的隊(duì)列的頭。

    public E remove() {  
        return removeFirst();  
    }  
  
    /**  
     * @throws NoSuchElementException {@inheritDoc}  
     */  
    public E removeFirst() {  
        E x = pollFirst();  
        if (x == null)  
            throw new NoSuchElementException();  
        return x;  
    }  
      
    public E pollFirst() {  
        int h = head;  
        E result = elements[h];  
        // 如果頭索引下標(biāo)對應(yīng)的元素為空，那么就返回空  
        if (result == null)  
            return null;  
        // 將頭索引處的元素設(shè)置為空  
        elements[h] = null;  
        // 將頭索引對應(yīng)的空元素，與運(yùn)算計(jì)算出新的索引值  
        head = (h + 1) & (elements.length - 1);  
        return result;  
    }  

總結(jié)

1. ArrayDeque采用循環(huán)隊(duì)列數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的。（所以增加、刪除、判斷隊(duì)空、判斷隊(duì)滿都是循環(huán)隊(duì)列的套路）
2. ArrayDeque增加元素，如果循環(huán)隊(duì)列容量不夠，那么就擴(kuò)容為原來的2倍。
3. ArrayDeque采用與位運(yùn)算來代替求余運(yùn)算，提高了效率。（用在判斷隊(duì)滿的時(shí)候）