用队列实现栈

难度: Easy

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

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

Submission

运行时间: 16 ms

内存: 16.2 MB

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 not self.q1



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

Explain

该题解使用两个队列q1和q2来模拟栈的操作。push操作时，新元素总是被添加到q2中，然后将q1中所有元素依次出队并添加到q2，最后交换q1和q2。这样做使得q1始终保持栈的顺序，最后入队的元素在队首。pop和top操作直接对q1进行，分别通过popleft()和访问下标0实现。empty操作判断q1是否为空即可。

时间复杂度: O(n)

空间复杂度: O(n)

class MyStack:

    def __init__(self):
        # 初始化两个队列q1和q2
        self.q1 = deque()
        self.q2 = deque()
        

    def push(self, x: int) -> None:
        # 新元素入队q2
        self.q2.append(x)
        # 将q1所有元素依次出队并添加到q2
        while self.q1:
            self.q2.append(self.q1.popleft())
        # 交换q1和q2，保证q1为栈顶
        self.q1, self.q2 = self.q2, self.q1


    def pop(self) -> int:
        # 移除并返回q1队首元素，即栈顶
        return self.q1.popleft()


    def top(self) -> int:
        # 返回q1队首元素，即栈顶
        return self.q1[0]


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

Explore

在`push`操作中，将所有元素从`q1`移动到`q2`，然后交换`q1`和`q2`的目的是为了保持栈的后入先出（LIFO）特性。通过将新元素加入空的`q2`，然后把`q1`的元素依次加到`q2`，新元素就位于`q1`（经过交换后）的队首，这样就模拟了栈的顶部。即使队列是先入先出（FIFO）的，通过这种方式可以使得最后入队的元素在队首，从而实现栈的操作特性。

在这种实现中，`pop`操作不需要额外的处理来保持栈的后入先出特性。这是因为在`push`操作中已经通过元素的重新排列（移动到`q2`然后交换队列）保证了栈顶元素始终位于`q1`的队首。因此，每次`pop`操作只需要移除并返回`q1`的队首元素，这个元素就是最后被推入栈的元素。

在`top`和`pop`操作中，如果`q1`为空，则表明栈内没有元素可供操作，这种情况下应该处理空栈的异常。在实际应用中，可以在进行这些操作前添加检查，如果`q1`为空，可以抛出异常或返回一个特定的错误值。这确保了方法的健壮性，防止对空栈执行无效操作。

选择使用两个队列来实现栈的功能是为了简化每次`push`操作时的元素重排过程。使用两个队列可以明确地将新元素放在队列的前端，模拟栈顶。尽管也可以使用一个队列来实现栈，这通常需要更复杂的操作来维护后入先出的顺序，例如在插入每个新元素时通过循环将队列的元素重新排列到队尾，使新元素可以位于队首。但这种方法在操作上更为复杂且可能效率较低。