Java Deque操作指南

大家好，欢迎来到IT知识分享网。

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

介绍

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

接口声明：

public interface Deque<E> extends Queue<E> { / * 将指定的元素插入此双端队列的前面 ，空间不足抛异常 */ 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<E> iterator(); / * 返回一个迭代器，对deque容器中的元素按相反的顺序进行迭代。 * 元素将按照从尾部到头部的顺序返回。 */ Iterator<E> descendingIterator(); }

创建Deque对象

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

添加元素

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

Deque<Integer> 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<Integer> 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<Integer> deque = new ArrayDeque<>(); deque.add(1); deque.addFirst(2); deque.addLast(3); // 正向遍历，输出： 2 1 3 Iterator<Integer> iter = deque.iterator(); while (iter.hasNext()) { System.out.print(iter.next() + " "); } // 反向遍历，输出：3 1 2 Iterator<Integer> 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特性了）。