当前位置：首页 > backend >正文

栈和队列的奇妙冒险：用栈实现队列

backend 2025/6/23 19:05:08

栈和队列的奇妙冒险：用栈实现队列

大家好，欢迎来到代码的奇幻世界！今天我们要探讨一个有趣的问题：如何用栈来实现队列？这就像是用咖啡杯来当茶壶用 —— 虽然有点奇怪，但只要方法正确，也能倒出好茶！

问题背景

在编程的世界里，栈和队列是两种基本的数据结构。栈就像是一叠盘子，只能从顶部取盘子（后进先出，LIFO）；而队列则像是排队买奶茶，先来的人先拿到奶茶（先进先出，FIFO）。现在，我们要用栈这种 “盘子堆” 来实现队列这种 “奶茶排队”，这可真是个有趣的挑战！

实现思路

想象一下，你有两个栈（盘子堆），一个用来放新加入的元素（栈 1），另一个用来按顺序取出元素（栈 2）。当需要取出元素时，如果栈 2 是空的，就把栈 1 中的所有元素一个个弹出并压入栈 2，这样栈 2 中的元素顺序就和队列的顺序一样了！

下面是具体的实现代码：

static class SQueue {// 栈1负责存储新元素，栈2负责按顺序提供元素private final Stack<Integer> stack1 = new Stack<>();private final Stack<Integer> stack2 = new Stack<>();public SQueue() {}// 入队操作：直接把元素压入栈1public void offer(int value) {stack1.push(value);}// 查看队首元素public Integer peek() {// 如果栈2空了，就从栈1中 reload 元素if (stack2.isEmpty()) {reload();}// 如果 reload 后还是空，说明队列里没元素了if (stack2.isEmpty()) {throw new EmptyStackException();}return stack2.peek();}// 出队操作public Integer poll() {if (stack2.isEmpty()) {reload();}if (stack2.isEmpty()) {throw new EmptyStackException();}return stack2.pop();}// 重新装载：把栈1的元素全部倒入栈2private void reload() {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}
}

代码解释

这个实现中有几个关键点：

两个栈的分工：
- 栈 1（stack1）：只负责接收新加入的元素，就像一个 “仓库”，只进不出。
- 栈 2（stack2）：只负责按顺序提供元素，就像一个 “商店货架”，元素从这里被顾客（程序）取走。
元素的流动：
- 当需要取元素时，如果栈 2（货架）是空的，就从栈 1（仓库）中把所有元素搬到栈 2 中。
- 搬运的过程会把元素的顺序反转两次（从栈 1 弹出时反转一次，压入栈 2 时再反转一次），最终得到正确的顺序。
效率分析：
- 入队操作（offer）：时间复杂度是 O (1)，就像把盘子放到堆顶上一样快。
- 出队操作（poll）和查看队首（peek）：平均时间复杂度是 O (1)。虽然在需要 reload 时会比较慢，但每个元素最多只会被 reload 一次，所以总体上还是很快的！

测试代码

让我们来测试一下这个神奇的 “栈变队列”：

public static void main(String[] args) {SQueue sQueue = new SQueue();// 让 0 到 9 这 10 个元素排好队for (int i = 0; i < 10; i++) {sQueue.offer(i);}// 看看是不是按顺序出来for (int i = 0; i < 10; i++) {System.out.println(sQueue.poll());}
}