LC232
用栈实现队列
队列 · 双栈可视化:栈与队列用两个栈实现队列,依次 push 1,2,pop 应得 1。
时间 均摊 O(1)空间 O(n)
题目1 / 10
题目与输入建立输入、目标与算法心智
pop 时若 out 空,把 in 全部倒入 out
正在加载算法场景...
当前发生了什么
用两个栈实现队列,依次 push 1,2,pop 应得 1。
机器状态
in 栈、out 栈、待出队元素。
为什么正确
in 栈负责 push;pop/peek 时若 out 空则把 in 全部倒入 out。
不变量
out 栈顶是队头;仅 out 空时才倒 in。
面试怎么说
in/out 双栈:push→in;pop/peek 若 out 空则倒 in;均摊 O(1)。
人类输入
用两个栈实现队列,依次 push 1,2,pop 应得 1。
机制
in 栈负责 push;pop/peek 时若 out 空则把 in 全部倒入 out。
机器状态
in 栈、out 栈、待出队元素。
可观察结果
pop 返回 1,队列 FIFO 成立。
不变量
- · out 栈顶是队头;仅 out 空时才倒 in。
常见误区
- · 每次 pop 都倒 in,均摊失效。
迁移练习
- · LC225 用队列实现栈
- · LC20 有效括号
面试怎么答
in/out 双栈:push→in;pop/peek 若 out 空则倒 in;均摊 O(1)。