CodeGym /课程 /JAVA 25 SELF /Queue, Deque, Stack：队列与栈的使用

Queue, Deque, Stack：队列与栈的使用

JAVA 25 SELF

第 27 级 , 课程 2

可用

1. Queue 接口：经典队列（FIFO）

在编程中，就像在生活中一样，有些场景不仅要存储元素集合，还要管理其处理顺序。想象一下超市里的排队：越靠前的人越先被服务。这就是 FIFO 原理——“先来先服务”。而橱柜里的一摞盘子则遵循 LIFO 原理——“后进先出”。在 Java 中，这些原理对应相应的集合：队列 Queue、双端队列 Deque 和栈 Stack。

应用场景：

按到达顺序处理任务（任务队列、文档打印、事件处理）。
实现操作撤销/重做（undo/redo）——栈。
表达式解析，树和图的遍历（广度/深度优先）等。

什么是队列？

队列（Queue）是一种遵循 FIFO 原理的集合。元素从尾部加入，从头部取出。就像在商店里：先到的人先被服务。

Queue 接口的基本方法

方法	作用	返回值
`offer(e)`	在末尾添加元素（不抛出异常）	true/false
`add(e)`	在末尾添加元素（可能抛出异常）	true/Exception
`poll()`	删除并返回第一个元素	元素/null
`remove()`	删除并返回第一个元素	元素/Exception
`peek()`	返回第一个元素，但不删除	元素/null
`element()`	返回第一个元素，但不删除	元素/Exception

你会注意到一些方法成对出现且行为相似。差别在于“温和度”：offer、poll、peek 在失败时返回特殊值（通常是 null 或 false），不抛出异常；而 add、remove、element 在边界情况下（队列为空，有时容量受限）会抛出异常。

示例：任务队列

import java.util.*;

public class QueueDemo {
    public static void main(String[] args) {
        Queue<String> tasks = new LinkedList<>();
        tasks.offer("刷牙");
        tasks.offer("做操");
        tasks.offer("喝咖啡");

        while (!tasks.isEmpty()) {
            String task = tasks.poll(); // 从队列头部取任务
            System.out.println("正在执行: " + task);
        }
    }
}

输出：

正在执行: 刷牙
正在执行: 做操
正在执行: 喝咖啡

为什么常用 LinkedList？

接口是契约，具体实现有多种。经常使用 LinkedList，因为它能在两端快速添加/删除。不过一个很好的替代是 ArrayDeque。还有一些专用实现：PriorityQueue（按优先级的队列），下文会讲到。

2. Deque 接口：双端队列

Deque（Double Ended Queue）——可以从两端（头部和尾部）添加和删除元素。就像一辆有两扇门的公交车：可以从任意一侧上车/下车。

Deque = 万能选手：既可以当作普通队列（FIFO），也可以当作栈（LIFO），或两者兼用的混合体。

Deque 接口的基本方法

方法	作用	用法示例
`addFirst(e)`	添加到头部	`queue.addFirst("A")`
`addLast(e)`	添加到尾部	`queue.addLast("B")`
`removeFirst()`	从头部删除并返回	`queue.removeFirst()`
`removeLast()`	从尾部删除并返回	`queue.removeLast()`
`peekFirst()`	查看头部（不删除）	`queue.peekFirst()`
`peekLast()`	查看尾部（不删除）	`queue.peekLast()`
`offerFirst(e)`	添加到头部（不抛出异常）	`queue.offerFirst("C")`
`offerLast(e)`	添加到尾部（不抛出异常）	`queue.offerLast("D")`

示例：Deque 既可作队列也可作栈

import java.util.*;

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

        // 作为队列使用（FIFO）
        deque.offerLast("A");
        deque.offerLast("B");
        deque.offerLast("C");
        System.out.println("队列 (FIFO):");
        while (!deque.isEmpty()) {
            System.out.println(deque.pollFirst());
        }

        // 作为栈使用（LIFO）
        deque.offerLast("1");
        deque.offerLast("2");
        deque.offerLast("3");
        System.out.println("栈 (LIFO):");
        while (!deque.isEmpty()) {
            System.out.println(deque.pollLast());
        }
    }
}

输出：

队列 (FIFO):
A
B
C
栈 (LIFO):
3
2
1

为什么选 ArrayDeque？

ArrayDeque 是基于数组的 Deque 的快速且紧凑的实现。对于栈和队列，它通常比老旧的 Stack 更快、更可靠，而且没有固定容量（仅受内存限制）。

3. Stack：栈——后进先出（LIFO）

栈遵循 LIFO 原则：最后压入的元素最先弹出。在编程中，栈常用于操作历史（undo）、遍历递归结构（树/图）、表达式计算等。

Stack 类（以及为何不建议使用）

Java 中有 Stack 类，它继承自已过时的 Vector。今天在新项目中不推荐使用它，更可取的是 Deque/ArrayDeque。

栈方法（基于 Deque）

方法	作用
`push(e)`	将元素压入栈顶
`pop()`	弹出并返回栈顶元素
`peek()`	查看栈顶元素

注意：在 Deque 中，这些操作分别对应 addFirst/removeFirst/peekFirst，但为了兼容性也提供了“栈式”的方法名 push/pop/peek。

示例：基于 ArrayDeque 的栈

import java.util.*;

public class StackDemo {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("第一");
        stack.push("第二");
        stack.push("第三");

        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}

输出：

第三
第二
第一

为什么不用 Stack？

Stack 是同步的（更慢），并继承了过时的 Vector。
ArrayDeque 往往更快、更省内存，且不阻塞线程。
如果你在新代码中看到 Stack——通常可以用 ArrayDeque 替换。

4. 何时使用哪种结构

结构	原则	适用场景	示例实现
Queue	FIFO	任务队列、事件处理、打印、客户排队	`LinkedList, ArrayDeque, PriorityQueue`
Stack	LIFO	Undo/redo、递归、解析器、树遍历	`ArrayDeque`
Deque	FIFO/LIFO	缓冲区、回文、双端队列、通用任务	`ArrayDeque, LinkedList`

生活中的例子：

银行排队——Queue。
编辑器中的操作历史——Stack。
公交车队列，两端都可进出——Deque。

5. 代码示例：在小应用中实现队列与栈

示例 1：文档打印队列

import java.util.*;

public class PrintQueueApp {
    public static void main(String[] args) {
        Queue<String> printQueue = new ArrayDeque<>();
        printQueue.offer("文档1.pdf");
        printQueue.offer("文档2.docx");
        printQueue.offer("文档3.xls");

        while (!printQueue.isEmpty()) {
            String doc = printQueue.poll();
            System.out.println("正在打印: " + doc);
        }
    }
}

示例 2：操作撤销栈（undo）

import java.util.*;

public class UndoStackApp {
    public static void main(String[] args) {
        Deque<String> undoStack = new ArrayDeque<>();
        undoStack.push("插入文本");
        undoStack.push("更改颜色");
        undoStack.push("删除图片");

        System.out.println("最近的操作: " + undoStack.peek()); // 删除图片

        while (!undoStack.isEmpty()) {
            System.out.println("撤销: " + undoStack.pop());
        }
    }
}

示例 3：双端队列

import java.util.*;

public class DequeApp {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();
        deque.addFirst("A");
        deque.addLast("B");
        deque.addFirst("C");
        deque.addLast("D");

        System.out.println("从头部取出: " + deque.removeFirst()); // C
        System.out.println("从尾部取出: " + deque.removeLast());   // D
        System.out.println("剩余: " + deque); // [A, B]
    }
}

6. 实现细节与注意事项

ArrayDeque 是大多数队列/栈场景下最快且最通用的实现。
LinkedList 也实现了 Deque；在短队列场景下通常比 ArrayDeque 慢。
PriorityQueue 是按优先级的队列：顺序由优先级（自然顺序或通过 Comparator 指定）决定，它不是普通的 FIFO 队列。
Stack 已过时且是同步的；在新项目中更推荐 ArrayDeque。
Deque 的便利之处在于可同时操作结构的头尾，一种抽象覆盖了队列与栈的使用场景。

7. 使用队列与栈的常见错误

错误 1：使用 Stack 而不是 Deque。
很多初学者看到 Stack 这个类就“望名取用”。在现代项目中通常使用 ArrayDeque（或 LinkedList）配合 push/pop 方法来代替。

错误 2：违背数据结构的工作原则。
尝试用索引访问队列/栈中的元素，例如 queue.get(0) 或 stack.get(0)。这不符合其模型——请使用相应的方法（peek、poll、pop 等）。

错误 3：在未检查情况下使用 remove()/element()/add()。
remove、element、add 在队列为空/容量受限时可能抛出异常。更安全的做法是使用“温和”的 offer、poll、peek，它们会返回特殊值。

错误 4：在 ArrayDeque 中使用 null 元素。
ArrayDeque 不允许 null。尝试加入 null 会导致 NullPointerException。

错误 5：把 PriorityQueue 当作普通队列。
在 PriorityQueue 中，顺序由优先级决定（自然顺序或由 Comparator 指定）。若需要严格的 FIFO，请使用 ArrayDeque 或 LinkedList。

错误 6：在 for-each 遍历中修改队列/栈。
在 for-each 遍历集合时删除元素可能导致 ConcurrentModificationException。删除时请使用迭代器，或像示例那样在循环中使用 poll/pop。

上一课上一课

下一课下一课

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION