LeetCode 232. Implement Queue using Stacks 题解

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]

总结

本题是栈和队列的经典应用问题，主要考察对栈和队列数据结构的理解和使用。通过使用两个栈，我们可以高效地实现队列的所有操作。

双栈的核心思想是：使用两个栈，一个输入栈用于存储新元素，一个输出栈用于存储待出队的元素，当需要出队或查看队首元素时，如果输出栈为空，将输入栈的所有元素转移到输出栈。

这种方法不仅适用于用栈实现队列问题，还可以应用于许多其他需要栈和队列转换的问题。掌握双栈的使用，对于解决这类问题非常重要。