由于前文《一文讲透LinkedList》对Deque的具体使用并未详写，因此在此处补上。前文已讲明Java 集合类的关系图，因此不在此再次说明。

介绍

Deque是java.util包中Queue接口的子类型，Deque是“双端队列”，支持从数据结构的任何一端添加或删除数据。它既可以用作队列（FIFO/先进先出），也可以用作栈（LIFO/后进先出）。

接口声明：

public interface Deque extends Queue {
    /**
     * 将指定的元素插入此双端队列的前面 ，空间不足抛异常
     */
    void addFirst(E e);

    /**
     * 将指定的元素插入此双端队列的后面 ，空间不足抛异常
     */
    void addLast(E e);

    /**
     * 将指定的元素插入此双端队列的前面 ，空间不足返回false
     */
    boolean offerFirst(E e);

    /**
     * 将指定的元素插入此双端队列的后面，空间不足返回false
     */
    boolean offerLast(E e);

    /**
     * 检索并删除第一个元素，deque为空时抛出异常
     */
    E removeFirst();

    /**
     * 检索并删除最后一个元素，deque为空时抛出异常
     */
    E removeLast();

    /**
     * 检索并删除第一个元素 ，deque为空时返回null
     */
    E pollFirst();

    /**
     * 检索并删除最后一个元素 ，deque为空时返回null
     */
    E pollLast();

    /**
     * 检索第一个元素 ，不从队列中删除，deque为空就抛异常
     */
    E getFirst();

    /**
     * 检索最后一个元素 ，不从队列中删除，deque为空就抛异常
     */
    E getLast();

    /**
     * 检索第一个元素 ，不从队列中删除，deque为空就则返回null
     */
    E peekFirst();

    /**
     * 检索最后一个元素 ，不从队列中删除，deque为空就则返回null
     */
    E peekLast();

    /**
     * 删除deque中第一个出现的元素，如果元素存在，则返回true
     */
    boolean removeFirstOccurrence(Object o);

    /**
     * 删除deque中最后一个出现的元素，如果元素存在，则返回true
     */
    boolean removeLastOccurrence(Object o);

    // *** 此部分为Queue接口的方法定义 ***

    /**
     * 将指定的元素插入此双端队列的后面，空间不足抛异常
     */
    boolean add(E e);

    /**
     * 将指定的元素插入此双端队列的后面，空间不足返回false
     */
    boolean offer(E e);

    /**
     * 和removeFirst一样 检索并删除第一个元素，为空时抛出异常
     */
    E remove();

    /**
     * 和pollFirst一样 检索并删除第一个元素 ，为空时返回null
     */
    E poll();

    /**
     * 和getFirst一样 只查看第一个元素 ，不从队列中删除，为空就抛异常
     */
    E element();

    /**
     * 和peekFirst一样 只查看第一个元素 ，不从队列中删除，为空时返回null
     */
    E peek();


    // *** 此部分为Stack接口的方法 ***

    /**
     * 将指定的元素插入此双端队列的前面 ，空间不足抛异常
     */
    void push(E e);

    /**
     * 和removeFirst一样，检索并删除第一个元素，为空时抛出异常
     */
    E pop();


    // *** 此部分为Collection接口的方法 ***

    /**
     * 和removeFirstOccurrence一样，删除deque中第一个出现的元素，
     * 如果元素存在，则返回true
     */
    boolean remove(Object o);

    /**
     * 如果deque中包含指定的元素，那么返回true，否则返回false
     */
    boolean contains(Object o);

    /**
     * 返回deque中的元素个数
     */
    public int size();

    /**
     * 按适当的顺序返回deque容器中所有元素的迭代器。
     * 元素将按照从头部到尾部的顺序返回。
     */
    Iterator iterator();

    /**
     * 返回一个迭代器，对deque容器中的元素按相反的顺序进行迭代。
     * 元素将按照从尾部到头部的顺序返回。
     */
    Iterator descendingIterator();

}

创建Deque对象

// 方式一：使用ArrayDeque创建
Deque deque = new ArrayDeque<>();

// 方式二：使用LinkedList创建
Deque deque = new LinkedList<>();

添加元素

要在双端队列中添加元素，我们可以使用add()方法。队列和双端队列的区别在于，在双端队列中，可以从两端进行添加元素。从头部添加元素的方法为：addFirst()，从尾部添加元素的方法为addLast() 。

Deque deque = new ArrayDeque<>();

deque.add(1); // 添加到尾部
deque.addFirst(2); // 添加到头部
deque.addLast(3); // 添加到尾部

System.out.println(deque); // 输出 [2, 1, 3]

移除元素

要在双端队列中移除元素，我们可以使用removeFirst()、removeLast()方法。除此之外，还可以使用 poll()、pop()、pollFirst()、pollLast() 方法。其中 pop() 用于移除和返回双端队列的头部。

注意：poll() 提供了与 pop() 相同的功能，区别在于 poll() 在双端队列为空时不会返回异常。

示例：

Deque deque = new ArrayDeque<>();

deque.add(1);
deque.addFirst(2);
deque.addLast(3);

System.out.println(deque);
System.out.println(deque.pop());
System.out.println(deque.poll());
System.out.println(deque.pollFirst());
System.out.println(deque.pollLast());

输出：
[2, 1, 3]
2
1
3
null

Deque遍历

Deque可以从两个方向进行遍历，如下：

Deque deque = new ArrayDeque<>();

deque.add(1);
deque.addFirst(2);
deque.addLast(3);

// 正向遍历，输出： 2 1 3 
Iterator iter = deque.iterator();
while (iter.hasNext()) {
    System.out.print(iter.next() + " ");
}

// 反向遍历，输出：3 1 2 
Iterator desIter = deque.descendingIterator();
while (desIter.hasNext()) {
    System.out.print(desIter.next() + " ");
}

常见问题

Q #1) Deque 是线程安全的吗？

答： ArrayDeque/LinkedList 不是线程安全的。但是 java.util.concurrent 包中的 BlockingDeque 是线程安全的。

Q #2)为什么 Deque 比 stack 快？

答：常用的 Deque 的 ArrayDeque 实现是内存高效的，它不需要跟踪前一个或下一个节点。此外，它是一个可调整大小的实现。因此双端队列比堆栈快。

Q #3) Deque 是堆栈吗？

答：Deque 是双端队列。它允许 LIFO（后进先出）行为，因此它可以作为一个堆栈来实现，但它不是一个堆栈。

Q #4) Deque 在哪里使用？

答：双端队列主要用于实现撤销和历史等功能。比如排队购票系统，对排队者的存储可以采用deque，支持头端的快速移除，尾端的快速添加。或者也可以使用deque实现一个浏览器的返回栈。

Q #5) ArrayDeque 和 LinkedList 比较

答：如果只需要Deque接口，只从两端进行元素操作，一般而言，ArrayDeque效率更高一些，应该被优先使用。不过，如果同时需要根据索引位置进行操作，或者经常需要在中间进行插入和删除，则应该选LinkedList（注意，这里使用的是List特性，而不是Deque特性了）。