用两个队列实现栈(LeetCode 225)
哪些公司问过
答案要点
- 核心思路:通过转移元素,让最后入队的元素到达队头,从而模拟后进先出
- 方案一:push 直接入队 O(1),pop 时转移前 n-1 个元素到另一队列,O(n)
- 方案二:push 时新元素入空队列并把旧元素全部转移过来,push O(n),pop/top O(1)
- 单队列也可实现:push 后把前 size-1 个元素循环出队再入队
- 根据读写比例选方案,并处理空栈时的 pop 与 top
易错点
- 转移完元素后忘记交换两个队列的角色,导致下次操作用错队列
- 把方案一的 pop 说成均摊 O(1),它每次都是 O(n)
- 使用了队列不支持的操作,比如从队尾取元素,违背题目限制
面试官常见追问
- 怎么用两个栈实现队列?
- 方案一里 top 操作怎么实现?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 栈和队列的区别与应用68 场
- 四则运算表达式求值15 场
- 循环队列(环形缓冲区)的实现14 场
- 最长有效括号12 场
- 滑动窗口最大值与滑动平均滤波12 场
- 有效的括号(栈)11 场
- 实现支持 O(1) 获取最小值的栈9 场
- 单调栈:下一个更大元素与每日温度6 场
- 数据流的中位数(大根堆加小根堆)5 场
- 滑动窗口最大值的单调队列解法4 场