LeetCode 232: Implement Queue using Stacks (Two-Stack FIFO Simulation)
LeetCode 232StackQueueDesignToday we solve LeetCode 232 - Implement Queue using Stacks.
Source: https://leetcode.com/problems/implement-queue-using-stacks/
English
Problem Summary
Design a queue using only stack operations. Implement push, pop, peek, and empty while preserving FIFO behavior.
Key Insight
Use two stacks: in for incoming elements and out for outgoing elements. When out is empty and we need front access, move all items from in to out. This reversal makes the oldest element appear on top of out.
Brute Force and Limitations
A naive way is to move elements back and forth on every push or every pop, causing O(n) per operation frequently. The two-stack lazy transfer strategy avoids repeated full transfers.
Optimal Algorithm Steps
1) push(x): push into in.
2) Before pop/peek, call moveIfNeeded().
3) moveIfNeeded(): if out is empty, move all elements from in to out.
4) pop(): remove top of out.
5) peek(): read top of out.
6) empty(): queue is empty iff both stacks are empty.
Complexity Analysis
Amortized time per operation: O(1).
Worst-case single pop/peek: O(n) when transfer happens.
Space: O(n).
Common Pitfalls
- Transferring on every operation instead of only when out is empty.
- Forgetting that empty must check both stacks.
- Accessing out directly without lazy transfer.
- Mixing front/back semantics when naming variables.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class MyQueue {
private final Deque<Integer> in = new ArrayDeque<>();
private final Deque<Integer> out = new ArrayDeque<>();
public void push(int x) {
in.push(x);
}
public int pop() {
moveIfNeeded();
return out.pop();
}
public int peek() {
moveIfNeeded();
return out.peek();
}
public boolean empty() {
return in.isEmpty() && out.isEmpty();
}
private void moveIfNeeded() {
if (!out.isEmpty()) return;
while (!in.isEmpty()) {
out.push(in.pop());
}
}
}type MyQueue struct {
in []int
out []int
}
func Constructor() MyQueue {
return MyQueue{}
}
func (q *MyQueue) Push(x int) {
q.in = append(q.in, x)
}
func (q *MyQueue) moveIfNeeded() {
if len(q.out) > 0 {
return
}
for len(q.in) > 0 {
n := len(q.in)
q.out = append(q.out, q.in[n-1])
q.in = q.in[:n-1]
}
}
func (q *MyQueue) Pop() int {
q.moveIfNeeded()
n := len(q.out)
x := q.out[n-1]
q.out = q.out[:n-1]
return x
}
func (q *MyQueue) Peek() int {
q.moveIfNeeded()
return q.out[len(q.out)-1]
}
func (q *MyQueue) Empty() bool {
return len(q.in) == 0 && len(q.out) == 0
}class MyQueue {
private:
stack<int> in, out;
void moveIfNeeded() {
if (!out.empty()) return;
while (!in.empty()) {
out.push(in.top());
in.pop();
}
}
public:
MyQueue() {}
void push(int x) {
in.push(x);
}
int pop() {
moveIfNeeded();
int x = out.top();
out.pop();
return x;
}
int peek() {
moveIfNeeded();
return out.top();
}
bool empty() {
return in.empty() && out.empty();
}
};class MyQueue:
def __init__(self):
self.in_stack = []
self.out_stack = []
def push(self, x: int) -> None:
self.in_stack.append(x)
def _move_if_needed(self) -> None:
if self.out_stack:
return
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
def pop(self) -> int:
self._move_if_needed()
return self.out_stack.pop()
def peek(self) -> int:
self._move_if_needed()
return self.out_stack[-1]
def empty(self) -> bool:
return not self.in_stack and not self.out_stackvar MyQueue = function() {
this.inStack = [];
this.outStack = [];
};
MyQueue.prototype.push = function(x) {
this.inStack.push(x);
};
MyQueue.prototype.moveIfNeeded = function() {
if (this.outStack.length > 0) return;
while (this.inStack.length > 0) {
this.outStack.push(this.inStack.pop());
}
};
MyQueue.prototype.pop = function() {
this.moveIfNeeded();
return this.outStack.pop();
};
MyQueue.prototype.peek = function() {
this.moveIfNeeded();
return this.outStack[this.outStack.length - 1];
};
MyQueue.prototype.empty = function() {
return this.inStack.length === 0 && this.outStack.length === 0;
};中文
题目概述
只能使用栈操作来实现队列，支持 push、pop、peek、empty，并保持队列先进先出（FIFO）语义。
核心思路
维护两个栈：in 负责入队，out 负责出队/看队首。当 out 为空且需要取队首时，把 in 全部倒入 out，利用栈反转把最早入队元素放到 out 栈顶。
暴力解法与不足
如果每次操作都整体搬运元素，会频繁触发 O(n) 代价。惰性搬运（仅在 out 为空时搬运）可以显著降低总成本。
最优算法步骤
1）push(x)：直接压入 in。
2）执行 pop/peek 前调用 moveIfNeeded()。
3）若 out 为空，则把 in 全部弹出并压入 out。
4）pop()：弹出 out 栈顶。
5）peek()：读取 out 栈顶。
6）empty()：当且仅当两个栈都为空。
复杂度分析
均摊时间复杂度：每个操作 O(1)。
单次最坏 pop/peek：O(n)（发生整批搬运时）。
空间复杂度：O(n)。
常见陷阱
- 每次都搬运，失去均摊优势。
- empty 只判断一个栈，逻辑错误。
- 未先搬运就直接读 out，导致访问错误。
- front/back 概念混淆，导致返回元素顺序不对。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class MyQueue {
private final Deque<Integer> in = new ArrayDeque<>();
private final Deque<Integer> out = new ArrayDeque<>();
public void push(int x) {
in.push(x);
}
public int pop() {
moveIfNeeded();
return out.pop();
}
public int peek() {
moveIfNeeded();
return out.peek();
}
public boolean empty() {
return in.isEmpty() && out.isEmpty();
}
private void moveIfNeeded() {
if (!out.isEmpty()) return;
while (!in.isEmpty()) {
out.push(in.pop());
}
}
}type MyQueue struct {
in []int
out []int
}
func Constructor() MyQueue {
return MyQueue{}
}
func (q *MyQueue) Push(x int) {
q.in = append(q.in, x)
}
func (q *MyQueue) moveIfNeeded() {
if len(q.out) > 0 {
return
}
for len(q.in) > 0 {
n := len(q.in)
q.out = append(q.out, q.in[n-1])
q.in = q.in[:n-1]
}
}
func (q *MyQueue) Pop() int {
q.moveIfNeeded()
n := len(q.out)
x := q.out[n-1]
q.out = q.out[:n-1]
return x
}
func (q *MyQueue) Peek() int {
q.moveIfNeeded()
return q.out[len(q.out)-1]
}
func (q *MyQueue) Empty() bool {
return len(q.in) == 0 && len(q.out) == 0
}class MyQueue {
private:
stack<int> in, out;
void moveIfNeeded() {
if (!out.empty()) return;
while (!in.empty()) {
out.push(in.top());
in.pop();
}
}
public:
MyQueue() {}
void push(int x) {
in.push(x);
}
int pop() {
moveIfNeeded();
int x = out.top();
out.pop();
return x;
}
int peek() {
moveIfNeeded();
return out.top();
}
bool empty() {
return in.empty() && out.empty();
}
};class MyQueue:
def __init__(self):
self.in_stack = []
self.out_stack = []
def push(self, x: int) -> None:
self.in_stack.append(x)
def _move_if_needed(self) -> None:
if self.out_stack:
return
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
def pop(self) -> int:
self._move_if_needed()
return self.out_stack.pop()
def peek(self) -> int:
self._move_if_needed()
return self.out_stack[-1]
def empty(self) -> bool:
return not self.in_stack and not self.out_stackvar MyQueue = function() {
this.inStack = [];
this.outStack = [];
};
MyQueue.prototype.push = function(x) {
this.inStack.push(x);
};
MyQueue.prototype.moveIfNeeded = function() {
if (this.outStack.length > 0) return;
while (this.inStack.length > 0) {
this.outStack.push(this.inStack.pop());
}
};
MyQueue.prototype.pop = function() {
this.moveIfNeeded();
return this.outStack.pop();
};
MyQueue.prototype.peek = function() {
this.moveIfNeeded();
return this.outStack[this.outStack.length - 1];
};
MyQueue.prototype.empty = function() {
return this.inStack.length === 0 && this.outStack.length === 0;
};
Comments