LeetCode 225. Implement Stack using Queues 题解题目描述请你仅使用两个队列实现一个后入先出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双端队列来模拟一个队列 , 只要是标准的队列操作即可。示例 1输入 [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解题思路方法双队列思路使用两个队列一个主队列用于存储元素一个辅助队列用于临时存储元素当需要压入元素时将元素压入辅助队列然后将主队列的所有元素转移到辅助队列最后交换主队列和辅助队列这样主队列的队首元素就是栈顶元素复杂度分析时间复杂度push操作O(n)需要将主队列的所有元素转移到辅助队列pop、top和empty操作O(1)直接操作主队列空间复杂度O(n)需要使用两个队列来存储元素代码实现方法双队列class MyStack: def __init__(self): # 初始化主队列和辅助队列 self.main_queue [] self.aux_queue [] def push(self, x: int) - None: # 将元素压入辅助队列 self.aux_queue.append(x) # 将主队列的所有元素转移到辅助队列 while self.main_queue: self.aux_queue.append(self.main_queue.pop(0)) # 交换主队列和辅助队列 self.main_queue, self.aux_queue self.aux_queue, self.main_queue def pop(self) - int: # 弹出主队列的队首元素 return self.main_queue.pop(0) def top(self) - int: # 返回主队列的队首元素 return self.main_queue[0] def empty(self) - bool: # 检查主队列是否为空 return not self.main_queue测试用例测试用例 1输入[MyStack,push,push,top,pop,empty] [[],[1],[2],[],[],[]]输出[null,null,null,2,2,false]总结本题是栈和队列的经典应用问题主要考察对栈和队列数据结构的理解和使用。通过使用两个队列我们可以高效地实现栈的所有操作。双队列的核心思想是使用两个队列一个主队列用于存储元素一个辅助队列用于临时存储元素当需要压入元素时将元素压入辅助队列然后将主队列的所有元素转移到辅助队列最后交换主队列和辅助队列。这种方法不仅适用于用队列实现栈问题还可以应用于许多其他需要栈和队列转换的问题。掌握双队列的使用对于解决这类问题非常重要。