双端队列（Deque），顾名思义是可以在队列的两端插入和移除元素的特殊队列。
Java提供了java.util.Deque<E>接口以提供对双端队列的支持。该接口是Java Collections Framework的一个成员。
1. Deque的方法
这个java.util.Deque<E>接口接口定义了访问Deque两端元素的方法，包括插入、删除和检查元素的方法。这些方法都以两种形式存在：
l 一种是如果操作失败则抛出异常；
l 另一种是返回一个特殊值（根据操作的不同返回null或false）。
后一种形式的插入操作是专门为容量受限的Deque实现而设计的。在大多数实现中，插入操作不会失败。
这些方法总结如下：
Deque方法总结
| 队首 |
队尾 |
|||
| 抛异常 |
特殊值 |
抛异常 |
特殊值 |
|
| 插入 |
addFirst(e) |
offerFirst(e) |
addLast(e) |
offerLast(e) |
| 移除 |
removeFirst() |
pollFirst() |
removeLast() |
pollLast() |
| 检查 |
getFirst() |
peekFirst() |
getLast() |
peekLast() |
2. Deque用作队列
Deque扩展了Queue接口。这意味着，当Deque作为队列使用时，拥有FIFO行为的结果。元素添加在Deque的末尾，并从队首处删除。从Queue接口继承的方法与Deque方法完全等效，如下表所示：
Queue和Deque方法的比较
| Queue |
Deque |
| add(e) |
addLast(e) |
| offer(e) |
offerLast(e) |
| remove() |
removeFirst() |
| poll() |
pollFirst() |
| element() |
getFirst() |
| peek() |
peekFirst() |
3. Deque用作栈
Deque也可以用作LIFO的栈。这个接口应该优先于旧版的Stack类使用。当一个Deque作为栈使用时，元素从Deque开始被推入并弹出。堆栈方法与Deque方法等效，如下表所示：
Stack和Deque方法的比较
| Stack |
Deque |
| push(e) |
addFirst(e) |
| pop() |
removeFirst() |
| peek() |
getFirst() |
请注意，当一个Deque用作一个队列或堆栈时，peek()方法同样有效。在这两种情况下，元素都是从Deque的队首开始的。
Deque接口提供了两种方法来移除内部元素，即removeFirstOccurrence和removeLastOccurrence。与List接口不同，此Deque不提供对元素的索引访问支持。
尽管Deque实现不是严格要求禁止插入空元素，但是强烈建议任何允许空元素的Deque实现的用户不要利用插入空元素的能力。这是因为null被各种方法用作一个特殊的返回值来指示Deque为空。
Deque实现通常不定义equals和hashCode方法的基于元素的版本，而是从类Object继承基于标识的版本。
4. 参考引用
本系列归档至《Java 数据结构及算法实战》：https://github.com/waylau/java-data-structures-and-algorithms-in-action
《数据结构和算法基础（Java 语言实现）》（柳伟卫著，北京大学出版社出版）：https://item.jd.com/13014179.html
