Queue

队列遵循 FIFO（First In, First Out），核心操作是尾部入队 offer、头部出队 poll 和查看队首 peek。

实现

• 链表队列：头删尾插均为 $O(1)$，但每个节点有额外指针；
• 循环数组：缓存友好，用 head、tail 和容量管理回绕；
• 双端队列：两端都可插入和删除，可同时模拟队列与栈；
• 优先队列：按优先级而非到达时间出队，通常由堆实现，不是普通 FIFO 队列。

Deque<Integer> queue = new ArrayDeque<>();
queue.offerLast(1);
queue.offerLast(2);
int first = queue.pollFirst();

常见应用

• BFS 与最短无权路径；
• 生产者—消费者和任务调度；
• 滑动窗口中的单调队列；
• 分层遍历、事件流与限速缓冲。

面试中优先使用 ArrayDeque，避免 LinkedList 的对象开销，也不要用 Stack 这个旧类。设计有界队列时还要明确满队列策略：阻塞、拒绝、覆盖还是丢弃。