class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, node):
        self.stack1.append(node)

    def pop(self):
        if len(self.stack2) == 0:
            # while len(self.stack1) > 0:
            #     self.stack2.append(self.stack1.pop())
            self.stack1.reverse()
            self.stack2 = self.stack1
            self.stack1 = []
        return self.stack2.pop()

题解思路

Python 里栈可以用列表 list 实现。

用两个列表模拟队列：

插入时用栈 1；

弹出时，先把栈 1 的元素挨个弹出到栈 2 中（使用列表的 pop）。这样一来最先进入栈 1 的元素就到了栈 2 的末端，只需要弹出栈 2 的末端元素，对应着队列的先进先出。

关于时间复杂度

插入自然是 O(1)

弹出乍看是 O(n) 的，但实际上每个元素都最多只会插入、弹出栈 2 一次。平均下来，每次弹出元素是 O(1) 的时间复杂度。

吸收

• 一种新的时间复杂度分析思路。
• “把栈 1 的元素挨个弹出到栈 2 中”这一步操作时，Python 可以直接使用 stack1.reverse() 进行列表反转。注意这一步是 in-place 操作，没有返回值。然后把 stack1 赋值给 stack2，stack1 设为空