Java Queue 教程

Jakob Jenkov 2020-04-20

Java 的 Queue 接口（java.util.Queue）表示一种数据结构，其设计目标是将元素插入队列尾部，并从队列头部移除元素。这与超市排队的机制类似。

Java 的 Queue 接口是 Java Collection 接口的子类型。它和 Java List 一样，表示一个有序的对象序列，但其预期用途略有不同。由于 Queue 是 Collection 的子接口，因此 Collection 中的所有方法在 Queue 中也都可用。

Java Queue 的实现类

由于 Queue 是一个接口，你需要实例化一个具体的实现类才能使用它。在 Java Collections API 中，你可以选择以下 Queue 实现：

• java.util.LinkedList
• java.util.PriorityQueue

LinkedList 是一个标准的队列实现。队列中的元素在内部以标准的链表结构存储。这使得在列表尾部（tail）插入元素和在列表头部（head）删除元素都非常高效。

PriorityQueue 则根据元素的自然顺序（如果它们实现了 Comparable 接口），或者根据传入 PriorityQueue 的 Comparator 对象来内部存储元素。

此外，java.util.concurrent 包中也提供了其他 Queue 实现，但本教程暂不涉及并发工具类。

以下是创建 Queue 实例的几个示例：

Queue queueA = new LinkedList();
Queue queueB = new PriorityQueue();

在大多数 Queue 实现中，队列的头部（head）和尾部（tail）位于两端。不过，也可以实现一个头尾在同一端的 Queue —— 这就变成了栈（Stack）。

泛型 Queue

默认情况下，你可以向 Queue 中添加任意 Object 类型的对象。但从 Java 5 开始，Java 泛型（Generics）允许你限制可以插入到 Queue 中的对象类型。例如：

Queue<MyObject> queue = new LinkedList<MyObject>();

这个 Queue 现在只能插入 MyObject 类型的实例。这样在访问或遍历元素时就不需要进行强制类型转换。例如：

Queue<MyObject> queue = new LinkedList<MyObject>();
MyObject myObject = queue.remove();

for(MyObject anObject : queue){
    // 对 anObject 执行某些操作...
}

注意第一行代码不需要强制转换，而且 for-each 循环可以直接将每个元素视为 MyObject 实例。这是因为该 Queue 在创建时指定了泛型类型为 MyObject。

建议：如果你知道队列中要存放的类型，请始终为 Queue 指定泛型类型。这有助于 Java 编译器进行类型检查、编写更简洁的代码，并帮助其他阅读你代码的人快速理解队列中包含的对象类型。更多关于 Java 泛型的信息，请参阅 Java 泛型教程。

向队列中添加元素

Java Queue 接口提供了两个方法用于向队列中添加元素：add() 和 offer()。这两个方法都会将元素添加到队列尾部。它们的区别在于当队列已满、无法再添加元素时的行为：

• add() 方法会抛出异常；
• offer() 方法则返回 false。

以下是使用 add() 和 offer() 方法向 Queue 添加元素的示例：

Queue<String> queue = new LinkedList<>();
queue.add("element 1");
queue.offer("element 2");

从队列中取出元素

要从 Java Queue 中取出元素，可以调用 poll() 或 remove() 方法。这两个方法都会移除并返回队列的第一个元素，区别在于队列为空时的行为：

• poll() 方法在队列为空时返回 null；
• remove() 方法在队列为空时抛出异常。

示例如下：

Queue<String> queue = new LinkedList<>();
queue.add("element 1");
queue.add("element 2");

String element1 = queue.poll();   // 返回 "element 1"
String element2 = queue.remove(); // 返回 "element 2"

第一次调用 poll() 会移除队列中的第一个元素 "element 1"；
随后调用 remove() 会移除此时位于队首的 "element 2"。

查看队列头部元素（不移除）

你可以通过 element() 或 peek() 方法查看队列头部的元素而不将其移除。

• element() 方法在队列为空时会抛出 NoSuchElementException 异常；
• peek() 方法在队列为空时返回 null。

示例（使用 element()）：

Queue<String> queue = new LinkedList<>();
queue.add("element 1");
queue.add("element 2");
queue.add("element 3");

String firstElement = queue.element(); // 返回 "element 1"

示例（使用 peek()）：

Queue<String> queue = new LinkedList<>();
queue.add("element 1");
queue.add("element 2");
queue.add("element 3");

String firstElement = queue.peek(); // 返回 "element 1"

从队列中移除元素

要从 Java Queue 中移除元素，可以调用 remove() 方法。该方法会移除队列头部的元素。

示例：

Queue<String> queue = new LinkedList<>();
queue.add("element 0");
queue.add("element 1");

String removedElement = queue.remove(); // 移除并返回 "element 0"

清空队列中的所有元素

你可以使用 clear() 方法清空 Queue 中的所有元素。该方法继承自 Collection 接口。

示例：

queue.clear();

获取队列大小

你可以通过 size() 方法获取 Queue 中当前存储的元素数量。

示例：

Queue<String> queue = new LinkedList<>();
queue.add("element 1");
queue.add("element 2");
queue.add("element 3");

int size = queue.size(); // size = 3

检查队列是否包含某个元素

你可以使用 contains() 方法检查 Queue 是否包含某个特定元素。如果包含则返回 true，否则返回 false。该方法同样继承自 Collection 接口。

示例：

Queue<String> queue = new LinkedList<>();
queue.add("Mazda");

boolean containsMazda = queue.contains("Mazda"); // true
boolean containsHonda = queue.contains("Honda"); // false

遍历队列中的所有元素

你也可以遍历 Queue 中的所有元素，而不仅仅是一次处理一个。以下是两种遍历方式：

使用 Iterator：

Queue<String> queue = new LinkedList<>();
queue.add("element 0");
queue.add("element 1");
queue.add("element 2");

Iterator<String> iterator = queue.iterator();
while(iterator.hasNext()) {
    String element = iterator.next();
    // 对 element 执行某些操作
}

使用增强 for 循环（for-each）：

for(String element : queue) {
    // 对 element 执行某些操作
}

注意：通过 Iterator 或 for-each 循环遍历时，元素的遍历顺序取决于具体的队列实现。

更多细节请查阅 JavaDoc

Queue 接口还有许多其他功能，本文仅聚焦于最常见的操作：添加/移除元素以及遍历元素。如需了解更多细节，请查阅官方 JavaDoc。