public abstract class AbstractQueue<E>
    extends AbstractCollection<E>
    implements <E> {

    protected AbstractQueue() {
    }

	//add底层调用offer，当offer失败返回false时，add方法抛出异常
    public boolean add(E e) {
        if (offer(e))
            return true;
        else
            throw new IllegalStateException("Queue full");
    }
	//remove底层调用poll，当poll返回null时，remove方法抛出异常 
    public E remove() {
        E x = poll();
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }
	//element底层调用peek，当peek返回null时，element方法抛出异常
    public E element() {
        E x = peek();
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }
	//clear方法循环调用poll，直到返回为null
    public void clear() {
        while (poll() != null)
            ;
    }
	
    public boolean addAll(Collection<? extends E> c) {
        if (c == null)
            throw new NullPointerException();
        if (c == this)
            throw new IllegalArgumentException();
        boolean modified = false;
        for (E e : c)
            if (add(e))
                modified = true;
        return modified;
    }

}

// 第一个元素的索引  
private transient int head;  
// 下个要添加元素的位置，为末尾元素的索引 + 1  
private transient int tail;

//默认数组大小16
   public ArrayDeque() {
       elements = new Object[16];
   }
//传入数组大小
   public ArrayDeque(int numElements) {
//调整实际数组大小为大于传入值的最小的2的幂次
       allocateElements(numElements);
   }
//直接传入集合
   public ArrayDeque(Collection<? extends E> c) {
       allocateElements(c.size());
       addAll(c);
   }

   public void addFirst(E e) {
       if (e == null)
           throw new NullPointerException();
//因为elements.length是2的幂次，(head - 1) & (elements.length - 1)相当于求模操作
//head-1只可能为-1，-1&(elements.length - 1)=(elements.length - 1)
       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;
//与head操作类似，为了处理tail=length-1的情况
       if ( (tail = (tail + 1) & (elements.length - 1)) == head)
           doubleCapacity();
   }

   public boolean add(E e) {
       addLast(e);
       return true;
   }

   public boolean offerFirst(E e) {
       addFirst(e);
       return true;
   }

   public boolean offerLast(E e) {
       addLast(e);
       return true;
   }

   public E removeFirst() {
       E x = pollFirst();
       if (x == null)
           throw new NoSuchElementException();
       return x;
   }

   public E removeLast() {
       E x = pollLast();
       if (x == null)
           throw new NoSuchElementException();
       return x;
   }

   public E pollFirst() {
       int h = head;
       ("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下标，处理越界情况让head=0
       head = (h + 1) & (elements.length - 1);
       return result;
   }

   public E pollLast() {
//获取tail下标，处理tail=0的特殊情况，移除元素后tail=elements.length-1
       int t = (tail - 1) & (elements.length - 1);
       ("unchecked")
       E result = (E) elements[t];
       if (result == null)
           return null;
       elements[t] = null;
//tail指向下个要添加元素的索引
       tail = t;
       return result;
   }

   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;
//i前面的元素
       final int front = (i - h) & mask;
//i后面的元素
       final int back  = (t - i) & mask;

//i不在t和h之间
       if (front >= ((t - h) & mask))
           throw new ConcurrentModificationException();

       // Optimize for least element motion
       if (front < back) {
	// head X X i X X X X tail，head-i的元素大于i-tail元素个数
           if (h <= i) {
               System.arraycopy(elements, h, elements, h + 1, front);
           } else { // Wrap around
	// i X X X X tail X X head 
               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 {
	// head X X X X i X X tail
           if (i < t) { // Copy the null tail as well
               System.arraycopy(elements, i + 1, elements, i, back);
               tail = t - 1;
           } else { // Wrap around
	// tail X X head X X X X i
               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;
       }