一、队列
队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
二、双端队列
双端队列是只既可以在表的前端进行插入和删除操作，又可以在表的后端进行插入和删除操作。
三、ArrayDeque的实现
Java中的双端队列是用数组实现的，类的全限名称是java.util.ArrayDeque，该类的声明如下：
public class ArrayDeque<E> extends AbstractCollection<E>implements Deque<E>, Cloneable, Serializable{}该类继承了AbstractCollection类，实现了Deque、Cloneable和Serializable接口。实现Cloneable和Serializable接口的主要目的是为了实现克隆和序列化。
该类中定义了四个个成员变量
public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable { private transient E[] elements; private transient int head; private transient int tail; private static final int MIN_INITIAL_CAPACITY = 8; }其中elements是数组的首地址，head是指向队首的下标，tail是指向队尾的下一个位置的下标。MIN_INITIAL_CAPACITY 定义了在创建队列是，如果有指定长度，而且指定长度小于MIN_INITIAL_CAPACITY，则使用MIN_INITIAL_CAPACITY 作为数组的最小长度。
其构造函数有一下几种：
public ArrayDeque() { elements = (E[]) new Object[16]; }第一种构造函数，默认情况下，数组的长度为16。
public ArrayDeque(int numElements) { allocateElements(numElements); }第二种构造函数，给定数组长度，则调用allocateElements()函数，分配数组空间。allocateElements()函数的实现如下：
private void allocateElements(int numElements) { int initialCapacity = MIN_INITIAL_CAPACITY; 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 } elements = (E[]) new Object[initialCapacity]; }对于一个给定长度，先判断是否小于定义的最小长度，如果小于，则使用定义的最小长度作为数组的长度。否则，找到比给定长度大的最小的2的幂数（在if里面的以为语句实现这一功能）。
public ArrayDeque(Collection<? extends E> c) { allocateElements(c.size()); addAll(c); }第三种构造函数，给定一个集合，先分配空间，然后添加到集合中。
从上面的三种构造函数中，可以判断出来，数组的长度是2的幂数，定义为2的幂数个人认为有两个原因：
1.伙伴系统
操作系统分配内存的方法使用伙伴系统的话，每一块的大小都是2的幂数，如果分配的内存大小为2的幂数，可以减少内存分配的时间。
伙伴系统在百度百科中的解释：http://baike.baidu.com/view/4935190.htm
2.插入和删除的速度
对于数组，如果head的值为0,时，在队首插入元素，有一种方法是将全部元素都向后移动一位，然后将新的元素插入。这样子的话，插入和删除的速度会非常慢，特别是在元素很多的情况下。另一种方法就是在head的值为0时，在队首插入元素，可以将head的值置为（数组的长度-1）。也就是将新插入的元素放到数组的最后，以此类推。在计算插入元素位置下标的时候，数组长度是2的幂数就用处了。下面是插入元素时，计算插入位置的值的语句
head = (head - 1) & (elements.length - 1)length-1的值为高位全为0，低位全为1，通过按位相与，可以得出应该插入元素的位置。
然后就是该类的一些方法了，有点面向对象的思想的都应该会想到，应该有头插，头删，尾插，尾删等等一些操作，在此就不一一列出了，实现起来也比较简单。关键还是要了解ArrayDeque的实现机制。
