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

 /**
  * 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;

 public void addFirst(E e) {
  if (e == null)
   throw new NullPointerException();
  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];
  System.arraycopy(elements, p, a, 0, r);
  System.arraycopy(elements, 0, a, r, p);
  elements = (E[])a;
  head = 0;
  tail = n;
 }

private boolean delete(int i) {
  checkInvariants();
  final E[] 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
  // 為了最小的拷貝數(shù)據(jù)
  if (front < back) {
   // 遞增的順序時
   if (h <= i) {
    // 刪除部分前面的向后移動
    System.arraycopy(elements, h, elements, h + 1, front);
   } else { // Wrap around
    // 跨越最小與最大值
    // 分兩次拷貝
    System.arraycopy(elements, 0, elements, 1, i);
    // 最大的地方單獨(dú)處理
    elements[0] = elements[mask];
    // 前面的部分向后移動一位
    System.arraycopy(elements, h, elements, h + 1, mask - h);
   }
   elements[h] = null;
   head = (h + 1) & mask;
   return false;
  } else {
   // 遞增的順序時
   if (i < t) { // Copy the null tail as well
    // 拷貝i后面的部分?jǐn)?shù)據(jù)前置
    System.arraycopy(elements, i + 1, elements, i, back);
    tail = t - 1;
   } else { // Wrap around
    // 跨越中間最大值的時候
    // 后面向前拷貝
    // 0處的值單獨(dú)處置放在最大的下標(biāo)處
    // 后面的部分從1開始向前移動一個，原來的1在0處
    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;
  }
 }

 public E pollFirst() {
  int h = head;
  E result = 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;
 }