Queue 和 Deque 是 Java 集合框架中用于表达“排队”和“两端操作”的接口。它们不仅能表示普通队列，还能表示双端队列、栈、优先级队列，以及并发中的阻塞队列。

如果 List 强调按位置访问，Queue/Deque 强调的是元素进出的规则。

1. Queue 是什么

Queue 通常表示先进先出，简称 FIFO。

入队 offer
   │
   ▼
tail [C, B, A] head
              │
              ▼
           poll 出队

示例：

Queue<String> queue = new ArrayDeque<>();
queue.offer("A");
queue.offer("B");

System.out.println(queue.poll()); // A
System.out.println(queue.poll()); // B

2. Queue 方法分组

Queue 方法有两套风格：失败时抛异常，或返回特殊值。

操作	抛异常	返回特殊值
入队	add(e)	offer(e)
出队	remove()	poll()
查看队首	element()	peek()

推荐业务代码优先使用返回特殊值的方法：

String task = queue.poll();
if (task != null) {
    process(task);
}

空队列时：

方法	行为
remove()	抛 NoSuchElementException
poll()	返回 null
element()	抛 NoSuchElementException
peek()	返回 null

3. Deque 是什么

Deque 是 double-ended queue，双端队列。它支持从两端插入和删除。

offerFirst             offerLast
    │                     │
    ▼                     ▼
head [A, B, C, D] tail
    ▲                     ▲
 pollFirst             pollLast

示例：

Deque<String> deque = new ArrayDeque<>();
deque.offerFirst("B");
deque.offerFirst("A");
deque.offerLast("C");

System.out.println(deque.pollFirst()); // A
System.out.println(deque.pollLast());  // C

4. Deque 方法

操作	头部	尾部
插入，失败抛异常	addFirst	addLast
插入，失败返回 false	offerFirst	offerLast
删除，失败抛异常	removeFirst	removeLast
删除，失败返回 null	pollFirst	pollLast
查看，失败抛异常	getFirst	getLast
查看，失败返回 null	peekFirst	peekLast

Deque 也提供栈方法：

栈操作	Deque 方法
入栈	push(e)，等价于 addFirst(e)
出栈	pop()，等价于 removeFirst()
查看栈顶	peek()

5. ArrayDeque

ArrayDeque 是基于循环数组的双端队列。

数组：
[_, C, D, _, _, A, B, _]
       ▲           ▲
      tail        head

当头尾移动到数组边界时，会绕回数组另一端。

特点：

特点	说明
头尾操作快	均摊 O(1)
不允许 null	null 用作空返回值标记
内存紧凑	比链表节点更省内存
非线程安全	多线程使用需额外同步

适合：

• 普通队列。
• 栈。
• 双端队列。
• BFS 临时队列。

示例：

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop()); // 2

6. LinkedList 作为队列

LinkedList 也实现了 Deque。

Deque<String> deque = new LinkedList<>();

但它基于链表，每个元素一个节点对象，内存开销较大，缓存局部性较差。

对比：

对比项	ArrayDeque	LinkedList
底层结构	循环数组	双向链表
内存占用	较低	较高
是否允许 null	不允许	允许
作为栈/队列	更推荐	一般

除非必须允许 null 或依赖链表特性，否则栈和队列优先 ArrayDeque。

7. PriorityQueue

PriorityQueue 是优先级队列，出队顺序不是插入顺序，而是优先级顺序。

默认小顶堆：

Queue<Integer> queue = new PriorityQueue<>();
queue.offer(3);
queue.offer(1);
queue.offer(2);

System.out.println(queue.poll()); // 1

结构：

小顶堆：
        1
      /   \
     3     2

自定义优先级：

Queue<Task> queue = new PriorityQueue<>(
        Comparator.comparingInt(Task::getPriority)
);

如果优先级越大越先出：

Queue<Task> queue = new PriorityQueue<>(
        Comparator.comparingInt(Task::getPriority).reversed()
);

8. PriorityQueue 注意点

注意点	说明
不保证整体有序遍历	只有每次 poll 才保证取出当前最小或最大
不允许 null	避免和空队列返回值混淆
非线程安全	并发场景用 PriorityBlockingQueue
比较器必须稳定	比较规则混乱会导致堆语义异常

错误理解：

System.out.println(priorityQueue);

打印结果不一定是排序后的列表。要按优先级取出：

while (!queue.isEmpty()) {
    System.out.println(queue.poll());
}

9. 阻塞队列

并发编程中常用 BlockingQueue，它不只是集合结构，还是线程协作工具。

常见实现：

实现	特点
ArrayBlockingQueue	有界数组阻塞队列
LinkedBlockingQueue	链表阻塞队列，可有界
PriorityBlockingQueue	优先级阻塞队列
DelayQueue	延迟到期后才能取出
SynchronousQueue	不存储元素，直接交接

生产消费模型：

Producer -> put -> BlockingQueue -> take -> Consumer

阻塞队列会在 Java 并发章节详细展开。

10. Queue 选型

需求	推荐
普通 FIFO 队列	ArrayDeque
栈	ArrayDeque
双端队列	ArrayDeque
允许 null 的双端队列	LinkedList
优先级队列	PriorityQueue
多线程生产消费	BlockingQueue
并发优先级队列	PriorityBlockingQueue

11. 常见算法场景

11.1 BFS

Queue<Node> queue = new ArrayDeque<>();
queue.offer(root);

while (!queue.isEmpty()) {
    Node node = queue.poll();
    for (Node child : node.children()) {
        queue.offer(child);
    }
}

11.2 单调队列

滑动窗口最大值等问题常用 Deque 保存候选元素。

窗口移动
  │
  ▼
Deque 保持从大到小
  │
  ▼
队首就是当前最大值

11.3 Top K

使用小顶堆维护最大的 K 个元素：

PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int value : values) {
    heap.offer(value);
    if (heap.size() > k) {
        heap.poll();
    }
}

Tips 快问快答

Q：Queue 和 Deque 最大区别是什么？ A：Queue 通常只操作队尾和队首，Deque 支持两端插入和删除。

Q：为什么推荐 offer/poll/peek？ A：它们失败时返回特殊值，业务代码更容易处理空队列或容量限制。

Q：栈为什么推荐 ArrayDeque 而不是 Stack？ A：Stack 是老类，继承 Vector；ArrayDeque 更现代、轻量。

Q：ArrayDeque 可以放 null 吗？ A：不可以，null 被用于表示某些操作的空返回值。

Q：PriorityQueue 遍历是有序的吗？ A：不保证。只有连续 poll 才按优先级取出。

Q：PriorityQueue 默认大顶堆还是小顶堆？ A：默认小顶堆，即自然顺序最小元素先出。

Q：队列多线程生产消费用什么？ A：使用 BlockingQueue 系列。

Q：LinkedList 适合当队列吗？ A：能用，但多数普通场景 ArrayDeque 更合适。

Q：Top K 常用什么集合？ A：常用 PriorityQueue 维护大小为 K 的堆。

Q：BFS 常用什么队列？ A：普通单线程 BFS 通常用 ArrayDeque。