Java队列 PriorityQueue

 ​

文章目录

• ​​PriorityQueue​​
• ​​小结​​

PriorityQueue

我们知道，​

​Queue​

​是一个先进先出（FIFO）的队列。

在银行柜台办业务时，我们假设只有一个柜台在办理业务，但是办理业务的人很多，怎么办？

可以每个人先取一个号，例如：​

​A1​

​、​

​A2​

​A3​

​……然后，按照号码顺序依次办理，实际上这就是一个​

​Queue​

​。

如果这时来了一个VIP客户，他的号码是​

​V1​

​，虽然当前排队的是​

​A10​

​A11​

​A12​

​……但是柜台下一个呼叫的客户号码却是​

​V1​

这个时候，我们发现，要实现​

​“VIP插队”​

​的业务，用​

​Queue​

​就不行了，因为​

​Queue​

​会严格按FIFO的原则取出队首元素。我们需要的是优先队列：​

​PriorityQueue​

​

​PriorityQueue​

​和​

​Queue​

​的区别在于，它的出队顺序与元素的优先级有关，对​

​PriorityQueue​

​调用​

​remove()​

​或​

​poll()​

​方法，返回的总是优先级最高的元素。

要使用​

​PriorityQueue​

​，我们就必须给每个元素定义“优先级”。我们以实际代码为例，先看看​

​PriorityQueue​

​的行为：

public class Main {
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,因为队列为空
    }
}
      

我们放入的顺序是​

​"apple"​

​"pear"​

​"banana"​

​，但是取出的顺序却是​

​"apple"​

​"banana"​

​"pear"​

​，这是因为从字符串的排序看，​

​"apple"​

​排在最前面，​

​"pear"​

​排在最后面。

因此，放入​

​PriorityQueue​

​的元素，必须实现​

​Comparable​

​接口，​

​PriorityQueue​

​会根据元素的排序顺序决定出队的优先级。

如果我们要放入的元素并没有实现​

​Comparable​

​接口怎么办？​

​PriorityQueue​

​允许我们提供一个​

​Comparator​

​对象来判断两个元素的顺序。我们以银行排队业务为例，实现一个​

​PriorityQueue​

​：

public class Main {
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​

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