使用PriorityQueue

278次阅读

没有评论

共计 2228 个字符，预计需要花费 6 分钟才能阅读完成。

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

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

可以每个人先取一个号，例如：A1、A2、A3……然后，按照号码顺序依次办理，实际上这就是一个Queue。

如果这时来了一个 VIP 客户，他的号码是V1，虽然当前排队的是A10、A11、A12……但是柜台下一个呼叫的客户号码却是V1。

这个时候，我们发现，要实现“VIP 插队”的业务，用 Queue 就不行了，因为 Queue 会严格按 FIFO 的原则取出队首元素。我们需要的是优先队列：PriorityQueue。

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

要使用 PriorityQueue，我们就必须给每个元素定义“优先级”。我们以实际代码为例，先看看PriorityQueue 的行为：

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

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：

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

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;
    }
}