What is the easiest method to implement a stack using queues?

The simplest method is the two-queue approach, where you maintain the new element in an empty queue and transfer all previous elements to it, preserving LIFO order.

Can I implement this stack using only one queue?

Yes, using single-queue rotation: enqueue the new element and rotate all existing elements behind it so the front always represents the top.

How do I efficiently retrieve the top element without rotating the queue every time?

Track the top element with a separate variable updated on push and pop operations, which avoids unnecessary rotations.

What is the time complexity for push and pop operations in this problem?

For the two-queue approach, push is O(n) and pop/top is O(1). For the single-queue rotation, push is O(n) and pop/top is O(1). Space is O(n) in both methods.

Are there common mistakes when implementing stack using queues?

Yes, common mistakes include trying to access the last element directly, ignoring top updates, and miscalculating push or pop complexity.

#225

Easy

auto_awesome栈·状态

LeetCode 题解工作台

用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（ push 、 top 、 pop 和 empty ）。实现 MyStack 类： void push(int x) 将元素 x 压入栈顶。 int pop() 移除并返回栈顶元素。 int top() 返回栈顶元素。…

栈设计队列

题目描述

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：

1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

进阶：你能否仅用一个队列来实现栈。

lightbulb

解题思路

方法一：两个队列

我们使用两个队列 $q_1$ 和 $q_2$ ，其中 $q_1$ 用于存储栈中的元素，而 $q_2$ 用于辅助实现栈的操作。

push 操作：将元素压入 $q_2$ ，然后将 $q_1$ 中的元素依次弹出并压入 $q_2$ ，最后交换 $q_1$ 和 $q_2$ 的引用。时间复杂度 $O(n)$ 。
pop 操作：直接弹出 $q_1$ 的队首元素。时间复杂度 $O(1)$ 。
top 操作：直接返回 $q_1$ 的队首元素。时间复杂度 $O(1)$ 。
empty 操作：判断 $q_1$ 是否为空。时间复杂度 $O(1)$ 。

空间复杂度 $O(n)$ ，其中 $n$ 是栈中元素的个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

class MyStack:
    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()

    def push(self, x: int) -> None:
        self.q2.append(x)
        while self.q1:
            self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1

    def pop(self) -> int:
        return self.q1.popleft()

    def top(self) -> int:
        return self.q1[0]

    def empty(self) -> bool:
        return len(self.q1) == 0


# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

speed

复杂度分析

指标	值
时间	and space complexity depend on the chosen approach: the two-queue method results in O(n) push and O(1) pop/top, whereas the single-queue rotation method has O(n) push with O(1) pop/top. Space is O(n) in both cases for queue storage.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask candidates to implement a stack with strict queue-only operations to test understanding of LIFO vs FIFO behavior.
question_mark
Check if the candidate optimizes push or pop; performance trade-offs reveal problem-solving depth.
question_mark
Listen for discussion about top element tracking or queue rotation as a method to preserve stack order.

warning

常见陷阱

外企场景

error
Attempting to access the last element directly without rotation or auxiliary storage violates queue-only rules.
error
Confusing push and pop time complexity and not accounting for O(n) rotations in single-queue approaches.
error
Neglecting to update the top variable when popping can lead to incorrect top() results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implement a stack using only a single queue without auxiliary variables.
arrow_right_alt
Optimize for frequent top() calls while minimizing rotations on push().
arrow_right_alt
Design a double-ended stack using two queues to allow both front and back LIFO operations.

help

常见问题

外企场景

继续练习

#232 用栈实现队列 #341 扁平化嵌套列表迭代器 #173 二叉搜索树迭代器