public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable
transient Object[] elements;
transient int head;
transient int tail;
-------、
public interface Deque<E> extends Queue<E> {
从定义可以看出，ArrayDeque类，实现了 Deque接口，而Deque继承了Queue(队列）接口；
而Queue接口，有以下功能：
boolean add(E e)
boolean offer(E e)
E remove();
E poll();
E element();
E peek();
Deque接口，定义了以下方法：
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)
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
-----------
boolean addAll(Collection<? extends E> c);
void push(E e);
E pop();
-----------
boolean remove(Object o);
boolean contains(Object o);
int size();
Iterator<E> iterator();
Iterator<E> descendingIterator();
从源码来看，ArrayDeque采用了类似与双指针的双端队列结构，
其中Deque可以分为Queue 和 Stack相对应的接口；
上面两个表共定义了Deque的12个接口。添加，删除，取值都有两套接口，它们功能相同，区别是对失败情况的处理不同。一套接口遇到失败就会抛出异常，另一套遇到失败会返回特殊值（false或null）。除非某种实现对容量有限制，大多数情况下，添加操作是不会失败的。虽然Deque的接口有12个之多，但无非就是对容器的两端进行操作，或添加，或删除，或查看。明白了这一点讲解起来就会非常简单。
ArrayDeque和LinkedList是Deque的两个通用实现，由于官方更推荐使用AarryDeque用作栈和队列，加之上一篇已经讲解过LinkedList，本文将着重讲解ArrayDeque的具体实现。
从名字可以看出ArrayDeque底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组（circular array），也就是说数组的任何一点都可能被看作起点或者终点。ArrayDeque是非线程安全的（not thread-safe），当多个线程同时使用的时候，需要程序员手动同步；另外，该容器不允许放入null元素。
摘抄自大神
由于底层为 circular array,故其 head 和 tail 在数值上大小不一定，head代表头部的第一个有效元素，tail代表尾部可以插入的位置；
其示意图如下：
方法剖析
1、addLast()方法
像队尾增加元素（tail）,
public void addLast(E e) {
if (e == null) //队列中不允许放入null
throw new NullPointerException();
final Object[] es = elements; //新建了一个新的数组，来引用原数组
es[tail] = e; // 先插入，在判断是否进行扩容
if (head == (tail = inc(tail, es.length))) //若列表已满,则进行扩容
grow(1);
}
static final int inc(int i, int modulus) {
if (++i >= modulus) i = 0;
//判断队尾是否已经在数组的尾部,若在则tail下一步为0
return i;
}
此时，tail的下一个空位为 tail+1
此时，tail的下一个空位为 0
2、addFirst() 方法
此时情况与addLast相似，只需江 tail+1 改为head-1 即可；
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
final Object[] es = elements;
es[head = dec(head, es.length)] = e; // 先插入，在判断是否进行扩容
if (head == tail)
grow(1);
}
static final int dec(int i, int modulus) {
if (--i < 0) i = modulus - 1;
return i;
}
上述代码我们看到，空间问题是在插入之后解决的，因为tail总是指向下一个可插入的空位，也就意味着elements数组至少有一个空位，所以插入元素的时候不用考虑空间问题。
扩容的方法：
private void grow(int needed) {
// overflow-conscious code
final int oldCapacity = elements.length;
int newCapacity;
// Double capacity if small; else grow by 50%
int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
// 判断原数组长度
if (jump < needed
|| (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
newCapacity = newCapacity(needed, jump);
final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
// Exceptionally, here tail == head needs to be disambiguated
if (tail < head || (tail == head && es[head] != null)) {
// wrap around; slide first leg forward to end of array
int newSpace = newCapacity - oldCapacity;
System.arraycopy(es, head,
es, head + newSpace,
oldCapacity - head);
for (int i = head, to = (head += newSpace); i < to; i++)
es[i] = null;
}
}
private int newCapacity(int needed, int jump) {
final int oldCapacity = elements.length, minCapacity;
if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
if (minCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
return Integer.MAX_VALUE;
}
if (needed > jump)
return minCapacity;
return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)
? oldCapacity + jump
: MAX_ARRAY_SIZE;
}
扩容分区间进行扩容，在不超过最大限度情况下，若源列表的长度小于64，则扩容为2倍，否则为1.5倍；
扩容完后，要将原有元素复制到新的队列中去；
3、pollFirst() 方法
public E pollFirst() {
final Object[] es;
final int h;
E e = elementAt(es = elements, h = head);
if (e != null) {
es[h] = null;
head = inc(h, es.length);
}
return e;
}
static final <E> E elementAt(Object[] es, int i) {
return (E) es[i];
}
pollFirst()的作用是删除并返回Deque首端元素，也即是head位置处的元素。如果容器不空，只需要直接返回elements[head]即可，当然还需要处理下标的问题。由于ArrayDeque中不允许放入null，当elements[head] == null时，意味着容器为空。
4、 pollLast()方法
public E pollLast() {
final Object[] es;
final int t;
E e = elementAt(es = elements, t = dec(tail, es.length));
if (e != null)
es[tail = t] = null;
return e;
}
pollLast()的作用是删除并返回Deque尾端元素，也即是tail位置前面的那个元素。
5、peekFirst() 和peekLast()
只返回，首端元素，并不删除元素；
