8.5.1 PriorityQueue实现类

PriorityQueue 会自动排序

PriorityQueue是一个比较标准的队列实现类。之所以说它是比较标准的队列实现,而不是绝对标准的队列实现,是因为**PriorityQueue保存队列元素的顺序并不是按加入队列的顺序,而是按队列元素的大小进行重新排序**。

因此当调用**peek()方法或者poll()方法取出队列中的元素时,并不是取出最先进入队列的元素,而是取出队列中最小的元素**。从这个意义上来看, PriorityQueue已经违反了队列的最基本规则:先进先出(FIFO)。

程序 PriorityQueue用法

下面程序示范了PriorityQueue队列的用法。

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());
    }
}

运行效果:

[-3, 6, 20, 18]
-3
6
18

PriorityQueue的toString()方法没有排序效果

运行上面程序直接输出PriorityQueue集合时,可能看到该队列里的元素并没有很好地按大小进行排序,但这只是受到PriorityQueue的toString方法的返回值的影响。

poll()方法会从小到大将元素移出队列

实际上,程序多次调用PriorityQueue集合对象的poll()方法时,可看到元素按从小到大的顺序”移出队列”.

PriorityQueue中不能加入null

PriorityQueue不允许插入null元素.

自然排序 定制排序

PriorityQueue需要对队列元素进行排序, PriorityQueue的元素有两种排序方式:

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

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