队列(Queue)这种数据结构，是”先来先服务”(FIFO)的。 但是有的时候，我们需要对“优先级”高的对象先处理。或者说，我们想在队列中按照我们喜欢的样子排序。
Java 1.5，开始引入了优先队列（PriorityQueue）。
- 继承自 AbstractQueue
- 泛型要实现Java Comparable或使用Comparator比较
- 大小不固定
- 非线程安全的(线程安全的是PriorityBlockingQueue)
简单来说，要使用这个队列，那么放入队列的对象要实现Comparable接口。之后，队列在添加元素的时候，就会根据这个方法，放入合适的位置。取出的时候，会弹出排在最前面的元素。
下面，我们通过一个例子体会一下优先队列的作用和用法。
这个练习题来自HackkerRank：Java Priority Queue
题目要求
学生有token，成绩，名字。每次输入一个命令，如果是“ENTER”，就添加新的学生进来，按照成绩排序放入。如果成绩相同，按照名字字母序放入。如果名字也相同，就按照token放。 如果命令是“SERVED”，就弹出最前面的同学。最后，打印剩下的队列，如果为空，打印“EMPTY”。
输入示例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
12 ENTER John 3.75 50 ENTER Mark 3.8 24 ENTER Shafaet 3.7 35 SERVED SERVED ENTER Samiha 3.85 36 SERVED ENTER Ashley 3.9 42 ENTER Maria 3.6 46 ENTER Anik 3.95 49 ENTER Dan 3.95 50 SERVED |
输出示例
|
1 2 3 4 |
Dan Ashley Shafaet Maria |
我的代码：
|
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; class Student implements Comparable<Student>{ private int token; private String fname; private double cgpa; public Student(int id, String fname, double cgpa) { super(); this.token = id; this.fname = fname; this.cgpa = cgpa; } public int getToken() { return token; } public String getFname() { return fname; } public double getCgpa() { return cgpa; } @Override public String toString() { return this.fname; } @Override public int compareTo(Student student) { int result; if(this.cgpa!=student.getCgpa()){ result = this.cgpa < student.getCgpa() ? 1:-1; }else if(!this.fname.equals(student.getFname())){ result = this.fname.compareTo(student.getFname()); }else{ result = -(this.token - student.getToken()); } return result; } } public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int totalEvents = Integer.parseInt(in.nextLine()); Queue<Student> queue = new PriorityQueue<Student>(); while(totalEvents>0){ String cmd = in.next(); if(cmd.equals("ENTER")){ String name = in.next(); double cgpa = in.nextDouble(); int id = in.nextInt(); queue.add(new Student(id,name,cgpa)); }else if(cmd.equals("SERVED")){ queue.poll(); } totalEvents--; } if(queue.isEmpty()){ System.out.println("EMPTY"); }else{ while (!queue.isEmpty()){ System.out.println(queue.poll()); } } } } |
通过这个例子，可以很好地理解优先队列了。