用栈实现队列
Implement Queue using Stacks
本机进度仅保存在当前浏览器
题目描述
请你仅使用两个栈实现先入先出队列，支持 push、pop、peek 操作，且所有操作均摊时间复杂度为 O(1)。
示例：push(1)、push(2)、peek() 返回 1、pop() 返回 1、empty() 返回 false。
解题思路
- 两个栈分工：入栈 inStack 只管进，出栈 outStack 只管出。
- 出栈栈为空时，把入栈栈整体倒灌进出栈栈——顺序恰好被第二次"反转"纠正为先进先出。
- 均摊分析：每个元素一生最多被搬运两次，单次操作看似 O(n)，均摊 O(1)。
参考实现
查看参考实现Python · 建议先自行作答
class MyQueue:
def __init__(self):
self.in_stack = []
self.out_stack = []
def push(self, x):
self.in_stack.append(x)
def _shift(self):
# 出栈为空时倒入全部元素，恢复队列顺序
if not self.out_stack:
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
def pop(self):
self._shift()
return self.out_stack.pop()
def peek(self):
self._shift()
return self.out_stack[-1]
def empty(self):
return not self.in_stack and not self.out_stack