225. 用队列实现栈

题目链接：225. 用队列实现栈
参考思路：labuladong 栈和队列

题目描述

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

核心思考：单队列自身旋转

与 232. 用栈实现队列 相比，这道题用队列来模拟栈，实际上只需要一个队列就够了。

队列是先进先出（FIFO），栈是后进先出（LIFO）。矛盾在于：队列只能从队头取元素，但栈需要取的是最后进入的元素（即队尾）。

解决方法是：在 pop 时，把队列前面的元素依次取出再放回队尾，相当于让整个队列”旋转”一圈，使得原来的队尾元素转到队头的位置，然后再取出它。

各操作的具体逻辑：

• push(x)：直接将元素加到队尾。同时用变量 top_elem 记录当前队尾元素（即栈顶）。
• top()：直接返回 top_elem。
• pop()：将队列前 n - 2 个元素依次从队头取出并重新放入队尾。此时队头的元素就是新的栈顶，用 top_elem 记录它，然后也把它放到队尾。最后再从队头弹出的就是原来的队尾元素（即要弹出的栈顶）。
• empty()：判断队列是否为空。

解题思路 (Python)

from collections import deque

class MyStack:
    def __init__(self):
        self.q = deque()
        self.top_elem = 0

    # 将元素 x 压入栈顶
    def push(self, x: int) -> None:
        # x 是队列的队尾，是栈的栈顶
        self.q.append(x)
        self.top_elem = x

    # 返回栈顶元素
    def top(self) -> int:
        return self.top_elem

    # 删除栈顶的元素并返回
    def pop(self) -> int:
        size = len(self.q)
        # 留下队尾 2 个元素
        while size > 2:
            self.q.append(self.q.popleft())
            size -= 1
        # 记录新的队尾元素
        self.top_elem = self.q[0]
        self.q.append(self.q.popleft())
        # 删除之前的队尾元素
        return self.q.popleft()

    # 判断栈是否为空
    def empty(self) -> bool:
        return not self.q

复杂度分析

• 时间复杂度：push、top、empty 均为 $O(1)$。pop 为 $O(N)$，其中 $N$ 是队列中的元素数量，因为需要将前 $N - 1$ 个元素旋转一圈。
• 空间复杂度：$O(N)$，存储所有元素所需的队列空间。