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

雙端隊列的動態(tài)數(shù)組實現(xiàn)
This class is likely to be faster than when used as a stack, and faster than LinkedList when used as a queue.

1. 數(shù)組大小分配算法
   2 ^ n <= numElements < 2 ^ (n+1) 分配 2 ^ (n+1)大小铃在。
   最少分配8，最多分配2 ^ 30個元素碍遍。

       /**
        * The minimum capacity that we'll use for a newly created deque.
        * Must be a power of 2.
        */
       private static final int MIN_INITIAL_CAPACITY = 8;
   
       // ******  Array allocation and resizing utilities ******
   
       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); //前2位為1
               initialCapacity |= (initialCapacity >>>  2); //前4位為1
               initialCapacity |= (initialCapacity >>>  4); //前8位為1
               initialCapacity |= (initialCapacity >>>  8); //前16位為1
               initialCapacity |= (initialCapacity >>> 16); //前32位為1
               initialCapacity++; //進1位
               if (initialCapacity < 0)   // Too many elements, must back off
                   initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
           }
           return initialCapacity;
       }
   

2. 容量擴充怕敬，加倍操作

   /**
    * Doubles the capacity of this deque.  Call only when full, i.e.,
    * when head and tail have wrapped around to become equal.
    */
   private void doubleCapacity() {
       assert head == tail;//相同位置东跪，說明數(shù)組已滿
       int p = head;
       int n = elements.length;
       int r = n - p; // number of elements to the right of p
       int newCapacity = n << 1;
       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;
   }
   ```   ?
   

3. 移動 機智的&操作
   index & (elements.length - 1) 從0開始到最后一位，然后回到第0位虽填。
   (index+elements.length) % elements.length 取模也可以丁恭，性能不如位運算；

   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();//空間滿了斋日，加倍
   }
   

   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;
   }
   

   size

   public int size() {
       return (tail - head) & (elements.length - 1);//-3與7牲览，剛好是8減3
   }
   

4. 刪除操作，刪除中間某個節(jié)點需要數(shù)組的移動桑驱。 有意思
   如果刪除節(jié)點靠近頭結點，則移動前半部分跛蛋，返回false熬的；
   如果刪除節(jié)點靠近尾結點，則移動后半部分赊级，返回true押框；-> 實現(xiàn)最少的數(shù)組移動

   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) {//刪除節(jié)點靠近頭結點
           if (h <= i) { //刪除節(jié)點在頭結點后邊，將front部分后移即可
               System.arraycopy(elements, h, elements, h + 1, front);
           } else { // 刪除節(jié)點在頭結點前邊理逊，分段處理
               System.arraycopy(elements, 0, elements, 1, i);
               elements[0] = elements[mask];
               System.arraycopy(elements, h, elements, h + 1, mask - h);
           }
           elements[h] = null;
           head = (h + 1) & mask;
           return false;
       } else {//刪除節(jié)點靠近尾結點
           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;
       }
   }
   

   ArrayDeque并不提供index訪問晋被，所以此函數(shù)只用于removeFirstOccurrence或者Iterator.remove

@夢工廠2018.3.10