0Pricing
Java Academy · 课时

双端队列操作：栈与队列

使用 LinkedList 作为 Deque，通过 push/pop 实现栈行为，通过 offer/poll 实现队列行为

双端队列操作：栈与队列 是 CoddyKit 上的免费 Java Academy 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Java Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Java Academy 课程共包含 4 节课。

双端队列：两端队列

双端队列允许在两端插入和删除元素。Java 的 Deque 接口由 LinkedList 和 ArrayDeque 实现。

import java.util.Deque;
import java.util.ArrayDeque;

Deque<String> deque = new ArrayDeque<>();
deque.addFirst("A"); // front
deque.addLast("B");  // back
deque.addFirst("Z"); // new front

System.out.println(deque); // [Z, A, B]

作为双端队列时比较 ArrayDeque 和 LinkedList

通常更推荐将 ArrayDeque 而不是 LinkedList 用作双端队列：

  • 没有每个元素对应的节点开销
  • 缓存局部性更好
  • 栈和队列操作速度略快

只有在同时需要 List 接口时，才选择 LinkedList。

使用双端队列执行栈操作

使用 push（addFirst）和 pop（removeFirst）来模拟 LIFO 栈。请避免使用过时的 Stack 类——它是同步的，并且已经过时。

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);

System.out.println(stack.pop());  // 3
System.out.println(stack.peek()); // 2 (no removal)
System.out.println(stack.pop());  // 2

使用双端队列执行队列操作

使用 offer（addLast）和 poll（removeFirst）来模拟 FIFO 队列。offer 失败时返回 false；add 则会抛出异常。

Deque<String> queue = new ArrayDeque<>();
queue.offer("task1");
queue.offer("task2");
queue.offer("task3");

System.out.println(queue.poll());  // task1
System.out.println(queue.poll());  // task2
System.out.println(queue.size());  // 1

双端队列方法参考表

双端队列提供两组方法：一组会抛出异常，另一组会返回特殊值：

  • addFirst/addLast 与 offerFirst/offerLast
  • removeFirst/removeLast 与 pollFirst/pollLast
  • getFirst/getLast 与 peekFirst/peekLast

优先使用 offer/poll/peek 这一组方法，以避免对空双端队列操作时抛出异常。

真实示例：使用两个栈实现撤销和重做

双端队列的经典使用场景：撤销历史记录是一个栈，重做记录是另一个栈。

Deque<String> undo = new ArrayDeque<>();
Deque<String> redo = new ArrayDeque<>();

undo.push("type 'Hello'");
undo.push("type ' World'");

String action = undo.pop();
System.out.println("Undone: " + action); // type ' World'
redo.push(action);

System.out.println("Redo top: " + redo.peek()); // type ' World'

使用双端队列检查回文

双端队列可以优雅地检查回文——同时比较两端的字符。

Deque<Character> deque = new ArrayDeque<>();
for (char c : "racecar".toCharArray()) deque.add(c);

boolean isPalindrome = true;
while (deque.size() > 1) {
    if (!deque.pollFirst().equals(deque.pollLast())) {
        isPalindrome = false;
        break;
    }
}
System.out.println(isPalindrome); // true

使用队列实现 BFS

广度优先搜索使用队列。在竞赛编程和图遍历中，ArrayDeque 是实现 BFS 的标准选择。

import java.util.*;

// BFS on a simple adjacency list
Map<Integer,List<Integer>> graph = Map.of(
    1, List.of(2,3),
    2, List.of(4),
    3, List.of(4),
    4, List.of()
);
Deque<Integer> queue = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
queue.offer(1);
while (!queue.isEmpty()) {
    int node = queue.poll();
    if (visited.add(node)) {
        System.out.print(node + " ");
        queue.addAll(graph.get(node));
    }
}

使用栈实现 DFS

深度优先搜索使用栈。同样，请优先使用 ArrayDeque，而不是过时的 Stack 类。

Deque<Integer> stack = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
stack.push(1);
while (!stack.isEmpty()) {
    int node = stack.pop();
    if (visited.add(node)) {
        System.out.print(node + " ");
        // push neighbors (will be processed in reverse order)
        List<Integer> neighbors = List.of(2, 3); // simplified
        for (int n : neighbors) if (!visited.contains(n)) stack.push(n);
    }
}

带大小检查的有界双端队列

ArrayDeque 会动态增长，但您可以手动限制容量，以模拟有界缓冲区：

Deque<Integer> buffer = new ArrayDeque<>();
int MAX = 3;

for (int i = 1; i <= 5; i++) {
    if (buffer.size() >= MAX) {
        buffer.pollFirst(); // drop oldest
    }
    buffer.offerLast(i);
}
System.out.println(buffer); // [3, 4, 5]

性能说明

ArrayDeque 使用循环数组，并会在填满时将容量加倍。所有操作的摊销成本都是 O(1)。由于缓存效率更高，它在大多数基准测试中都优于 LinkedList。请不要手动进行同步——并发场景应使用 ConcurrentLinkedDeque 或阻塞队列。

快速检查

对于 LIFO 操作，应优先使用哪个类来替代过时的 Stack？

回顾：双端队列操作

关键要点：

  • 双端队列允许在两端以 O(1) 插入和删除元素
  • 对于纯栈或队列的使用场景，ArrayDeque 优于 LinkedList
  • push/pop → LIFO 栈；offer/poll → FIFO 队列
  • 经典用途：撤销/重做、BFS/DFS、滑动窗口、回文检查
  • 避免使用过时的 Stack 和 Queue 类

常见问题解答

「双端队列操作：栈与队列」课时是免费的吗？

是的 — 「双端队列操作：栈与队列」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Java Academy 课程的其余内容，请升级到 CoddyKit PRO。 Java Academy 课程共包含 4 节课。

「双端队列操作：栈与队列」这节课中我会学到什么？

使用 LinkedList 作为 Deque，通过 push/pop 实现栈行为，通过 offer/poll 实现队列行为 你通过在浏览器中直接运行的动手代码来练习 Java Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Java Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Java Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。

「双端队列操作：栈与队列」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Java Academy 课中编写并运行代码吗？

能。每节 Java Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. LinkedList 内部原理
  2. 双端队列操作：栈与队列
  3. LinkedList 与 ArrayList 的权衡
  4. 使用 PriorityQueue 进行有序处理
← 返回 Java Academy