Queue 和 Deque

Java 中的 Queue 和 Deque 是处理队列、双端队列和栈操作的重要接口。Queue 如 PriorityQueue 提供基于优先级的出队操作，底层是最小堆；而 Deque 支持从两端插入和删除，ArrayDeque 是其高性能实现，适用于栈和双端队列场景。LinkedList 同时实现了 List 和 Deque 接口，但性能不如专用实现。它们都不是线程安全的，适用于单线程或通过同步手段控制并发。

Queue 接口的两套方法（高频面试点）

同一个动作，Queue 都提供两种风格：失败抛异常 vs 失败返回特殊值——面试和源码里来回出现，必须分清：

记忆法：e 开头三兄弟（add/remove/element）脾气硬会抛异常；o/p 开头三兄弟（offer/poll/peek）温和返回 null/false。日常写代码推荐 offer/poll/peek——用返回值判空比捕获异常自然得多。Deque 把这套矩阵在头尾各复制一份（addFirst/offerFirst、removeLast/pollLast……），规则相同。

ArrayDeque —— 高性能双端队列

• 底层结构：循环数组（动态扩容）
• 支持操作：头尾插入、删除、队列 & 栈行为
• 优势：
  • 比 LinkedList 更高效
  • 不允许存 null 元素（避免歧义）
  • 不线程安全（多线程环境需加锁）
• 适合场景：栈、队列、双端队列、缓存队列等

示例用法：

Deque<String> deque = new ArrayDeque<>();
deque.offerFirst("A"); // 头部插入
deque.offerLast("B");  // 尾部插入
deque.pollFirst();     // 头部弹出
deque.pollLast();      // 尾部弹出

类比 C++：std::deque（双端队列）

PriorityQueue —— 优先级队列（最小堆）

• 底层结构：基于 最小堆 的数组实现
• 排序规则：默认按元素的自然顺序（或传入 Comparator）
• 元素特点：允许重复，不允许 null
• 应用场景：定时任务调度、最短路径、Top K 问题等

示例用法：

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(2);
pq.offer(8);
System.out.println(pq.poll()); // 输出 2（最小值）

类比 C++：std::priority_queue（但 Java 默认是最小堆，C++ 是最大堆）

LinkedList —— 多面手（同时是 List + Queue + Deque）

• 既实现了 List 接口，又实现了 Deque 接口
• 适合需要频繁头尾插入删除的双端队列
• 但性能略逊于 ArrayDeque，主要用于兼容性和老代码场景