使用PriorityQueue
在银行柜台办业务时,我们假设只有一个柜台在办理业务,但是办理业务的人很多,怎么办?
可以每个人先取一个号,例如:A1
、A2
、A3
……然后,按照号码顺序依次办理,实际上这就是一个Queue
。
如果这时来了一个VIP客户,他的号码是V1
,虽然当前排队的是A10
、A11
、A12
……但是柜台下一个呼叫的客户号码却是V1
。
这个时候,我们发现,要实现“VIP插队”的业务,用Queue
就不行了,因为Queue
会严格按FIFO的原则取出队首元素。我们需要的是优先队列:PriorityQueue
。
要使用PriorityQueue
,我们就必须给每个元素定义“优先级”。我们以实际代码为例,先看看PriorityQueue
的行为:
我们放入的顺序是"apple"
、"pear"
、"banana"
,但是取出的顺序却是"apple"
、"banana"
、"pear"
,这是因为从字符串的排序看,"apple"
排在最前面,"pear"
排在最后面。
因此,放入PriorityQueue
的元素,必须实现Comparable
接口,会根据元素的排序顺序决定出队的优先级。
实现PriorityQueue
的关键在于提供的UserComparator
对象,它负责比较两个元素的大小(较小的在前)。UserComparator
总是把V
开头的号码优先返回,只有在开头相同的时候,才比较号码大小。
上面的UserComparator
的比较逻辑其实还是有问题的,它会把A10
排在A2
的前面,请尝试修复该错误。
PriorityQueue
实现了一个优先队列:从队首获取元素时,总是获取优先级最高的元素。