public interface Deque<E> extends Queue<E> {
 // 添加元素到隊列頭
 void addFirst(E e);
 // 添加元素到隊列尾
 void addLast(E e);
 // 添加元素到隊列頭
 boolean offerFirst(E e);
 // 添加元素到隊列尾
 boolean offerLast(E e);
 // 從隊列頭移除元素
 E removeFirst();
 // 從隊列尾移除元素
 E removeLast();
 // 從隊列頭移除元素
 E pollFirst();
 // 從隊列尾移除元素
 E pollLast();
 // 查看隊列頭元素
 E getFirst();
 // 查看隊列尾元素
 E getLast();
 // 查看隊列頭元素
 E peekFirst();
 // 查看隊列尾元素
 E peekLast();
 // 從隊列頭向后遍歷移除指定元素
 boolean removeFirstOccurrence(Object o);
 // 從隊列尾向前遍歷移除指定元素
 boolean removeLastOccurrence(Object o);
// *** 隊列中的方法 ***
 // 添加元素，等于addLast(e)
 boolean add(E e);
 // 添加元素，等于offerLast(e)
 boolean offer(E e);
 // 移除元素，等于removeFirst()
 E remove();
 // 移除元素，等于pollFirst()
 E poll();
 // 查看元素，等于getFirst()
 E element();
 // 查看元素，等于peekFirst()
 E peek();
// *** 棧方法 ***
// 入棧，等于addFirst(e)
 void push(E e);
 // 出棧，等于removeFirst()
 E pop();
// *** Collection中的方法 ***
 // 刪除指定元素，等于removeFirstOccurrence(o)
 boolean remove(Object o);
 // 檢查是否包含某個元素
 boolean contains(Object o);
 // 元素個數(shù)
 public int size();
 // 迭代器
 Iterator<E> iterator();
 // 反向迭代器
 Iterator<E> descendingIterator();
}

// 存儲元素的數(shù)組
transient Object[] elements; // non-private to simplify nested class access
// 隊列頭位置
transient int head;
// 隊列尾位置
transient int tail;
// 最小初始容量
private static final int MIN_INITIAL_CAPACITY = 8;

// 默認(rèn)構(gòu)造方法，初始容量為16
public ArrayDeque() {
 elements = new Object[16];
}
// 指定元素個數(shù)初始化
public ArrayDeque(int numElements) {
 allocateElements(numElements);
}
// 將集合c中的元素初始化到數(shù)組中
public ArrayDeque(Collection<? extends E> c) {
 allocateElements(c.size());
 addAll(c);
}
// 初始化數(shù)組
private void allocateElements(int numElements) {
 elements = new Object[calculateSize(numElements)];
}
// 計算容量，這段代碼的邏輯是算出大于numElements的最接近的2的n次方且不小于8
// 比如，3算出來是8，9算出來是16，33算出來是64
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;
}

// 從隊列頭入隊
public void addFirst(E e) {
 // 不允許null元素
 if (e == null)
 throw new NullPointerException();
 // 將head指針減1并與數(shù)組長度減1取模
 // 這是為了防止數(shù)組到頭了邊界溢出
 // 如果到頭了就從尾再向前
 // 相當(dāng)于循環(huán)利用數(shù)組
 elements[head = (head - 1) & (elements.length - 1)] = e;
 // 如果頭尾挨在一起了，就擴(kuò)容
 // 擴(kuò)容規(guī)則也很簡單，直接兩倍
 if (head == tail)
 doubleCapacity();
}
// 從隊列尾入隊
public void addLast(E e) {
 // 不允許null元素
 if (e == null)
 throw new NullPointerException();
 // 在尾指針的位置放入元素
 // 可以看到tail指針指向的是隊列最后一個元素的下一個位置
 elements[tail] = e;
 // tail指針加1，如果到數(shù)組尾了就從頭開始
 if ( (tail = (tail + 1) & (elements.length - 1)) == head)
 doubleCapacity();
}

private void doubleCapacity() {
 assert head == tail;
 // 頭指針的位置
 int p = head;
 // 舊數(shù)組長度
 int n = elements.length;
 // 頭指針離數(shù)組尾的距離
 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");
 // 新建新數(shù)組
 Object[] a = new Object[newCapacity];
 // 將舊數(shù)組head之后的元素拷貝到新數(shù)組中
 System.arraycopy(elements, p, a, 0, r);
 // 將舊數(shù)組下標(biāo)0到head之間的元素拷貝到新數(shù)組中
 System.arraycopy(elements, 0, a, r, p);
 // 賦值為新數(shù)組
 elements = a;
 // head指向0，tail指向舊數(shù)組長度表示的位置
 head = 0;
 tail = n;
}

// 從隊列頭出隊
public E pollFirst() {
 int h = head;
 @SuppressWarnings("unchecked")
 // 取隊列頭元素
 E result = (E) elements[h];
 // 如果隊列為空，就返回null
 if (result == null)
 return null;
 // 將隊列頭置為空
 elements[h] = null; // Must null out slot
 // 隊列頭指針右移一位
 head = (h + 1) & (elements.length - 1);
 // 返回取得的元素
 return result;
}
// 從隊列尾出隊
public E pollLast() {
 // 尾指針左移一位
 int t = (tail - 1) & (elements.length - 1);
 @SuppressWarnings("unchecked")
 // 取當(dāng)前尾指針處元素
 E result = (E) elements[t];
 // 如果隊列為空返回null
 if (result == null)
 return null;
 // 將當(dāng)前尾指針處置為空
 elements[t] = null;
 // tail指向新的尾指針處
 tail = t;
 // 返回取得的元素
 return result;
}

public void push(E e) {
 addFirst(e);
}

public E pop() {
 return removeFirst();
}