PriorityQueue是一个基于优先级的无界队列; 本来按照自然顺序排序，或者根据构造队列时提供的 Comparator 进行排序，具体取决于所用的构造方法。- 队列不允许用
null元素，也不允许不能比较的对象(没有实现Comparable接口的对象).
PriorityQueue队列头指的是排序规则最小元素- 初始的容量(实际是一个Object[])，随着不断向优先级队列添加元素，其容量会自动扩容，无需指定容量增加策略
1
2
3
4
5
6
7
8
9
| (I) Iterable
^
(I) Collection
^
(I) Queue (C) AbstractCollection
^ ^
(I) Serializable (C) AbstractQueue
^ ^
(C) PriorityQueue
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| public static void main(String[] args) {
PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
queue.offer(1);
queue.offer(4);
queue.offer(5);
queue.offer(2);
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
PriorityQueue<Student> q = new PriorityQueue<Student>(new Comparator<Student>() {
public int compare(Student o1, Student o2) {
if (o1.getScore() == o2.getScore()){
return o1.getName().compareTo(o2.getName());
}
return o1.getScore() - o2.getScore();
}
});
q.offer(new Student("lei", 100));
q.offer(new Student("kawasaki", 90));
q.offer(new Student("bob", 60));
System.out.println(q.poll());
System.out.println(q.poll());
System.out.println(q.poll());
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| public class Student {
private String name;
private int score;
public Student(String lei, int i) {
this.name = name;
this.score = score;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getScore() {
return score;
}
public void setScore(int score) {
this.score = score;
}
}
|
PriorityQueue优先级规则可以由我们根据具体需求而定制， 方式有2种：
- 添加元素自身实现了Comparable接口，确保元素是可排序的对象
- 如果添加元素没有实现Comparable接口，可以在创建PriorityQueue队列时直接指定比较器
源码
1
2
3
4
5
6
7
| public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {
transient Object[] queue; //队列容器， 默认是11
private int size = 0; //队列长度
private final Comparator<? super E> comparator; //队列比较器， 为null使用自然排序
//....
}
|
此处省略入列源码
从源码上看PriorityQueue的入列操作并没对所有加入的元素进行优先级排序。仅仅保证数组第一个元素是最小的即可
上面源码，当第一个元素出列之后，对剩下的元素再排序，挑选出最小的元素排在数组第一个位置。
通过上面的源码，可以看出PriorityQueue并不是thread-safe的队列，因为offer, poll都没有对队列进行锁定，所以如果要用一个thread-safe的PriorityQueue, 需要额外加锁。
总结
PriorityQueue:
- 是一个无界的，也不是 thread-safe的队列
- 是一种通过数组实现的，并有优先级的队列
- 存储的元素要求必须是可比较的对象， 如果不是就必须明确指定比较器