232. 用栈实现队列

题目链接：232. 用栈实现队列

题目描述

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

核心思考：双栈倒腾模拟队列

栈是后进先出（LIFO），队列是先进先出（FIFO）。要用栈模拟队列，关键在于如何将元素的顺序翻转一次，使得最早进入的元素能最先被取出。

做法是维护两个栈：

• s1（输入栈）：所有新元素都 push 到这里。
• s2（输出栈）：所有 pop 和 peek 操作都从这里取。

当 s2 为空、需要取元素时，把 s1 中的所有元素逐个弹出并压入 s2。经过这次倒腾，s1 中最早进入的元素（栈底）就跑到了 s2 的栈顶，顺序刚好翻转，符合队列的先进先出语义。

各操作的具体逻辑：

• push(x)：直接压入 s1。
• peek()：如果 s2 为空，先将 s1 全部倒入 s2，然后返回 s2 栈顶元素。
• pop()：先调用 peek() 确保 s2 非空，然后弹出 s2 栈顶。
• empty()：当且仅当 s1 和 s2 都为空时，队列为空。

解题思路 (Python)

class MyQueue:

    def __init__(self):
        self.s1 = []
        self.s2 = []

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

    def pop(self) -> int:
        self.peek()
        return self.s2.pop()

    def peek(self) -> int:
        if not self.s2:
            while self.s1:
                self.s2.append(self.s1.pop())
        return self.s2[-1]

    def empty(self) -> bool:
        return not self.s1 and not self.s2


# 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()

复杂度分析

• 时间复杂度：push 和 empty 为 $O(1)$。pop 和 peek 的均摊时间复杂度为 $O(1)$。虽然单次倒腾操作可能需要 $O(N)$ 时间，但每个元素在整个生命周期中最多只会被从 s1 移动到 s2 一次，因此分摊到每次操作上仍然是常数时间。
• 空间复杂度：$O(N)$，其中 $N$ 是队列中的元素数量。两个栈合计存储了所有元素。