队列(Queue)这种数据结构，是”先来先服务”(FIFO)的。 但是有的时候，我们需要对“优先级”高的对象先处理。或者说，我们想在队列中按照我们喜欢的样子排序。

Java 1.5，开始引入了优先队列（PriorityQueue）。

简单来说，要使用这个队列，那么放入队列的对象要实现Comparable接口。之后，队列在添加元素的时候，就会根据这个方法，放入合适的位置。取出的时候，会弹出排在最前面的元素。

下面，我们通过一个例子体会一下优先队列的作用和用法。

这个练习题来自HackkerRank：Java Priority Queue

题目要求

学生有token，成绩，名字。每次输入一个命令，如果是“ENTER”，就添加新的学生进来，按照成绩排序放入。如果成绩相同，按照名字字母序放入。如果名字也相同，就按照token放。 如果命令是“SERVED”，就弹出最前面的同学。最后，打印剩下的队列，如果为空，打印“EMPTY”。

输入示例

Java Priority Queue Input

Java

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

输出示例

Java Priority Queue Output

Java

1

2

3

4

Dan

Ashley

Shafaet

Maria

我的代码：

https://www.hackerrank.com/challenges/java-priority-queue 答案

Java

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

            }

        }

    }

}

通过这个例子，可以很好地理解优先队列了。

参考资料

Java优先队列（PriorityQueue）示例