Java Deque 使用教程：双端队列的核心概念与最佳实践 – wiki基地

---

Java Deque 使用教程：双端队列的核心概念与最佳实践

在 Java 集合框架中，Deque（Double-Ended Queue，双端队列）是一个非常强大且灵活的接口。它结合了队列（Queue）和栈（Stack）的特性，允许在两端进行元素的插入和删除。本文将深入探讨 Deque 的核心概念、主要实现类、常用操作以及在实际开发中的最佳实践。

1. 什么是 Deque？

Deque 是 java.util 包下的一个接口，它继承自 Queue 接口。顾名思义，双端队列是一种支持在两端（头部和尾部）进行元素添加和移除的线性集合。这意味着你可以像使用队列一样从一端添加元素、从另一端移除元素（先进先出，FIFO），也可以像使用栈一样从同一端添加和移除元素（后进先出，LIFO）。

Deque 与 Queue / Stack 的关系：

• Queue (队列)：通常只允许在队尾插入元素（offer/add），在队头移除元素（poll/remove）。Deque 扩展了 Queue，提供了更灵活的两端操作。
• Stack (栈)：遵循 LIFO（后进先出）原则，通常只允许在栈顶进行元素的插入（push）和移除（pop）。虽然 Stack 类在 Java 早期版本中存在，但 Deque 接口提供了更完整、更高效的栈实现（尤其是 ArrayDeque），因此官方推荐使用 Deque 作为栈的替代品。

2. Deque 的主要实现类

Java 提供了 Deque 接口的两个主要实现类：

2.1 ArrayDeque

• 底层实现：基于可变数组实现。
• 特性：非线程安全，但在单线程环境下性能优异，因为它避免了 LinkedList 中节点对象创建的开销。
• 适用场景：作为栈或队列的快速、高效的替代品。当需要一个容量可自动调整且不需要线程安全保证的双端队列时，ArrayDeque 是首选。

2.2 LinkedList

• 底层实现：基于双向链表实现。
• 特性：非线程安全。
• 适用场景：当频繁地在队列中间进行插入或删除操作时，LinkedList 可能表现更好，因为链表结构使得这些操作的开销相对较小。然而，对于纯粹的两端操作，ArrayDeque 通常更优。

3. Deque 的核心操作

Deque 接口定义了一系列方法，这些方法分为三组，每组都有三种行为方式（抛出异常、返回特殊值、阻塞）：

• 抛出异常：操作失败时抛出异常。
• 返回特殊值：操作失败时返回 null 或 false。
• 阻塞：在并发编程中，如果队列满或空，操作会被阻塞直到可以执行。Deque 接口本身没有阻塞方法，但其子接口 BlockingDeque 提供了。

下表总结了 Deque 的主要操作及其行为：

操作类型	抛出异常 (Exception)	返回特殊值 (Special Value)	描述
插入	addFirst(e)	offerFirst(e)	在头部插入元素。
	addLast(e)	offerLast(e)	在尾部插入元素。
	add(e)	offer(e)	行为同 addLast(e) / offerLast(e)。
移除	removeFirst()	pollFirst()	移除并返回头部元素。
	removeLast()	pollLast()	移除并返回尾部元素。
	remove()	poll()	行为同 removeFirst() / pollFirst()。
检查	getFirst()	peekFirst()	返回头部元素但不移除。
	getLast()	peekLast()	返回尾部元素但不移除。
	element()	peek()	行为同 getFirst() / peekFirst()。
栈操作	push(e)		在头部插入元素（等同于 addFirst(e)）。
	pop()		移除并返回头部元素（等同于 removeFirst()）。

重要提示：
* 当你将 Deque 用作队列时，通常使用 offer(), poll(), peek() 方法，它们更健壮，不会抛出异常。
* 当你将 Deque 用作栈时，使用 push(), pop(), peek() 方法。

4. Deque 的使用示例

4.1 作为队列 (FIFO)

“`java
import java.util.ArrayDeque;
import java.util.Deque;

public class DequeAsQueue {
public static void main(String[] args) {
Deque queue = new ArrayDeque<>();

    // 插入元素到队尾
    queue.offer("Apple");
    queue.offer("Banana");
    queue.offer("Cherry");

    System.out.println("Queue: " + queue); // Output: Queue: [Apple, Banana, Cherry]

    // 检查队头元素
    String firstElement = queue.peek();
    System.out.println("First element (peek): " + firstElement); // Output: First element (peek): Apple
    System.out.println("Queue after peek: " + queue); // Output: Queue after peek: [Apple, Banana, Cherry]

    // 移除队头元素
    String removedElement = queue.poll();
    System.out.println("Removed element (poll): " + removedElement); // Output: Removed element (poll): Apple
    System.out.println("Queue after poll: " + queue); // Output: Queue after poll: [Banana, Cherry]

    // 再次移除
    System.out.println("Removed: " + queue.poll()); // Output: Removed: Banana
    System.out.println("Queue: " + queue); // Output: Queue: [Cherry]
}

}
“`

4.2 作为栈 (LIFO)

“`java
import java.util.ArrayDeque;
import java.util.Deque;

public class DequeAsStack {
public static void main(String[] args) {
Deque stack = new ArrayDeque<>();

    // 压入元素到栈顶 (头部)
    stack.push(10);
    stack.push(20);
    stack.push(30);

    System.out.println("Stack: " + stack); // Output: Stack: [30, 20, 10] (注意 ArrayDeque 的字符串表示，栈顶在左边)

    // 查看栈顶元素
    Integer topElement = stack.peek();
    System.out.println("Top element (peek): " + topElement); // Output: Top element (peek): 30
    System.out.println("Stack after peek: " + stack); // Output: Stack after peek: [30, 20, 10]

    // 弹出栈顶元素
    Integer poppedElement = stack.pop();
    System.out.println("Popped element: " + poppedElement); // Output: Popped element: 30
    System.out.println("Stack after pop: " + stack); // Output: Stack after pop: [20, 10]

    // 再次弹出
    System.out.println("Popped: " + stack.pop()); // Output: Popped: 20
    System.out.println("Stack: " + stack); // Output: Stack: [10]
}

}
“`

4.3 双端操作

“`java
import java.util.ArrayDeque;
import java.util.Deque;

public class DequeDoubleEnded {
public static void main(String[] args) {
Deque deque = new ArrayDeque<>();

    // 头部插入
    deque.addFirst('B'); // deque: [B]
    deque.addFirst('A'); // deque: [A, B]

    // 尾部插入
    deque.addLast('C');  // deque: [A, B, C]
    deque.addLast('D');  // deque: [A, B, C, D]

    System.out.println("Deque: " + deque); // Output: Deque: [A, B, C, D]

    // 移除头部
    System.out.println("Removed First: " + deque.removeFirst()); // Output: Removed First: A
    System.out.println("Deque: " + deque); // Output: Deque: [B, C, D]

    // 移除尾部
    System.out.println("Removed Last: " + deque.removeLast());  // Output: Removed Last: D
    System.out.println("Deque: " + deque); // Output: Deque: [B, C]
}

}
“`

5. Deque 的最佳实践

5.1 选择合适的实现类

• 优先使用 ArrayDeque：在大多数不需要线程安全的场景下，ArrayDeque 由于其底层数组实现，通常比 LinkedList 提供更好的性能（尤其是在元素数量较多时，减少了对象创建和垃圾回收的开销）。它是一个优秀的通用队列和栈实现。
• 何时考虑 LinkedList：只有当你的应用需要频繁地在队列的中间进行插入或删除操作时，或者当你需要一个双向链表本身的功能时，才考虑使用 LinkedList。对于纯粹的两端操作，ArrayDeque 仍然是更优选择。
• 线程安全：ArrayDeque 和 LinkedList 都不是线程安全的。如果在多线程环境中使用，你需要手动进行同步（例如使用 Collections.synchronizedDeque() 包装），或者使用 java.util.concurrent 包中的并发双端队列实现，如 ConcurrentLinkedDeque 或 LinkedBlockingDeque。

5.2 规范化操作方法

• 避免混合使用：为了代码清晰和可读性，当将 Deque 用作队列时，坚持使用 offer/poll/peek 系列方法。当用作栈时，坚持使用 push/pop/peek。避免混用如 addFirst 和 push（尽管它们功能相同）。
• 处理 null 返回值：offer, poll, peek 方法在操作失败时会返回 false 或 null。在你的代码中务必检查这些返回值，以避免 NullPointerException 或逻辑错误。
• 容量限制：ArrayDeque 是一个动态数组，没有固定容量限制（理论上只受限于内存）。LinkedList 也没有固定容量。如果需要有容量限制的双端队列，应考虑 BlockingDeque 及其实现类。

5.3 常见应用场景

• 实现栈：解析器、表达式求值、浏览器历史记录、撤销/重做功能等。
• 实现队列：任务调度、广度优先搜索（BFS）中的待访问节点列表。
• 实现双端队列本身：需要灵活地从两端添加/移除元素的场景，例如：
  • 滑动窗口算法：在固定大小的窗口中维护最大/最小值时，可以利用 Deque 存储窗口内的元素，并在窗口滑动时高效地进行添加和移除。
  • 任务窃取（Work Stealing）：在某些并发框架中，工作线程可以从自己的双端队列头部取出任务，当自己的队列为空时，可以从其他线程的队列尾部“窃取”任务。

5.4 性能考量

• ArrayDeque 的优势：在大多数场景下，ArrayDeque 的性能优于 LinkedList，因为它避免了链表节点对象的开销，并且在内部数组扩容时，通常会有分摊常数时间的性能。
• 内存使用：ArrayDeque 可能在扩容时占用更多内存，但其内部实现通常能有效利用内存。LinkedList 的每个元素都需要额外的内存来存储前后节点的引用。
• 迭代：Deque 支持迭代器。对于 ArrayDeque，迭代通常更快，因为它直接遍历数组。

总结

Deque 接口是 Java 集合框架中一个非常实用的工具，它提供了队列和栈的灵活功能，使得开发者可以根据具体需求选择最合适的数据结构。理解 ArrayDeque 和 LinkedList 之间的区别，并遵循最佳实践，将帮助你编写出更高效、更健壮的 Java 代码。在多数情况下，将 ArrayDeque 作为栈或队列的首选实现，并根据其 offer/poll/peek 或 push/pop 方法进行规范化操作，是 Java 开发中的推荐做法。

---