PriorityQueue和PriorityBlockingQueue

Stella981
• 阅读 398

点击上方的****蓝字关注我吧

程序那些事

简介

Queue一般来说都是FIFO的,当然之前我们也介绍过Deque可以做为栈来使用。今天我们介绍一种PriorityQueue,可以按照对象的自然顺序或者自定义顺序在Queue中进行排序。

PriorityQueue

先看PriorityQueue,这个Queue继承自AbstractQueue,是非线程安全的。

PriorityQueue的容量是unbounded的,也就是说它没有容量大小的限制,所以你可以无限添加元素,如果添加的太多,最后会报OutOfMemoryError异常。

这里教大家一个识别的技能,只要集合类中带有CAPACITY的,其底层实现大部分都是数组,因为只有数组才有capacity,当然也有例外,比如LinkedBlockingDeque。

只要集合类中带有comparator的,那么这个集合一定是个有序集合。

我们看下PriorityQueue:

private static final int DEFAULT_INITIAL_CAPACITY = 11;
private final Comparator<? super E> comparator;

定义了初始Capacity和comparator,那么PriorityQueue的底层实现就是Array,并且它是一个有序集合。

有序集合默认情况下是按照natural ordering来排序的,如果你传入了 Comparator,则会按照你指定的方式进行排序,我们看两个排序的例子:

@Slf4j

public class PriorityQueueUsage {

   @Test
   public void usePriorityQueue(){
       PriorityQueue integerQueue = new PriorityQueue<>();

       integerQueue.add(1);
       integerQueue.add(3);
       integerQueue.add(2);

       int first = integerQueue.poll();
       int second = integerQueue.poll();
       int third = integerQueue.poll();

       log.info("{},{},{}",first,second,third);
   }

   @Test
   public void usePriorityQueueWithComparator(){
       PriorityQueue integerQueue = new PriorityQueue<>((a,b)-> b-a);
       integerQueue.add(1);
       integerQueue.add(3);
       integerQueue.add(2);

       int first = integerQueue.poll();
       int second = integerQueue.poll();
       int third = integerQueue.poll();

       log.info("{},{},{}",first,second,third);
   }}

默认情况下会按照升序排列,第二个例子中我们传入了一个逆序的Comparator,则会按照逆序排列。

PriorityBlockingQueue

PriorityBlockingQueue是一个BlockingQueue,所以它是线程安全的。

我们考虑这样一个问题,如果两个对象的natural ordering或者Comparator的顺序是一样的话,两个对象的顺序还是固定的吗?

出现这种情况,默认顺序是不能确定的,但是我们可以这样封装对象,让对象可以在排序顺序一致的情况下,再按照创建顺序先进先出FIFO的二次排序:

public class FIFOEntry<E extends Comparable<? super E>>
       implements Comparable<FIFOEntry> {
   static final AtomicLong seq = new AtomicLong(0);
   final long seqNum;
   final E entry;
   public FIFOEntry(E entry) {
       seqNum = seq.getAndIncrement();
       this.entry = entry;
   }
   public E getEntry() { return entry; }
   public int compareTo(FIFOEntry other) {
       int res = entry.compareTo(other.entry);
       if (res == 0 && other.entry != this.entry)
           res = (seqNum < other.seqNum ? -1 : 1);
       return res;
   }}

上面的例子中,先比较两个Entry的natural ordering,如果一致的话,再按照seqNum进行排序。

欢迎关注我的公众号:程序那些事,更多精彩等着您!

更多内容请访问 www.flydean.com

PriorityQueue和PriorityBlockingQueue

微信号 : 程序那些事

● 扫码关注我吧

本文分享自微信公众号 - 程序那些事(flydean-tech)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
九路 九路
2年前
1 手写ArrayList核心源码
手写ArrayList核心源码ArrayList是Java中常用的数据结构,不光有ArrayList,还有LinkedList,HashMap,LinkedHashMap,HashSet,Queue,PriorityQueue等等,我们将手写这些常用的数据结构的核心源码,用尽量少的代码来揭示核心原理。下面我们来手写ArrayList的核心源码首先
cpp加油站 cpp加油站
1年前
【deque容器系列一】基于STL源码分析deque容器整体实现及内存结构
本篇文章基于gcc中stl的源码介绍deque容器的整体实现和它的内存结构。说明一下,我用的是gcc7.1.0编译器,标准库源代码也是这个版本的。首先呢,还是看一下思维导图,如下:1.deque容器整体源码实现介绍deque容器是stl中顺序容器的一种,之前已经介绍过array和vector了,今天介绍deque容器,deque的本质是一个类模板,它的
刚刚好 刚刚好
4个月前
css问题
1、在IOS中图片不显示(给图片加了圆角或者img没有父级)<div<imgsrc""/</divdiv{width:20px;height:20px;borderradius:20px;overflow:h
九路 九路
2年前
4.2 手写Java PriorityQueue 核心源码
上一节介绍了PriorityQueue的原理,先来简单的回顾一下PriorityQueue的原理以最大堆为例来介绍1.PriorityQueue是用一棵完全二叉树实现的。2.不但是棵完全二叉树,而且树中的每个根节点都比它的左右两个孩子节点元素大3.PriorityQueue底层是用数组来保存这棵完全二叉树的。如下图,是一棵最大堆。
晴空闲云 晴空闲云
4个月前
css中box-sizing解放盒子实际宽高计算
我们知道传统的盒子模型,如果增加内边距padding和边框border,那么会撑大整个盒子,造成盒子的宽度不好计算,在实务中特别不方便。boxsizing可以设置盒模型的方式,可以很好的设置固定宽高的盒模型。盒子宽高计算假如我们设置如下盒子:宽度和高度均为200px,那么这会这个盒子实际的宽高就都是200px。但是当我们设置这个盒子的边框和内间距的时候,那
艾木酱 艾木酱
3个月前
快速入门|使用MemFire Cloud构建React Native应用程序
MemFireCloud是一款提供云数据库,用户可以创建云数据库,并对数据库进行管理,还可以对数据库进行备份操作。它还提供后端即服务,用户可以在1分钟内新建一个应用,使用自动生成的API和SDK,访问云数据库、对象存储、用户认证与授权等功能,可专
Wesley13 Wesley13
1年前
Java并发新构件之PriorityBlockingQueue
AnunboundedblockingqueuethatusesthesameorderingrulesasclassPriorityQueueandsuppliesblockingretrievaloperations. Whilethisqueueislogicallyunbounded,attemp
Stella981 Stella981
1年前
JVM中的Safepoints
点击上方的蓝字关注我吧_程序那些事_!(https://oscimg.oschina.net/oscnet/dc95e4f667570fbf4dae8b47e7e7e537d65.gif)简介java程序员都听说过GC,大家也都知道GC的目的是扫描堆空间,然后将那些标记为删除的对象从堆空间释放,以提升可用的
Wesley13 Wesley13
1年前
java优先队列PriorityQueue修改队列内元素排序问题
今天发现了新大陆。我以前一直以为,PriorityQueue队列是基于堆排序的不断更新排序的,没错,它是不断更新排序的。但是前提是要插入(删除)数据,如果仅仅是修改已经稳定队列的值或内容,而不进行插入或者删除,那么,这个顺序是不会变的。举个例子:importjava.util.Comparator;i
Wesley13 Wesley13
1年前
ABA问题的本质及其解决办法
点击上方的蓝字关注我吧_程序那些事_简介CAS的全称是compareandswap,它是java同步类的基础,java.util.concurrent中的同步类基本上都是使用CAS来实现其原子性的。CAS的原理其实很简单,为了保证在多线程环境下我们的更新是符合预期的,或者说一个线程在更新某个对象的时
helloworld_28799839 helloworld_28799839
4个月前
常用知识整理
Javascript判断对象是否为空jsObject.keys(myObject).length0经常使用的三元运算我们经常遇到处理表格列状态字段如status的时候可以用到vue