LeetCode 232简单栈 / 队列设计
用栈实现队列 图解题解
这道题到底在问什么
只用两个栈实现队列的 push、pop、peek、empty。
- 操作
- push(1), push(2), peek(), pop()
- 输出
- 1, 1
最优解：一步一步想明白
- 3可以每次插入都搬运元素，但会让 push 很重。更好的做法是懒搬运。
- 4新元素先进 in。要出队时，如果 out 为空，就把 in 全部倒过去，顺序正好反过来。
- 5push1 进入 in 栈。out 为空，不急着倒。
- 6push2 继续压入 in。此时 in 栈顶是 2。
- 7move要看队头，但 out 为空，触发搬运。
- 8front=1把 2、1 依次从 in 弹出压入 out。out 栈顶变成最早进入的 1。
- 9pop 1从 out 弹出 1。队列的先进先出完成。
- 10peek 2下一次 peek 直接看 out 栈顶 2，不需要再倒。
- 13懒搬运让 push 轻，pop/peek 需要时再付成本。
- 16keep order如果 out 还有队头 2，新 push 的 3 在 in。此时不能把 in 倒进 out，否则 3 会插到队头前面。
- 23这题学完不要乱跳，下一步去 对应专题 连刷同类题；卡住时用 AI 答疑追问“为什么这一步成立”，比只背答案更稳。
⚠️ 容易写错的地方
✗ 错：每次 pop 都从 in 倒
✓ 对：只有 out 为空才倒
否则会破坏已有 out 的队头顺序。
✗ 错：peek 直接看 in 栈底
✓ 对：统一调用 move 后看 out 栈顶
不要绕过抽象，保持逻辑一致。
✗ 错：复杂度写单次 O(1)
✓ 对：写均摊 O(1)
某一次搬运可能是 O(n)。
完整代码（Python / C++ / Java）
Python
class MyQueue:
def __init__(self):
self.in_st = []
self.out_st = []
def push(self, x):
self.in_st.append(x)
def _move(self):
if not self.out_st:
while self.in_st:
self.out_st.append(self.in_st.pop())
def pop(self):
self._move()
return self.out_st.pop()
def peek(self):
self._move()
return self.out_st[-1]
def empty(self):
return not self.in_st and not self.out_stC++
class MyQueue {
stack<int> inSt, outSt;
void move() {
if (outSt.empty()) {
while (!inSt.empty()) {
outSt.push(inSt.top());
inSt.pop();
}
}
}
public:
void push(int x) { inSt.push(x); }
int pop() { move(); int x = outSt.top(); outSt.pop(); return x; }
int peek() { move(); return outSt.top(); }
bool empty() { return inSt.empty() && outSt.empty(); }
};Java
class MyQueue {
Deque<Integer> inSt = new ArrayDeque<>();
Deque<Integer> outSt = new ArrayDeque<>();
private void move() {
if (outSt.isEmpty()) {
while (!inSt.isEmpty()) outSt.push(inSt.pop());
}
}
public void push(int x) { inSt.push(x); }
public int pop() { move(); return outSt.pop(); }
public int peek() { move(); return outSt.peek(); }
public boolean empty() { return inSt.isEmpty() && outSt.isEmpty(); }
}套路模板 · 用栈实现队列迁移骨架
# 栈题先问：遇到当前元素，要不要结算最近的历史状态？
stack = []
for x in 输入:
while stack and 当前元素能结算栈顶:
top = stack.pop() # 最近的先处理
用 top 更新答案/恢复现场
stack.append(当前状态)
return 答案vector<State> st;
for (auto x : input) {
while (!st.empty() && 当前元素能结算栈顶) {
auto top = st.back(); st.pop_back();
// 用 top 更新答案/恢复现场
}
st.push_back(当前状态);
}
return ans;Deque<State> stack = new ArrayDeque<>();
for (Item x : input) {
while (!stack.isEmpty() && 当前元素能结算栈顶) {
State top = stack.pop();
// 用 top 更新答案/恢复现场
}
stack.push(当前状态);
}
return ans;复杂度
单次最坏
O(n)
out 为空时一次性搬运 n 个元素
均摊时间
O(1)
每个元素最多从 in 到 out 搬一次
空间复杂度
O(n)
两个栈共存队列元素
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 用栈实现队列 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么倒过去顺序就对了？+
in 的栈底是最早进入的元素，倒到 out 后它变成栈顶。
这道题为什么用「队列设计」，换最直接的暴力解会差在哪？+
队列设计抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。