【LeetCode刷题日记】23：用栈实现队列

🔥个人主页：北极的代码（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：苍穹外卖日记，SSM框架深入，JavaWeb
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

摘要：

本文介绍如何使用两个栈实现队列功能。通过维护输入栈(stackIn)和输出栈(stackOut)，在push操作时直接压入输入栈，pop/peek操作时若输出栈为空则将输入栈元素全部转移至输出栈，从而实现队列的先进先出特性。关键点在于延迟倒腾策略，保证每个元素只被转移一次，使操作均摊时间复杂度为O(1)。文章包含完整Java实现代码，展示了push、pop、peek和empty等核心方法的实现逻辑。

题目背景：LeetCode232（可直达）

使用栈实现队列的下列操作：

push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。

示例:

MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false

说明:

• 你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
• 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

题目解析：

这道题目是最基础的栈的灵活应用，我们要用栈去实现队列，我们已经知道，栈是先进后出，而队列是先进先出，使用栈来模拟队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。

如图所示，我们的输入栈和输出栈实现的就是这个效果，

在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。

最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。

优点

1. 高效：每个元素只倒腾一次，均摊 O(1)

2. 延迟倒腾：只有在stackOut为空时才倒腾，避免频繁操作

3. 简单可靠：逻辑清晰，不易出错

栈	职责	操作
stackIn	负责入队	只做push，元素都先放这里
stackOut	负责出队	只做pop和peek，元素从这里出去

对比直接用栈的缺点

如果每次pop都把stackIn全部倒出来再倒回去，时间复杂度就是 O(n)，这种延迟倒腾的设计避免了这个问题。

【队列状态】 队首 ←─────────── 队尾 1 2 3 【两个栈的存储】 stackIn: [1, 2, 3] ← 3是栈顶（后进） ↓ 倒腾 stackOut: [3, 2, 1] ← 1是栈顶（先出） 【操作流程】 push(1) → push(2) → push(3) stackIn: 1,2,3 ↓ peek() / pop() → dumpstackIn() stackIn倒进stackOut ↓ stackOut: 3,2,1 ↓ pop() → 1 ✅ 先进先出

用两个栈模拟队列：stackIn负责收元素，stackOut负责出元素，只有当stackOut为空时才把stackIn的全部倒进去，这样就能把栈的 LIFO 变成队列的 FIFO。

题目答案：

class MyQueue { Stack<Integer> stackIn; Stack<Integer> stackOut; /** Initialize your data structure here. */ public MyQueue() { stackIn = new Stack<>(); // 负责进栈 stackOut = new Stack<>(); // 负责出栈 } /** Push element x to the back of queue. */ public void push(int x) { stackIn.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { dumpstackIn(); return stackOut.pop(); } /** Get the front element. */ public int peek() { dumpstackIn(); return stackOut.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { return stackIn.isEmpty() && stackOut.isEmpty(); } // 如果stackOut为空，那么将stackIn中的元素全部放到stackOut中 private void dumpstackIn(){ if (!stackOut.isEmpty()) return; while (!stackIn.isEmpty()){ stackOut.push(stackIn.pop()); } } }

结语：如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！