public void test() {
    ArrayDeque<Integer> deque = new ArrayDeque<>();
    deque.addLast(100);
    System.out.println(deque);
    deque.addFirst(55);
    System.out.println(deque);
    deque.addLast(-55);
    System.out.println(deque);
    deque.removeFirst();
    System.out.println(deque);
    deque.removeLast();
    System.out.println(deque);
}

// 底層用于存儲具體數(shù)據(jù)的數(shù)組
transient Object[] elements;
// 這就是前面談到的 head
transient int head;
// 與上文談到的 tail 含義一樣
transient int tail;
// MIN_INITIAL_CAPACITY 表示數(shù)組 elements 的最短長度
private static final int MIN_INITIAL_CAPACITY = 8;

public ArrayDeque() {
    elements = new Object[16];
}

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

// tail 的初始值為 0 
public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    // 這里進(jìn)行的 & 位運(yùn)算 相當(dāng)于取余數(shù)操作
    // (tail + 1) & (elements.length - 1) == (tail + 1) % elements.length
    // 這個操作主要是用于判斷數(shù)組是否滿了，如果滿了則需要擴(kuò)容
    // 同時這個操作將 tail + 1，即 tail = tail + 1
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

// head 的初始值為 0 
public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    // 若此時數(shù)組長度elements.length = 16
    // 那么下面代碼執(zhí)行過后 head = 15
    // 下面代碼的操作結(jié)果和下面兩行代碼含義一致
    // elements[(head - 1 + elements.length) % elements.length] = e
    // head = (head - 1 + elements.length) % elements.length
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();
}

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;
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    // arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length)
    // 上面是函數(shù) System.arraycopy 的函數(shù)參數(shù)列表
    // 大家可以參考上面理解下面的拷貝代碼
    System.arraycopy(elements, p, a, 0, r);
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0;
    tail = n;
}

public E pollLast() {
    // 計算出待刪除的數(shù)據(jù)的下標(biāo)
    int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    E result = (E) elements[t];
    if (result == null)
        return null;
    // 將需要刪除的數(shù)據(jù)的下標(biāo)值設(shè)置為 null 這樣這塊內(nèi)存就
    // 可以被回收了
    elements[t] = null;
    tail = t;
    return result;
}
public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    // Element is null if deque empty
    if (result == null)
        return null;
    elements[h] = null;     // Must null out slot
    head = (h + 1) & (elements.length - 1);
    return result;
}