Java学习70：使用PriorityQueue

我们知道，Queue是一个先进先出的队列。

现在有一个这样的需求，我们知道在银行办理业务的时候需要排队拿号，这时候我们排队拿的号就是一个队列。但是这时候突然来了个VIP客户（没办法，人家有钱），拿到了号码是V1，于是柜台处理完上一个业务之后下一个本来轮到你的，但是还是叫的V1（很不爽，但是没办法）。现在我们需要实现的就是这样的一个插队的功能。

要实现这个功能，在队列这一知识点中，有一个队列叫优先队列PriorityQueue。

他和Queue的区别就是他的出队的顺序与元素的优先级有关，对PriorityQueue调用remove()或poll()方法，返回的总是优先级最高的元素。

我们还是上一串代码看看这个怎么实现的；
老规矩吧，创建包和文件，我丢一张图放着：

import java.util.PriorityQueue;
import java.util.Queue;

public class Demo10 {
    public static void main(String[] args) {
        Queue<String> q=new PriorityQueue<>();
        // 添加3个元素到队列:
        q.offer("apple");
        q.offer("pear");
        q.offer("banana");
        // 删除顶端元素
        System.out.println(q.poll()); // apple
        System.out.println(q.poll()); // banana
        System.out.println(q.poll()); // pear
        System.out.println(q.poll()); // null,因为队列为空
    }
}

我们看输出的结果，是不是很奇怪，输出的顺序和我们放进去的顺序不是一样的。有木有感觉似曾相识（疯狂暗示Map）。这是因为这个东西吧，内部也自带了一个Compareable接口。

如果我们要放入的元素并没有实现Compareable接口咋办？自己写撒，动手能力这么强，加油奥利给；
我们还是以银行排队的业务来为例子，实现一个PriorityQueue：

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Demo10 {
    public static void main(String[] args) {
        Queue<User> q = new PriorityQueue<>(new UserComparator());
        // 添加3个元素到队列:
        q.offer(new User("Bob", "A1"));
        q.offer(new User("Alice", "A2"));
        q.offer(new User("Boss", "V1"));
        System.out.println(q.poll()); // Boss/V1
        System.out.println(q.poll()); // Bob/A1
        System.out.println(q.poll()); // Alice/A2
        System.out.println(q.poll()); // null,因为队列为空
    }
}

class UserComparator implements Comparator<User> {
    public int compare(User u1, User u2) {
        if (u1.number.charAt(0) == u2.number.charAt(0)) {
            // 如果两人的号都是A开头或者都是V开头,比较号的大小:
            return u1.number.compareTo(u2.number);
        }
        if (u1.number.charAt(0) == 'V') {
            // u1的号码是V开头,优先级高:
            return -1;
        } else {
            return 1;
        }
    }
}

class User {
    public final String name;
    public final String number;

    public User(String name, String number) {
        this.name = name;
        this.number = number;
    }

    public String toString() {
        return name + "/" + number;
    }
}

实现PriorityQueue的关键在于提供的UserComparator对象，它负责比较两个元素的大小（较小的在前）。UserComparator总是把V开头的号码优先返回，只有在开头相同的时候，才比较号码大小。

上面的UserComparator的比较逻辑其实还是有问题的，它会把A10排在A2的前面，请尝试修复该错误。

小结
PriorityQueue实现了一个优先队列：从队首获取元素时，总是获取优先级最高的元素。

PriorityQueue默认按元素比较的顺序排序（必须实现Comparable接口），也可以通过Comparator自定义排序算法（元素就不必实现Comparable接口）。

谢谢观看