Java集合 使用PriorityQueue
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Java集合 使用PriorityQueue,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3089字,纯文字阅读大概需要5分钟。
内容图文
![Java集合 使用PriorityQueue](/upload/InfoBanner/zyjiaocheng/603/4e44496061a642e4a4132f45b5c1dd6a.jpg)
转载:https://www.liaoxuefeng.com/wiki/1252599548343744/1265120632401152
我们知道,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; } }
实现PriorityQueue
的关键在于提供的UserComparator
对象,它负责比较两个元素的大小(较小的在前)。UserComparator
总是把V
开头的号码优先返回,只有在开头相同的时候,才比较号码大小。
上面的UserComparator
的比较逻辑其实还是有问题的,它会把A10
排在A2
的前面,请尝试修复该错误。
小结
PriorityQueue
实现了一个优先队列:从队首获取元素时,总是获取优先级最高的元素。
PriorityQueue
默认按元素比较的顺序排序(必须实现Comparable
接口),也可以通过Comparator
自定义排序算法(元素就不必实现Comparable
接口)。
内容总结
以上是互联网集市为您收集整理的Java集合 使用PriorityQueue全部内容,希望文章能够帮你解决Java集合 使用PriorityQueue所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。