如何实现双端队列(deque)
哪些公司问过
答案要点
- 两端插入删除都要求 O(1),可用双向链表或循环数组实现
- 双向链表维护头尾指针,用哨兵节点简化边界
- 循环数组用取模移动 head/tail,用 size 或空一格区分空和满
- 循环数组满了扩容并按逻辑顺序拷贝,支持随机访问
- std::deque 是分段连续缓冲区,ArrayDeque 是循环数组
易错点
- 循环数组头部插入时 head-1 没加容量就取模,得到负下标
- 没有区分空和满,导致 head==tail 时判断错误
- 扩容时直接按物理顺序拷贝,打乱了逻辑顺序
面试官常见追问
- 循环数组怎么区分队列空和满?
- std::deque 的底层结构是什么?
- 双端队列有哪些典型应用?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 栈和队列的区别与应用68 场
- 四则运算表达式求值15 场
- 循环队列(环形缓冲区)的实现14 场
- 最长有效括号12 场
- 滑动窗口最大值与滑动平均滤波12 场
- 有效的括号(栈)11 场
- 实现支持 O(1) 获取最小值的栈9 场
- 单调栈:下一个更大元素与每日温度6 场
- 数据流的中位数(大根堆加小根堆)5 场
- 滑动窗口最大值的单调队列解法4 场