栈和队列的区别与应用
哪些公司问过
答案要点
- 栈:LIFO,只在栈顶操作;队列:FIFO,队尾入队、队头出队
- 核心操作 push/pop、enqueue/dequeue 都是 O(1)
- 栈的应用:函数调用、括号匹配、表达式求值、撤销、DFS;队列的应用:BFS、任务调度、消息缓冲
- 数组实现队列要用循环队列避免假溢出;链表实现没有这个问题
- C++ STL 的 stack、queue 是容器适配器,默认基于 deque;优先队列用堆实现,按优先级出队
易错点
- 把栈和队列的顺序说反
- 数组实现队列不用循环,造成假溢出
- 不知道 stack、queue 是适配器
- 说不出实际的应用场景
面试官常见追问
- 队列和优先队列有什么区别?
- 数组和链表各有什么优劣?
- 如何用两个栈实现队列?
- 单调栈、单调队列有什么用?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 四则运算表达式求值15 场
- 循环队列(环形缓冲区)的实现14 场
- 最长有效括号12 场
- 滑动窗口最大值与滑动平均滤波12 场
- 有效的括号(栈)11 场
- 实现支持 O(1) 获取最小值的栈9 场
- 单调栈:下一个更大元素与每日温度6 场
- 数据流的中位数(大根堆加小根堆)5 场
- 滑动窗口最大值的单调队列解法4 场
- 用两个栈实现队列(LeetCode 232)4 场