0%

8.5.1 PriorityQueue实现类

发表于 更新于 分类于 ， ，

8.5.1 PriorityQueue实现类

PriorityQueue是一个比较标准的队列实现类。之所以说它是比较标准的队列实现,而不是绝对标准的队列实现,是因为PriorityQueue保存队列元素的顺序并不是按加入队列的顺序,而是按队列元素的大小进行重新排序。因此当调用peek()方法或者poll()方法取出队列中的元素时,并不是取出最先进入队列的元素,而是取出队列中最小的元素。从这个意义上来看, PriorityQueue已经违反了队列的最基本规则:先进先出(FIFO)。下面程序示范了PriorityQueue队列的用法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;

public class PriorityQueueTest
{
	public static void main(String[] args)
	{
		PriorityQueue pq = new PriorityQueue();
		// 下面代码依次向pq中加入四个元素
		pq.offer(6);
		pq.offer(-3);
		pq.offer(20);
		pq.offer(18);
		// 输出pq队列，并不是按元素的加入顺序排列
		System.out.println(pq); // 输出[-3, 6, 20, 18]
		// 访问队列第一个元素，其实就是队列中最小的元素：-3
		System.out.println(pq.poll());
		System.out.println(pq.poll());
		System.out.println(pq.poll());
	}
}

运行效果:

1
2
3
4
[-3, 6, 20, 18]
-3
6
18

运行上面程序直接输出PriorityQueue集合时,可能看到该队列里的元素并没有很好地按大小进行排序,但这只是受到PriorityQueue的toString方法的返回值的影响。实际上,程序多次调用PriorityQueue集合对象的poll()方法时,可看到元素按从小到大的顺序”移出队列”.
PriorityQueue不允许插入null元素,它还需要对队列元素进行排序, PriorityQueue的元素有两种排序方式:

  • 自然排序:采用自然排序的PriorityQueue集合中的元素必须实现了Comparable接口,而且存放的应该是同一个类的多个实例,否则可能导致ClassCastException异常。
  • 定制排序:创建PriorityQueue队列时,传入一个Comparator对象,该对象负责对队列中的所有元素进行排序。采用定制排序时不要求队列元素实现Comparable接口。

PriorityQueue队列对元素的要求与TreeSet对元素的要求基本一致,因此关于使用自然排序和定制排序的详细介绍请参考8.3.3节。

原文链接: 8.5.1 PriorityQueue实现类