LeetCode 225: Implement Stack using Queues (Single-Queue Rotation to Simulate LIFO)
LeetCode 225QueueStackSimulationToday we solve LeetCode 225 - Implement Stack using Queues.
Source: https://leetcode.com/problems/implement-stack-using-queues/
English
Problem Summary
Design a stack (LIFO) using only standard queue operations. Implement push, pop, top, and empty.
Key Insight
If we keep the newest element always at the front of one queue, then pop and top become direct front operations. After each push(x), rotate the previous elements behind x.
Brute Force and Limitations
A common approach uses two queues and moves all elements during pop/top. It works, but it complicates state management and increases constant overhead. One queue with immediate rotation is cleaner.
Optimal Algorithm Steps
1) Enqueue new value x.
2) Let k = size - 1 (old element count).
3) Repeat k times: dequeue front and enqueue back.
4) Now x is at front, so pop is one dequeue and top is one front read.
Complexity Analysis
Time: push O(n), pop O(1), top O(1), empty O(1).
Space: O(n).
Common Pitfalls
- Rotating by size instead of size-1, which breaks order.
- Forgetting queue emptiness checks before top/pop in custom wrappers.
- Mixing queue APIs and unintentionally removing from the wrong side.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class MyStack {
private Queue<Integer> q;
public MyStack() {
q = new ArrayDeque<>();
}
public void push(int x) {
q.offer(x);
int k = q.size() - 1;
while (k-- > 0) {
q.offer(q.poll());
}
}
public int pop() {
return q.poll();
}
public int top() {
return q.peek();
}
public boolean empty() {
return q.isEmpty();
}
}type MyStack struct {
q []int
}
func Constructor() MyStack {
return MyStack{q: []int{}}
}
func (s *MyStack) Push(x int) {
s.q = append(s.q, x)
k := len(s.q) - 1
for i := 0; i < k; i++ {
front := s.q[0]
s.q = s.q[1:]
s.q = append(s.q, front)
}
}
func (s *MyStack) Pop() int {
v := s.q[0]
s.q = s.q[1:]
return v
}
func (s *MyStack) Top() int {
return s.q[0]
}
func (s *MyStack) Empty() bool {
return len(s.q) == 0
}class MyStack {
private:
queue<int> q;
public:
MyStack() {}
void push(int x) {
q.push(x);
int k = (int)q.size() - 1;
while (k--) {
q.push(q.front());
q.pop();
}
}
int pop() {
int v = q.front();
q.pop();
return v;
}
int top() {
return q.front();
}
bool empty() {
return q.empty();
}
};from collections import deque
class MyStack:
def __init__(self):
self.q = deque()
def push(self, x: int) -> None:
self.q.append(x)
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self) -> int:
return self.q.popleft()
def top(self) -> int:
return self.q[0]
def empty(self) -> bool:
return len(self.q) == 0var MyStack = function() {
this.q = [];
};
MyStack.prototype.push = function(x) {
this.q.push(x);
let k = this.q.length - 1;
while (k-- > 0) {
this.q.push(this.q.shift());
}
};
MyStack.prototype.pop = function() {
return this.q.shift();
};
MyStack.prototype.top = function() {
return this.q[0];
};
MyStack.prototype.empty = function() {
return this.q.length === 0;
};中文
题目概述
只使用队列的标准操作来实现一个栈（后进先出）。需要实现 push、pop、top、empty。
核心思路
用一个队列也能模拟栈：每次 push(x) 后，把之前的元素依次轮转到队尾，让新元素 x 移到队首。这样队首始终是“栈顶”。
暴力解法与不足
双队列方案通常在 pop/top 时搬移元素，逻辑更绕、常数也更高。单队列“push 后立即旋转”更直观，后续操作更快。
最优算法步骤
1）先把新元素入队。
2）记录旧元素数量 k = size - 1。
3）循环 k 次：队首出队再入队。
4）旋转后新元素来到队首，pop/top 可直接读取队首。
复杂度分析
时间复杂度：push O(n)，pop O(1)，top O(1)，empty O(1)。
空间复杂度：O(n)。
常见陷阱
- 旋转次数写成 size 而不是 size-1，会破坏栈顶顺序。
- 自己封装时忘记判空就访问 top/pop。
- 队列头尾操作混淆，导致实现不再是 LIFO。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class MyStack {
private Queue<Integer> q;
public MyStack() {
q = new ArrayDeque<>();
}
public void push(int x) {
q.offer(x);
int k = q.size() - 1;
while (k-- > 0) {
q.offer(q.poll());
}
}
public int pop() {
return q.poll();
}
public int top() {
return q.peek();
}
public boolean empty() {
return q.isEmpty();
}
}type MyStack struct {
q []int
}
func Constructor() MyStack {
return MyStack{q: []int{}}
}
func (s *MyStack) Push(x int) {
s.q = append(s.q, x)
k := len(s.q) - 1
for i := 0; i < k; i++ {
front := s.q[0]
s.q = s.q[1:]
s.q = append(s.q, front)
}
}
func (s *MyStack) Pop() int {
v := s.q[0]
s.q = s.q[1:]
return v
}
func (s *MyStack) Top() int {
return s.q[0]
}
func (s *MyStack) Empty() bool {
return len(s.q) == 0
}class MyStack {
private:
queue<int> q;
public:
MyStack() {}
void push(int x) {
q.push(x);
int k = (int)q.size() - 1;
while (k--) {
q.push(q.front());
q.pop();
}
}
int pop() {
int v = q.front();
q.pop();
return v;
}
int top() {
return q.front();
}
bool empty() {
return q.empty();
}
};from collections import deque
class MyStack:
def __init__(self):
self.q = deque()
def push(self, x: int) -> None:
self.q.append(x)
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self) -> int:
return self.q.popleft()
def top(self) -> int:
return self.q[0]
def empty(self) -> bool:
return len(self.q) == 0var MyStack = function() {
this.q = [];
};
MyStack.prototype.push = function(x) {
this.q.push(x);
let k = this.q.length - 1;
while (k-- > 0) {
this.q.push(this.q.shift());
}
};
MyStack.prototype.pop = function() {
return this.q.shift();
};
MyStack.prototype.top = function() {
return this.q[0];
};
MyStack.prototype.empty = function() {
return this.q.length === 0;
};
Comments