手写实现一个队列
哪些公司问过
答案要点
- 循环数组:head 指向队首,tail 指向队尾下一个空位,下标对容量取模
- 用 size 计数区分队空与队满,或浪费一个槽位
- 入队满时按两倍扩容,从 head 开始顺序拷贝,均摊 O(1)
- 出队判空,取出后置空槽位便于回收,head 后移
- 替代方案:带头尾指针的链表,或两个栈实现(均摊 O(1))
易错点
- 用普通数组出队后整体前移,出队变成 O(n)
- head 等于 tail 时无法区分空和满
- 扩容时直接按下标拷贝,没有从 head 开始按顺序展开
面试官常见追问
- 怎么用两个栈实现队列?
- 如果要支持多线程呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 栈和队列的区别与应用68 场
- 四则运算表达式求值15 场
- 循环队列(环形缓冲区)的实现14 场
- 最长有效括号12 场
- 滑动窗口最大值与滑动平均滤波12 场
- 有效的括号(栈)11 场
- 实现支持 O(1) 获取最小值的栈9 场
- 单调栈:下一个更大元素与每日温度6 场
- 数据流的中位数(大根堆加小根堆)5 场
- 滑动窗口最大值的单调队列解法4 场