Interview
队列与栈
队列与栈
介绍
栈和队列是两种最基础的线性数据结构，区别在于元素的进出顺序：
- 栈 (Stack)：后进先出（LIFO）— 最后放进去的最先拿出来
- 队列 (Queue)：先进先出（FIFO）— 先放进去的先拿出来
选择哪个取决于问题的处理顺序：需要”倒回去”用栈，需要”按顺序”用队列。
模式识别
当你看到这些信号：
- “括号匹配”、“撤销操作”、“逆序处理”、“DFS” → 栈
- “按层遍历”、“FIFO 顺序”、“BFS”、“滑动窗口极值” → 队列
- “需要最小/最大值优先处理” → 优先队列 (PriorityQueue)
Stack
LIFO — Last In, First Out。适合需要回溯、撤销、括号匹配、DFS 等场景。
Java 常用方法
Stack<E> stack = new Stack<>();
E push(E item) // push onto top
E pop() // remove and return top (throws if empty)
E peek() // look at top without removing
boolean empty() // check if empty
int search(Object) // 1-based position from top, -1 if not foundNote：
Stack继承自Vector（线程安全，有性能开销）。单线程场景推荐用Deque接口的ArrayDeque实现：Deque<E> stack = new ArrayDeque<>();，方法为push()、pop()、peek()。
常见用例
- 括号匹配：左括号入栈，右括号出现时弹出栈顶检查是否匹配
- DFS 非递归实现：用栈代替递归（见 Tree & DFS 章节）
- 逆序处理：先入栈再依次弹出，得到逆序
Queue
FIFO — First In, First Out。适合按顺序处理、BFS、消息队列等场景。
Java 常用方法
Queue<E> queue = new LinkedList<>();
boolean add(E e) // insert (throws if full)
boolean offer(E e) // insert (returns false if full) — preferred
E poll() // remove and return head (null if empty)
E peek() // look at head without removing (null if empty)
int size()实现类
| 实现类 | 特点 |
|---|---|
LinkedList | 双端队列，同时实现了 Queue 和 Deque |
PriorityQueue | 优先队列，元素按自然顺序或 Comparator 排列 |
ArrayDeque | 双端队列，比 LinkedList 快，推荐用于栈和队列 |
常见用例
- BFS：按层遍历，用队列存储待访问节点（见 Tree & DFS 章节）
- 滑动窗口：维护一个单调队列在 O(n) 时间内找到窗口极值
- 任务调度：FIFO 顺序处理请求
关键技巧
- 栈 = 回溯/倒序，队列 = 按序处理 — 这是选择标准
- DFS 用栈，BFS 用队列 — 两种遍历的本质区别，面试常考
- 用
ArrayDeque代替Stack— 更快，API 更干净，面试官会注意到 poll()vspop()— 队列用 poll（null safe），栈用 pop（throws if empty）- 单调栈/单调队列 — 进阶模式。维护栈/队列内元素单调递增或递减，用于”下一个更大元素”、“滑动窗口最大值”类问题，O(n) 时间