华为 OD 训练营 · 题解精讲
LeetCode232、用栈实现队列
LeetCode232、用栈实现队列 视频地址。
题目描述
请你仅使用两个栈实现先入先出队列。 队列应当支持一般队列支持的所有操作（push、pop、peek、empty）： 实现 MyQueue 类： void push(int x)将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty()如果队列为空，返回 True ；否则，返回 False
题目解析
入队操作 如果是栈的插入操作，那我们可以把元素都先插入到 stackIn 中，也就实现了队列的 入队操作 。 出队操作 当 stackOut 中不为空时，直接操作，此时在 stackOut 中的栈顶元素是最先进入队列的元素，返回该元素即可； 如果 stackOut 为空且 stackIn 不为空，首先需要把 stackIn 中的元素逐个弹出并压入到 stackOut 中，然后返回 stackOut 的栈顶元素即可。
参考代码
参考代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 用栈实现队列 （ LeetCode 232 ）:https://leetcode-cn.com/problems/implement-queue-using-stacks/
class MyQueue:
def __init__(self):
# 一个栈叫做 stackIn，负责进栈操作，相当于队列 queue 中的入队操作
self.stackIn = []
# 一个栈叫做 stackOut，负责出栈操作，相当于队列 queue 中的出队操作
self.stackOut = []
def push(self, x: int) -> None:
# 新添加的元素添加到 stackIn 中
self.stackIn.append(x)
def pop(self) -> int:
# 如果 stackOut 为空，首先需要将 stackIn 中的所有元素添加到 stackOut 中
# 注意 stackIn 是栈，栈的性质是先进后出，后进先出，所以是不断的将 stackIn 中的栈顶元素添加进 stackOut 中
if not self.stackOut:
# 通过 while 循环将 stackIn 中的所有元素都取出
while self.stackIn:
# stackOut 不断的添加 stackIn 的栈顶元素
self.stackOut.append(self.stackIn.pop())
# 此时，stackIn 已经为空，直接「移除」 stackOut 的栈顶元素
return self.stackOut.pop()
def peek(self) -> int:
# peek 和 pop 的区别在于是返回栈顶元素而非删除栈顶元素
# 如果 stackOut 为空，首先需要将 stackIn 中的所有元素添加到 stackOut 中
# 注意 stackIn 是栈，栈的性质是先进后出，后进先出，所以是不断的将 stackIn 中的栈顶元素添加进 stackOut 中
if not self.stackOut:
# 通过 while 循环将 stackIn 中的所有元素都取出
while self.stackIn:
# stackOut 不断的添加 stackIn 的栈顶元素
self.stackOut.append(self.stackIn.pop())
# peek 和 pop 的区别在于是返回栈顶元素而非删除栈顶元素
# 此时，stackIn 已经为空，直接「返回」 stackOut 的栈顶元素
return self.stackOut[-1]
def empty(self) -> bool:
# 队列是否为空，判断 stackIn 和 stackOut 是否同时不存在元素
return not self.stackIn and not self.stackOut