1. 简介

在Java的PriorityQueue中,iterator()方法是一个核心功能。该方法提供了遍历队列中元素的便捷方式。本文将深入探讨*iterator()*方法的功能特性,并通过实际场景演示其有效用法。

2. PriorityQueue 概览

Java中的PriorityQueue是一种基于优先级存储元素的数据结构。其内部使用二叉堆实现——一种树形结构,元素按优先级排列。最高优先级元素位于根节点,子节点继承父节点的优先级。这种结构确保最高优先级元素始终位于队列前端,最低优先级元素位于后端。

PriorityQueue类实现了Queue接口,提供多种操作队列元素的方法,包括iterator()方法。该方法继承自Iterable接口,用于获取集合元素的迭代器。方法签名如下:

public Iterator<E> iterator()

iterator()方法返回队列元素的迭代器,参数类型E指定队列元素类型。该方法不接受任何参数。

3. 迭代器特性

3.1. 快速失败机制

iterator()方法返回的迭代器具有快速失败特性。**若在迭代过程中修改队列(添加或删除元素),将立即抛出ConcurrentModificationException异常**。这确保迭代器始终反映队列的当前状态。

以下代码在获取迭代器后修改了PriorityQueue

PriorityQueue<Integer> numbers = new PriorityQueue<>();
numbers.add(3);
numbers.add(1);
numbers.add(2);

Iterator<Integer> iterator = numbers.iterator();
numbers.add(4);

try {
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
} catch (ConcurrentModificationException e) {
    System.out.println("迭代过程中发生ConcurrentModificationException");
}

程序输出:

迭代过程中发生ConcurrentModificationException

3.2. 遍历顺序

iterator()方法按特定方式遍历堆结构,通常采用层序遍历。这意味着从堆顶开始逐层访问元素。**这种方式访问元素效率高,但可能不产生严格的优先级顺序。

以下示例展示如何使用iterator()遍历PriorityQueue

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

Iterator<Integer> iterator = queue.iterator();
while (iterator.hasNext()) {
    Integer element = iterator.next();
    System.out.println(element);
}

程序输出:

1
3
2

PriorityQueue内部结构如下:

   1
  / \
 3   2

迭代器按层序遍历元素,产生顺序1、3、2。 虽然此顺序保持了堆的基本结构,但未严格遵循优先级顺序。

4. Comparator 接口

某些场景下,我们需要按自定义规则排序PriorityQueue中的元素。这可通过Comparator接口实现。该接口允许定义比较函数,用于队列元素排序。

Comparator接口包含*compare()*方法,接收两个同类型参数并返回整数值。返回值决定队列元素的排序方式。

考虑以下Person类示例,要求按年龄排序。我们创建自定义比较器:

class PersonAgeComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        return p1.age - p2.age; 
    }
}

随后创建自定义排序的PriorityQueue,将PersonAgeComparator实例传入构造函数:

PriorityQueue<Person> priorityQueue = new PriorityQueue<>(new PersonAgeComparator());

priorityQueue.add(new Person("Alice", 25));
priorityQueue.add(new Person("Bob", 30));
priorityQueue.add(new Person("Charlie", 22));

Iterator<Person> iterator = priorityQueue.iterator();

while (iterator.hasNext()) {
    Person person = iterator.next();
    System.out.println("姓名: " + person.name + ", 年龄: " + person.age);
}

程序输出:

姓名: Charlie, 年龄: 22
姓名: Bob, 年龄: 30
姓名: Alice, 年龄: 25

5. 有序检索

即使使用自定义Comparator,前例也未严格按年龄升序显示元素。PriorityQueue的内部结构可能导致直接迭代时出现意外结果。这是因为迭代器采用层序遍历,逐层访问元素,导致迭代顺序与优先级顺序不同。

要确保按优先级顺序检索元素,可使用poll()方法。该方法移除并返回PriorityQueue中最高优先级元素(本例中为最小年龄)。

使用*poll()*方法按顺序检索元素:

while (!priorityQueue.isEmpty()) {
    Person person = priorityQueue.poll();
    System.out.println("姓名: " + person.name + ", 年龄: " + person.age);
}

程序输出:

姓名: Charlie, 年龄: 22
姓名: Alice, 年龄: 25
姓名: Bob, 年龄: 30

6. 使用场景

虽然iterator()不适合严格有序检索,但在优先级顺序无关紧要的场景中表现出色——例如将PriorityQueue中的人名转为大写,或计算平均年龄等统计信息(无需考虑优先级)。以下示例说明其用法:

while (iterator.hasNext()) {
    Person person = iterator.next();
    person.setName(person.getName().toUpperCase());
}

7. 总结

本文深入探讨了Java中的PriorityQueue类,重点分析了iterator()方法的作用。需注意:虽然PriorityQueue内部保持有序,但*iterator()方法不保证按该顺序遍历。因此,iterator()*方法适用于不依赖优先级顺序的操作。

完整代码示例可在GitHub获取。


原始标题:PriorityQueue iterator() Method in Java | Baeldung