[225][简单][栈][队列] 用队列实现栈

题目描述

225. 用队列实现栈

请你仅使用两个队列实现一个后入先出（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 都保证栈不为空

进阶：你能否实现每种操作的均摊时间复杂度为 O(1) 的栈？换句话说，执行 n 个操作的总时间复杂度 O(n) ，尽管其中某个操作可能需要比其他操作更长的时间。你可以使用两个以上的队列。

解题思路

要把队列模拟成栈, 就要在一个新元素进入队列时, 把之前所有的元素排放在这个新元素之后, 这样在进行队列弹出时, 才能最先把这个新元素弹出, 实现对后进先出栈性质的模拟.

使用一个队列就可以完成这个操作. 在一个新元素进入队列后, 将它之前所有的队列元素出列, 然后重新加入到队列中. 由于每个元素入栈时都会进行这个操作, 可以保证每个新元素都在旧元素之前. 因此队列里元素的顺序是逆转存储的.

这样push操作的时间复杂度是$O(n)$, 其他操作的时间复杂度为$O(1)$.

class MyStack:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.queue = []

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        raw_length = len(self.queue)
        self.queue.append(x)
        for _ in range(raw_length):
            self.queue.append(self.queue.pop(0))

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        return self.queue.pop(0) if self.queue else None

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.queue[0] if self.queue else None

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return not self.queue