How does stack-based state management work in 'Implement Queue using Stacks'?

Stack-based state management uses two stacks to simulate the FIFO behavior of a queue. Elements are pushed onto the first stack, and when needed, moved to the second stack to maintain the proper order for pop and peek operations.

What is the time complexity of the pop and peek operations?

The time complexity for pop and peek is amortized O(1), as each element is only moved between stacks once.

What is the space complexity of this solution?

The space complexity is O(n), where n is the number of elements stored in the queue, as the elements are stored in two stacks.

Can we implement this queue using just one stack?

While you can implement a queue with one stack, it would require additional recursive or auxiliary storage, and may not be as efficient or straightforward as using two stacks.

What are the common mistakes in this problem?

Common mistakes include failing to handle the transfer of elements between stacks correctly, misunderstanding the amortized time complexity, and overcomplicating the solution.

#232

Easy

auto_awesome栈·状态

LeetCode 题解工作台

用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（ push 、 pop 、 peek 、 empty ）：实现 MyQueue 类： void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开…

栈设计队列

题目描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

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

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：

1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）

进阶：

你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

lightbulb

解题思路

方法一：双栈

我们使用两个栈，其中栈 stk1用于入队，另一个栈 stk2 用于出队。

入队时，直接将元素入栈 stk1。时间复杂度 $O(1)$ 。

出队时，先判断栈 stk2 是否为空，如果为空，则将栈 stk1 中的元素全部出栈并入栈 stk2，然后再从栈 stk2 中出栈一个元素。如果栈 stk2 不为空，则直接从栈 stk2 中出栈一个元素。均摊时间复杂度 $O(1)$ 。

获取队首元素时，先判断栈 stk2 是否为空，如果为空，则将栈 stk1 中的元素全部出栈并入栈 stk2，然后再从栈 stk2 中获取栈顶元素。如果栈 stk2 不为空，则直接从栈 stk2 中获取栈顶元素。均摊时间复杂度 $O(1)$ 。

判断队列是否为空时，只要判断两个栈是否都为空即可。时间复杂度 $O(1)$ 。

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

29

30

31

32

class MyQueue:
    def __init__(self):
        self.stk1 = []
        self.stk2 = []

    def push(self, x: int) -> None:
        self.stk1.append(x)

    def pop(self) -> int:
        self.move()
        return self.stk2.pop()

    def peek(self) -> int:
        self.move()
        return self.stk2[-1]

    def empty(self) -> bool:
        return not self.stk1 and not self.stk2

    def move(self):
        if not self.stk2:
            while self.stk1:
                self.stk2.append(self.stk1.pop())


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

speed

复杂度分析

指标	值
时间	complexity is amortized O(1) per operation, since elements are moved between the two stacks at most once. Space complexity depends on the number of elements in the queue, which in the worst case is O(n), where n is the number of elements stored in the queue at any given time.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate understands stack-based state management.
question_mark
Candidate is aware of amortized time complexity in queue implementations.
question_mark
Candidate can articulate how to maintain FIFO order using two stacks.

warning

常见陷阱

外企场景

error
Not handling the case where elements need to be transferred from one stack to another.
error
Misunderstanding the amortized time complexity, thinking that transferring elements every time leads to O(n) complexity per operation.
error
Overcomplicating the solution by adding unnecessary data structures or operations beyond the two stacks.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implementing the queue using only one stack.
arrow_right_alt
Designing a thread-safe queue using two stacks.
arrow_right_alt
Handling dynamic resizing of stacks based on queue size.

help

常见问题

外企场景

继续练习

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