Java 容器之 Queue

简介

队列（Queue）是一种先进先出（FIFO）的线性数据结构。Java 中的 Queue 接口位于 java.util 包下，扩展了 Collection 接口，提供了入队、出队、查看队首元素等核心操作。此外，双端队列 Deque 和优先级队列 PriorityQueue 为不同场景提供了更灵活的选择。

Queue 简介

Queue 接口

Queue 接口定义如下：

public interface Queue<E> extends Collection<E> {}

Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。

Queue 扩展了 Collection 的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。

Queue 接口	抛出异常	返回特殊值
插入队尾	add(E e)	offer(E e)
删除队首	remove()	poll()
查询队首元素	element()	peek()

AbstractQueue 抽象类

AbstractQueue 类提供 Queue 接口的核心实现，以最大限度地减少实现 Queue 接口所需的工作。

AbstractQueue 抽象类定义如下：

public abstract class AbstractQueue<E>
    extends AbstractCollection<E>
    implements Queue<E> {}

Deque 接口

Deque 接口是 double ended queue 的缩写，即双端队列。Deque 继承 Queue 接口，并扩展支持在队列的两端插入和删除元素。

所以提供了特定的方法，如:

• 尾部插入时需要的 addLast(e)、offerLast(e)。
• 尾部删除所需要的 removeLast()、pollLast()。

大多数的实现对元素的数量没有限制，但这个接口既支持有容量限制的 deque，也支持没有固定大小限制的。

Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：

Deque 接口	抛出异常	返回特殊值
插入队首	addFirst(E e)	offerFirst(E e)
插入队尾	addLast(E e)	offerLast(E e)
删除队首	removeFirst()	pollFirst()
删除队尾	removeLast()	pollLast()
查询队首元素	getFirst()	peekFirst()
查询队尾元素	getLast()	peekLast()

事实上，Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈。

ArrayDeque

ArrayDeque 是 Deque 的顺序表实现。

ArrayDeque 用一个动态数组实现了栈和队列所需的所有操作。

LinkedList

LinkedList 是 Deque 的链表实现。

示例：

public class LinkedListQueueDemo {

    public static void main(String[] args) {
        //add()和remove()方法在失败的时候会抛出异常(不推荐)
        Queue<String> queue = new LinkedList<>();

        queue.offer("a"); // 入队
        queue.offer("b"); // 入队
        queue.offer("c"); // 入队
        for (String q : queue) {
            System.out.println(q);
        }
        System.out.println("===");
        System.out.println("poll=" + queue.poll()); // 出队
        for (String q : queue) {
            System.out.println(q);
        }
        System.out.println("===");
        System.out.println("element=" + queue.element()); //返回第一个元素
        for (String q : queue) {
            System.out.println(q);
        }
        System.out.println("===");
        System.out.println("peek=" + queue.peek()); //返回第一个元素
        for (String q : queue) {
            System.out.println(q);
        }
    }

}

ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能，但两者有什么区别呢？

• ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
• ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。
• ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。
• ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。

PriorityQueue

PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。

PriorityQueue 类定义如下：

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {}

PriorityQueue 要点：

• PriorityQueue 实现了 Serializable，支持序列化。
• PriorityQueue 类是无界优先级队列。
• PriorityQueue 中的元素根据自然顺序或 Comparator 提供的顺序排序。
• PriorityQueue 不接受 null 值元素。
• PriorityQueue 不是线程安全的。
• PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据
• PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
• PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。

典型应用场景

场景一：消息队列与任务调度

Queue 天然适合用于消息缓冲和任务排队场景：

Queue<Task> taskQueue = new LinkedList<>();
taskQueue.offer(new Task("sendEmail", "user@test.com"));
taskQueue.offer(new Task("generateReport", "monthly"));

// 工作线程消费任务
while (!taskQueue.isEmpty()) {
    Task task = taskQueue.poll();
    task.execute();
}

场景二：BFS 广度优先搜索

在图论和树结构中，Queue 是实现 BFS 算法的核心数据结构：

public List<Integer> bfs(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        result.add(node.val);
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
    return result;
}

场景三：使用 PriorityQueue 实现 Top-K 问题

从海量数据中找出最大/最小的 K 个元素：

// 找出数组中最小的 K 个数
public int[] getLeastNumbers(int[] arr, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a); // 大顶堆
    for (int num : arr) {
        pq.offer(num);
        if (pq.size() > k) pq.poll(); // 维持堆大小为 K
    }
    return pq.stream().mapToInt(Integer::intValue).toArray();
}

场景四：使用 ArrayDeque 实现栈

ArrayDeque 性能优于 Stack 类，是实现 LIFO 栈的推荐选择：

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);
int top = stack.pop(); // 3

最佳实践

1. 优先使用 ArrayDeque 而非 LinkedList：ArrayDeque 基于动态数组实现，在大多数场景下性能更优，内存局部性更好。
2. 使用 offer/poll/peek 而非 add/remove/element：前者在操作失败时返回 null/false，后者抛出异常，更适合生产环境。
3. 注意 PriorityQueue 不保证迭代顺序：只有通过 poll() 才能按优先级顺序获取元素。
4. 多线程场景使用 BlockingQueue：如 ArrayBlockingQueue、LinkedBlockingQueue，它们提供了线程安全的阻塞操作。
5. 避免在 Queue 中存储 null：null 与 poll() 返回 null（表示队列为空）容易混淆。

常见问题

Q1：ArrayDeque 和 LinkedList 实现队列有什么区别？

特性	ArrayDeque	LinkedList
底层结构	动态数组	双链表
内存局部性	好（连续内存）	差（分散节点）
null 元素	不支持	支持
扩容开销	偶发扩容	每次插入分配节点
推荐场景	队列/栈的首选	需要频繁在中间操作时

Q2：PriorityQueue 的线程安全性如何？

PriorityQueue 不是线程安全的。在并发环境下应使用 PriorityBlockingQueue，它提供了线程安全的入队和出队操作。

Q3：Queue 的 offer 和 add 有什么区别？

• offer()：插入失败时返回 false，不抛出异常。
• add()：插入失败时抛出 IllegalStateException。

对于有容量限制的队列（如 ArrayBlockingQueue），推荐使用 offer()。

参考资料

• 解读 Java 并发队列 BlockingQueue
• 《Java 并发编程实战》
• Java Queue 官方文档