Java Queue

Queue 与 Deque 的区别？

Queue 接口定义了一个单向的队列结构，强调的是按添加顺序依次处理元素，典型操作包括 offer() 添加、poll() 移除头元素、peek() 查看头部元素。

Queue 的实现类如 PriorityQueue 和 LinkedList 等，分别用于优先级调度或通用队列功能。

而 Deque（Double-Ended Queue）接口则是 Queue 的增强版，支持从队列两端进行插入和删除。它既可以作为队列使用（如 addLast() / pollFirst()），也可以模拟栈结构（如 push() / pop()）。

常用实现包括 ArrayDeque 和 LinkedList，其中 ArrayDeque 更适合作为栈或队列，性能优于 Stack 和 LinkedList。Deque 的灵活性使其在数据结构转换、滑动窗口、缓存实现中更为高效。

---

在 Queue 中 poll() 和 remove() 有什么区别？

Queue 接口提供了两种类似的方法用于获取并移除队首元素：poll() 和 remove()。它们的主要区别在于处理空队列的方式。poll() 是更安全的选择，当队列为空时会返回 null，不会中断程序流程，因此适用于生产环境中不确定队列状态的场景。而 remove() 则在队列为空时直接抛出 NoSuchElementException 异常，适用于你确信队列不为空的场合，用于快速暴露逻辑错误。例如：

Queue<String> queue = new LinkedList<>();
queue.offer("A");
queue.poll();      // 返回 "A"
queue.poll();      // 返回 null
queue.remove();    // 抛出 NoSuchElementException

ArrayDeque 与 LinkedList 有什么区别？

两者都实现了 Deque 接口，支持从两端插入与删除元素，常用于实现队列或栈。

ArrayDeque 内部使用可变长数组，支持均摊 O(1) 的插入删除操作，但不允许插入 null 元素，其结构紧凑、缓存命中率高，适合作为栈或队列的高性能实现。

LinkedList 则基于双向链表实现，支持插入 null，功能更灵活，能用于链式遍历、节点插入等复杂结构操作，但在内存占用和指针操作上略显冗余。

此外，ArrayDeque 是在 JDK 1.6 引入的，相较之下更现代，避免了 Stack 的同步开销问题。在仅关注队列或栈性能的场景下，ArrayDeque 通常是首选。

说一说 PriorityQueue

PriorityQueue 是 JDK 1.5 引入的高级队列实现，属于 Queue 接口的一个重要子类。与普通队列（FIFO）不同，PriorityQueue 会根据元素的优先级顺序来决定出队顺序——优先级高的元素会更早被移除。这一特性通过堆（heap）数据结构实现，默认使用小顶堆，即堆顶总是优先级最低（最小值）的元素。其底层由可扩展数组支持，通过元素的"上浮"与"下沉"操作，实现 O(log n) 的插入与删除效率。

默认情况下，元素必须实现 Comparable 接口，PriorityQueue 会根据 compareTo 结果进行自然排序；若构造时提供 Comparator 实例，则可自定义优先级规则。值得注意的是，PriorityQueue 不允许存储 null 元素，也不能添加彼此不可比较的对象，否则会在运行时抛出异常。此外，该类是非线程安全的，若在多线程环境中使用，应考虑通过外部同步或使用线程安全的并发队列（如 PriorityBlockingQueue）。

PriorityQueue 在面试与实战中常用于调度场景、任务优先级处理、Top K 问题、堆排序、图算法（如 Dijkstra）等，是一个典型的"基础数据结构 + 算法应用"结合体，掌握其原理和使用细节非常重要。