Java双端队列(Deque)完全攻略：从入门到精通 – wiki基地

作者： /

Java双端队列 (Deque) 完全攻略：从入门到精通

1. 引言：什么是双端队列 (Deque)？

在Java中，队列（Queue）是一种先进先出（FIFO）的数据结构，栈（Stack）是一种后进先出（LIFO）的数据结构。然而，在实际编程中，我们常常需要一种更为灵活的数据结构，它既能像队列一样在队尾添加和在队头移除元素，又能像栈一样在队头添加和移除元素。这时，双端队列（Double-Ended Queue），简称 Deque，就应运而生了。

Deque 是 “Double-Ended Queue” 的缩写，它允许我们在队列的两端（头部和尾部）进行元素的添加和移除操作。这使得 Deque 能够非常方便地模拟队列和栈的行为，同时提供了比单独的 Queue 或 Stack 接口更丰富的操作。

为什么使用 Deque？

  • 灵活性： 支持从两端进行添加和移除，兼具队列和栈的功能。
  • 统一接口： 提供了一套统一且语义清晰的方法来操作数据结构。
  • 性能： Java提供的 Deque 实现（如 ArrayDeque）通常比传统的 Stack 类（它继承自 Vector，带有同步开销）在性能上更优。

在 Java 中，Deque 是 java.util 包下的一个接口，它继承自 Queue 接口。

2. Deque 接口的核心方法

Deque 接口提供了两套操作方法：一套在操作失败时抛出异常，另一套返回特殊值（如 null 或 false）。这与 Queue 接口的设计哲学保持一致。

操作类型 抛出异常 (Queue) 返回特殊值 (Queue) 抛出异常 (Deque) 返回特殊值 (Deque) 栈操作 (Deque) 描述
添加元素 add(e) offer(e) addFirst(e) offerFirst(e) push(e) 在头部添加元素
addLast(e) offerLast(e) 在尾部添加元素
移除元素 remove() poll() removeFirst() pollFirst() pop() 移除并返回头部元素
removeLast() pollLast() 移除并返回尾部元素
检查元素 element() peek() getFirst() peekFirst() peek() 返回头部元素但不移除
getLast() peekLast() 返回尾部元素但不移除
其他 removeFirstOccurrence(o) 移除第一次出现的指定元素（从头到尾查找）
removeLastOccurrence(o) 移除最后一次出现的指定元素（从尾到头查找）

方法详解：

  • 添加元素:
    • addFirst(e) / offerFirst(e): 在双端队列的头部插入元素。addFirst 在容量受限时可能抛出 IllegalStateException，offerFirst 则返回 false。
    • addLast(e) / offerLast(e): 在双端队列的尾部插入元素。addLast 在容量受限时可能抛出 IllegalStateException，offerLast 则返回 false。
    • push(e): 行为与 addFirst(e) 相同，用于模拟栈的入栈操作。
  • 移除元素:
    • removeFirst() / pollFirst(): 移除并返回双端队列头部的元素。removeFirst 在队列为空时抛出 NoSuchElementException，pollFirst 则返回 null。
    • removeLast() / pollLast(): 移除并返回双端队列尾部的元素。removeLast 在队列为空时抛出 NoSuchElementException，pollLast 则返回 null。
    • pop(): 行为与 removeFirst() 相同，用于模拟栈的出栈操作。
  • 检查元素:
    • getFirst() / peekFirst(): 返回双端队列头部的元素，但不移除。getFirst 在队列为空时抛出 NoSuchElementException，peekFirst 则返回 null。
    • getLast() / peekLast(): 返回双端队列尾部的元素，但不移除。getLast 在队列为空时抛出 NoSuchElementException，peekLast 则返回 null。
    • peek(): 行为与 peekFirst() 相同，用于模拟栈的查看栈顶元素操作。

3. Deque 的主要实现类

Java 提供了 Deque 接口的两种常用实现：ArrayDeque 和 LinkedList。

3.1 ArrayDeque

ArrayDeque 是 Deque 接口基于可变数组的实现。它没有容量限制（除非内存耗尽），并且在两端操作时都具有 O(1) 的平均时间复杂度。

特点：

  • 底层实现： 动态调整大小的数组。
  • 性能： 在头部和尾部添加/移除元素均摊 O(1) 时间复杂度。随机访问元素 O(n)。
  • 线程安全性： 非线程安全。如果需要在多线程环境中使用，需要外部同步或使用 ConcurrentLinkedDeque。
  • Null 值： 不允许存储 null 元素。
  • 内存效率： 通常比 LinkedList 更节省内存，因为它不需要为每个元素存储额外的链表节点信息。
  • 用途： 适合用作栈和队列的替代品，特别是当对内存和性能有较高要求时。

示例：作为栈使用

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

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

    // 入栈
    stack.push("Apple");
    stack.push("Banana");
    stack.push("Cherry");
    System.out.println("Stack after pushes: " + stack); // [Cherry, Banana, Apple] (头部是栈顶)

    // 查看栈顶元素
    String topElement = stack.peek();
    System.out.println("Top element: " + topElement); // Cherry
    System.out.println("Stack after peek: " + stack); // [Cherry, Banana, Apple]

    // 出栈
    String poppedElement = stack.pop();
    System.out.println("Popped element: " + poppedElement); // Cherry
    System.out.println("Stack after pop: " + stack); // [Banana, Apple]

    stack.pop();
    stack.pop();
    // 尝试从空栈出栈，会抛出 NoSuchElementException
    // stack.pop();
}

}
“`

示例：作为队列使用

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

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

    // 入队 (尾部添加)
    queue.offer("Task 1");
    queue.offer("Task 2");
    queue.offer("Task 3");
    System.out.println("Queue after offers: " + queue); // [Task 1, Task 2, Task 3] (头部是队头)

    // 查看队头元素
    String headElement = queue.peek();
    System.out.println("Head element: " + headElement); // Task 1
    System.out.println("Queue after peek: " + queue); // [Task 1, Task 2, Task 3]

    // 出队 (头部移除)
    String dequeuedElement = queue.poll();
    System.out.println("Dequeued element: " + dequeuedElement); // Task 1
    System.out.println("Queue after poll: " + queue); // [Task 2, Task 3]

    queue.poll();
    queue.poll();
    // 尝试从空队列出队，返回 null
    String emptyPoll = queue.poll();
    System.out.println("Poll from empty queue: " + emptyPoll); // null
}

}
“`

3.2 LinkedList

LinkedList 是 List 接口和 Deque 接口的一个实现。它通过双向链表实现，因此在两端操作元素非常高效，但在中间插入或删除元素需要遍历链表。

特点：

  • 底层实现： 双向链表。
  • 性能： 在头部和尾部添加/移除元素均为 O(1) 时间复杂度。随机访问元素 O(n)。
  • 线程安全性： 非线程安全。
  • Null 值： 允许存储 null 元素。
  • 内存效率： 每个元素都包含数据以及指向前一个和后一个节点的引用，因此比 ArrayDeque 占用更多内存。
  • 用途： 当需要频繁在队列中间进行插入或删除操作时，或者允许存储 null 值时，LinkedList 可能更适用。

示例：作为双端队列使用

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

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

    // 头部添加
    deque.addFirst(10); // deque: [10]
    deque.offerFirst(5);  // deque: [5, 10]

    // 尾部添加
    deque.addLast(20);  // deque: [5, 10, 20]
    deque.offerLast(25); // deque: [5, 10, 20, 25]
    System.out.println("Deque after adding elements: " + deque);

    // 头部检查
    System.out.println("First element (peek): " + deque.peekFirst()); // 5
    System.out.println("First element (get): " + deque.getFirst());   // 5

    // 尾部检查
    System.out.println("Last element (peek): " + deque.peekLast());   // 25
    System.out.println("Last element (get): " + deque.getLast());     // 25

    // 头部移除
    System.out.println("Removed first (poll): " + deque.pollFirst()); // 5, deque: [10, 20, 25]

    // 尾部移除
    System.out.println("Removed last (remove): " + deque.removeLast()); // 25, deque: [10, 20]

    System.out.println("Deque after removals: " + deque); // [10, 20]
}

}
“`

4. 典型使用场景

Deque 的灵活性使其在多种算法和数据结构实现中非常有用。

4.1 模拟栈

Deque 是 java.util.Stack 类的推荐替代品。Stack 是基于 Vector 实现的，Vector 是同步的，这在单线程环境下会带来不必要的开销。使用 ArrayDeque 作为栈，可以获得更好的性能。

java
// 使用 Deque 模拟栈
Deque<String> myStack = new ArrayDeque<>();
myStack.push("A");
myStack.push("B");
myStack.pop(); // B

4.2 模拟队列

Deque 也可以完美地模拟标准队列。

java
// 使用 Deque 模拟队列
Deque<String> myQueue = new ArrayDeque<>();
myQueue.offer("First");
myQueue.offer("Second");
myQueue.poll(); // First

4.3 回文检查器

判断一个字符串或列表是否是回文（正读反读都一样）是 Deque 的经典应用。

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

public class PalindromeChecker {
public static boolean isPalindrome(String s) {
Deque deque = new ArrayDeque<>();
for (char c : s.toCharArray()) {
deque.addLast(c); // 将字符依次添加到双端队列的尾部
}

    while (deque.size() > 1) {
        if (deque.removeFirst() != deque.removeLast()) { // 同时从两端移除并比较
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    System.out.println("'madam' is palindrome: " + isPalindrome("madam")); // true
    System.out.println("'hello' is palindrome: " + isPalindrome("hello")); // false
    System.out.println("'level' is palindrome: " + isPalindrome("level")); // true
}

}
“`

4.4 滑动窗口最大值/最小值问题

在一些算法问题中，例如寻找滑动窗口中的最大值或最小值，Deque 可以用来维护一个单调队列，从而将 O(N*K) 的时间复杂度优化到 O(N)。这通常涉及到在窗口滑动时，从头部移除过期的元素，并从尾部添加新元素，同时保持队列的单调性。

5. 线程安全性

ArrayDeque 和 LinkedList 都是非线程安全的。如果在多线程环境中使用，需要额外的同步机制。

  • 外部同步： 可以使用 Collections.synchronizedDeque() 方法来获得一个线程安全的 Deque 包装器。
    java
    Deque<String> deque = Collections.synchronizedDeque(new ArrayDeque<>());
  • 并发实现： Java 提供了 ConcurrentLinkedDeque 类，它是 Deque 接口的一个线程安全实现，基于链表。在需要高并发性能时，ConcurrentLinkedDeque 通常是更好的选择，因为它避免了整个队列的锁。

6. 性能考量：ArrayDeque vs LinkedList

特性 ArrayDeque LinkedList
底层结构 动态数组 双向链表
两端操作 均摊 O(1) O(1)
中间操作 O(n)（插入/删除需要移动元素） O(n)（需要遍历到指定位置）
随机访问 O(n) O(n)
Null 值 不允许 允许
内存使用 更高效（无节点开销） 每个元素有额外引用开销，内存占用稍大
线程安全 非线程安全 非线程安全
扩容/收缩 可能触发数组扩容，涉及元素复制 按需创建/销毁节点，无整体扩容概念

何时选择哪一个？

  • ArrayDeque:
    • 作为栈或队列使用，并且不需要在中间进行插入或删除操作。
    • 对性能和内存效率有较高要求。
    • 不需要存储 null 值。
    • 单线程环境，或自行进行外部同步。
  • LinkedList:
    • 需要频繁在队列的中间进行插入或删除操作（尽管这会降低效率）。
    • 需要存储 null 值。
    • 作为通用列表使用，同时需要 Deque 的两端操作功能。
    • 单线程环境，或自行进行外部同步。

对于大多数情况，尤其是在作为栈或队列使用时，ArrayDeque 通常是比 LinkedList 更好的选择，因为它更轻量、性能更高。

7. 最佳实践与常见陷阱

  • 选择合适的实现： 大多数情况下，优先考虑 ArrayDeque。只有在特定需求（如允许 null 值或需要 List 接口的其他特性）时才考虑 LinkedList。
  • 区分抛异常和返回特殊值的方法： 根据你的错误处理策略选择使用 add/remove/element 系列（抛出异常）还是 offer/poll/peek 系列（返回特殊值）。对于大多数生产代码，倾向于使用返回特殊值的方法，因为它们提供了更平滑的错误处理机制。
  • 线程安全： 在多线程环境中使用 Deque 时，务必进行适当的同步。对于并发场景，ConcurrentLinkedDeque 是一个强大的选择。
  • Null 值： ArrayDeque 不允许 null 元素。尝试添加 null 会抛出 NullPointerException。LinkedList 允许 null 元素，但通常建议避免在集合中存储 null，因为它可能导致 NullPointerException 或难以预料的行为。
  • Stack 和 Vector 的替代： 总是推荐使用 Deque（特别是 ArrayDeque）来替代老旧的 Stack 类，以及 Vector 作为动态数组。

8. 总结

Java 的 Deque 接口为我们提供了一个功能强大且灵活的双端队列数据结构。通过 ArrayDeque 和 LinkedList 这两个主要实现，我们可以根据具体的性能、内存和功能需求，高效地实现栈、队列以及其他需要两端操作的数据结构和算法。掌握 Deque 的使用，将极大地提升你在 Java 集合框架中的编程能力。

滚动至顶部