2021-04-16 08:19  阅读(132)
文章分类:Java 零基础入门 文章标签:JavaJava 入门
©  原文作者:廖雪峰的网站 原文地址:https://www.liaoxuefeng.com/

我们知道,Queue是一个先进先出(FIFO)的队列。

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

可以每个人先取一个号,例如:A1A2A3……然后,按照号码顺序依次办理,实际上这就是一个Queue

如果这时来了一个VIP客户,他的号码是V1,虽然当前排队的是A10A11A12……但是柜台下一个呼叫的客户号码却是V1

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

PriorityQueueQueue的区别在于,它的出队顺序与元素的优先级有关,对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;
        }
    }
    

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

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

小结

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

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

点赞(0)
版权归原创作者所有,任何形式转载请联系作者; Java 技术驿站 >> 使用PriorityQueue
上一篇
使用Queue
下一篇
使用Deque