LeetCode 232. Implement Queue using Stacks 题解题目描述请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty实现MyQueue类void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空返回true否则返回false说明你只能使用标准的栈操作 —— 也就是只有push to top,peek/pop from top,size, 和is empty操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque双端队列来模拟一个栈只要是标准的栈操作即可。示例 1输入 [MyQueue,push,push,peek,pop,empty] [[],[1],[2],[],[],[]] 输出 [null,null,null,1,1,false] 解释 MyQueue myQueue new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false解题思路方法双栈思路使用两个栈一个输入栈用于存储新元素一个输出栈用于存储待出队的元素当需要出队或查看队首元素时如果输出栈为空将输入栈的所有元素转移到输出栈这样输出栈的栈顶元素就是队首元素复杂度分析时间复杂度push操作O(1)直接压入输入栈pop和peek操作均摊 O(1)每个元素最多被转移一次empty操作O(1)检查两个栈是否都为空空间复杂度O(n)需要使用两个栈来存储元素代码实现方法双栈class MyQueue: def __init__(self): # 初始化输入栈和输出栈 self.input_stack [] self.output_stack [] def push(self, x: int) - None: # 将元素压入输入栈 self.input_stack.append(x) def pop(self) - int: # 如果输出栈为空将输入栈的所有元素转移到输出栈 if not self.output_stack: while self.input_stack: self.output_stack.append(self.input_stack.pop()) # 弹出输出栈的栈顶元素 return self.output_stack.pop() def peek(self) - int: # 如果输出栈为空将输入栈的所有元素转移到输出栈 if not self.output_stack: while self.input_stack: self.output_stack.append(self.input_stack.pop()) # 返回输出栈的栈顶元素 return self.output_stack[-1] def empty(self) - bool: # 检查两个栈是否都为空 return not self.input_stack and not self.output_stack测试用例测试用例 1输入[MyQueue,push,push,peek,pop,empty] [[],[1],[2],[],[],[]]输出[null,null,null,1,1,false]总结本题是栈和队列的经典应用问题主要考察对栈和队列数据结构的理解和使用。通过使用两个栈我们可以高效地实现队列的所有操作。双栈的核心思想是使用两个栈一个输入栈用于存储新元素一个输出栈用于存储待出队的元素当需要出队或查看队首元素时如果输出栈为空将输入栈的所有元素转移到输出栈。这种方法不仅适用于用栈实现队列问题还可以应用于许多其他需要栈和队列转换的问题。掌握双栈的使用对于解决这类问题非常重要。