1.双端队列介绍
在介绍双端队列之前，我们需要先介绍队列的概念。和栈相对应，在许多算法设计中，需要一种"先进先出(First Input First Output)"的数据结构，因而一种被称为"队列(Queue)"的数据结构被抽象了出来(因为现实中的队列,就是先进先出的)。
队列是一种线性表，将线性表的一端作为队列的头部，而另一端作为队列的尾部。队列元素从尾部入队，从头部出队(尾进头出，先进先出)。
双端队列(Double end Queue)是一种特殊的队列结构，和普通队列不同的是，双端队列的线性表两端都可以进行出队和入队操作。当只允许使用一端进行出队、入队操作时，双端队列等价于一个栈；当限制一端只能出队，另一端只能入队时，双端队列等价于一个普通队列。
简洁起见，下述内容的"队列"默认代表的就是"双端队列"。
2.双端队列ADT接口
/** * 双端队列 ADT接口 * */public interface Deque<E>{ /** * 头部元素插入 * */ void addHead(E e); /** * 尾部元素插入 * */ void addTail(E e); /** * 头部元素删除 * */ E removeHead(); /** * 尾部元素删除 * */ E removeTail(); /** * 窥视头部元素(不删除) * */ E peekHead(); /** * 窥视尾部元素(不删除) * */ E peekTail(); /** * @return 返回当前队列中元素的个数 */ int size(); /** * 判断当前队列是否为空 * @return 如果当前队列中元素个数为0，返回true；否则，返回false */ boolean isEmpty(); /** * 清除队列中所有元素 * */ void clear(); /** * 获得迭代器 * */ Iterator<E> iterator(); }
3.双端队列实现细节
3.1 双端队列基于数组的实现（ArrayDeque）
双端队列作为一个线性表，一开始也许会考虑能否像栈一样，使用向量作为双端队列的底层实现。
但是仔细思考就会发现：在向量中，头部元素的插入、删除会导致内部元素的整体批量的移动，效率很差。而队列具有"先进先出"的特性，对于频繁入队，出队的队列容器来说，O(n)时间复杂度的单位操作效率是无法容忍的。因此我们必须更进一步，从更为基础的数组结构出发，实现我们的双端队列。
3.1.1 数组双端队列实现思路：
在进行代码细节的展开之前，让我们先来理解以下基本思路：
1.和向量一样，双端队列在内部数组容量不足时，能和向量一样动态的扩容。
2.双端队列内部维护着"头部下标"、"尾部下标"。头部下标指向的是队列中第一位元素，尾部下标指向的是下一个尾部元素插入的位置。
从头部下标起始，到尾部下标截止(左闭右开区间)，连续保存着队列中的全部元素。在元素出队，入队时，通过移动头尾下标，进行队列中元素的插入、删除，从而避免了类似向量中大量内部元素的整体移动。
当头部元素入队时，头部下标向左移动一位；头部元素出队时，头部下标向右移动一位。
当尾部元素入队时，尾部下标向右移动一位；尾部元素出队时，尾部下标向左移动一位。
3.当元素下标的移动达到了边界时，需要将数组从逻辑上看成一个环，其头尾是相邻的：
下标从数组第0位时，向左移动一位，会跳转到数组的最后一位。
下标从数组最后一位时，向右移动一位，会跳转到数组的第0位。
下标越界时的跳转操作，在细节上是通过下标取模实现的。
3.1.2 队列的基本属性：
只有当队列为空时，头部节点和尾部节点的下标才会相等。
/** * 基于数组的 双端队列 * */
