快捷搜索:  汽车  科技

java同步队列有哪些?数据结构-队列详解

java同步队列有哪些?数据结构-队列详解Queue 常用方法,如下图所示:2)Queue 方法说明注:为了让读者更直观地理解,上图为精简版的 Queue 类关系图。本文如无特殊说明,内容都是基于 Java 1.8 版本。1)Queue 分类从上图可以看出 Queue 大体可分为以下三类。

各位志同道合的朋友们大家好,我是一个一直在一线互联网踩坑十余年的编码爱好者,现在将我们的各种经验以及架构实战分享出来,如果大家喜欢,就关注我,一起将技术学深学透,我会每一篇分享结束都会预告下一专题

队列(Queue):与栈相对的一种数据结构, 集合(Collection)的一个子类。队列允许在一端进行插入操作,而在另一端进行删除操作的线性表,栈的特点是后进先出,而队列的特点是先进先出。队列的用处很大,比如实现消息队列。

Queue 类关系图,如下图所示:

java同步队列有哪些?数据结构-队列详解(1)

java同步队列有哪些?数据结构-队列详解(2)

注:为了让读者更直观地理解,上图为精简版的 Queue 类关系图。本文如无特殊说明,内容都是基于 Java 1.8 版本。

队列(Queue)

1)Queue 分类

从上图可以看出 Queue 大体可分为以下三类。

  • 双端队列:双端队列(Deque)是 Queue 的子类也是 Queue 的补充类,头部和尾部都支持元素插入和获取。
  • 阻塞队列:阻塞队列指的是在元素操作时(添加或删除),如果没有成功,会阻塞等待执行。例如,当添加元素时,如果队列元素已满,队列会阻塞等待直到有空位时再插入。
  • 非阻塞队列:非阻塞队列和阻塞队列相反,会直接返回操作的结果,而非阻塞等待。双端队列也属于非阻塞队列。

2)Queue 方法说明

Queue 常用方法,如下图所示:

java同步队列有哪些?数据结构-队列详解(3)

java同步队列有哪些?数据结构-队列详解(4)

方法说明:

  • add(E):添加元素到队列尾部,成功返回 true
  • offer(E):添加元素到队列尾部,成功返回 true
  • remove():删除元素,成功返回 true,失败返回 false
  • poll():获取并移除此队列的第一个元素,若队列为空,则返回 null
  • peek():获取但不移除此队列的第一个元素,若队列为空,则返回 null
  • element():获取但不移除此队列的第一个元素,若队列为空,则抛异常

3)Queue 使用实例

Queue<String>linkedList=newLinkedList<>(); linkedList.add("Dog"); linkedList.add("Camel"); linkedList.add("Cat"); while(!linkedList.isEmpty()){ System.out.println(linkedList.poll()); }

java同步队列有哪些?数据结构-队列详解(5)

程序执行结果:

Dog

Camel

Cat

阻塞队列

1)BlockingQueue

BlockingQueue 在 java.util.concurrent 包下,其他阻塞类都实现自 BlockingQueue 接口,BlockingQueue 提供了线程安全的队列访问方式,当向队列中插入数据时,如果队列已满,线程则会阻塞等待队列中元素被取出后再插入;当从队列中取数据时,如果队列为空,则线程会阻塞等待队列中有新元素再获取。

BlockingQueue 核心方法

插入方法:

  • add(E):添加元素到队列尾部,成功返回 true
  • offer(E):添加元素到队列尾部,成功返回 true
  • put(E):将元素插入到队列的尾部,如果该队列已满,则一直阻塞

删除方法:

  • remove(Object):移除指定元素,成功返回 true,失败返回 false
  • poll(): 获取并移除队列的第一个元素,如果队列为空,则返回 null
  • take():获取并移除队列第一个元素,如果没有元素则一直阻塞

检查方法:

  • peek():获取但不移除队列的第一个元素,若队列为空,则返回 null

2)LinkedBlockingQueue

LinkedBlockingQueue 是一个由链表实现的有界阻塞队列,容量默认值为 Integer.MAX_VALUE,也可以自定义容量,建议指定容量大小,默认大小在添加速度大于删除速度情况下有造成内存溢出的风险,LinkedBlockingQueue 是先进先出的方式存储元素。

3)ArrayBlockingQueue

ArrayBlockingQueue 是一个有边界的阻塞队列,它的内部实现是一个数组。它的容量是有限的,我们必须在其初始化的时候指定它的容量大小,容量大小一旦指定就不可改变。

ArrayBlockingQueue 也是先进先出的方式存储数据,ArrayBlockingQueue 内部的阻塞队列是通过重入锁 ReenterLock 和 Condition 条件队列实现的,因此 ArrayBlockingQueue 中的元素存在公平访问与非公平访问的区别,对于公平访问队列,被阻塞的线程可以按照阻塞的先后顺序访问队列,即先阻塞的线程先访问队列。而非公平队列,当队列可用时,阻塞的线程将进入争夺访问资源的竞争中,也就是说谁先抢到谁就执行,没有固定的先后顺序。

示例代码如下:

//默认非公平阻塞队列 ArrayBlockingQueuequeue=newArrayBlockingQueue(6); //公平阻塞队列 ArrayBlockingQueuequeue2=newArrayBlockingQueue(6 true); //ArrayBlockingQueue源码展示 publicArrayBlockingQueue(intcapacity){ this(capacity false); } publicArrayBlockingQueue(intcapacity booleanfair){ if(capacity<=0) thrownewIllegalArgumentException(); this.items=newObject[capacity]; lock=newReentrantLock(fair); notEmpty=lock.newCondition(); notFull=lock.newCondition(); }

java同步队列有哪些?数据结构-队列详解(6)

4)DelayQueue

DelayQueue 是一个支持延时获取元素的无界阻塞队列,队列中的元素必须实现 Delayed 接口,在创建元素时可以指定延迟时间,只有到达了延迟的时间之后,才能获取到该元素。

实现了 Delayed 接口必须重写两个方法 ,getDelay(TimeUnit) 和 compareTo(Delayed),如下代码所示:

classDelayElementimplementsDelayed{ @Override //获取剩余时间 publiclonggetDelay(TimeUnitunit){ //dosomething } @Override //队列里元素的排序依据 publicintcompareTo(Delayedo){ //dosomething } }

java同步队列有哪些?数据结构-队列详解(7)

DelayQueue 使用的完整示例,请参考以下代码:

publicclassDelayTest{ publicstaticvoidmain(String[]args)throwsInterruptedException{ DelayQueuedelayQueue=newDelayQueue(); delayQueue.put(newDelayElement(1000)); delayQueue.put(newDelayElement(3000)); delayQueue.put(newDelayElement(5000)); System.out.println("开始时间:" DateFormat.getDateTimeInstance().format(newDate())); while(!delayQueue.isEmpty()){ System.out.println(delayQueue.take()); } System.out.println("结束时间:" DateFormat.getDateTimeInstance().format(newDate())); } staticclassDelayElementimplementsDelayed{ //延迟截止时间(单面:毫秒) longdelayTime=System.currentTimeMillis(); publicDelayElement(longdelayTime){ this.delayTime=(this.delayTime delayTime); } @Override //获取剩余时间 publiclonggetDelay(TimeUnitunit){ returnunit.convert(delayTime-System.currentTimeMillis() TimeUnit.MILLISECONDS); } @Override //队列里元素的排序依据 publicintcompareTo(Delayedo){ if(this.getDelay(TimeUnit.MILLISECONDS)>o.getDelay(TimeUnit.MILLISECONDS)){ return1; }elseif(this.getDelay(TimeUnit.MILLISECONDS)<o.getDelay(TimeUnit.MILLISECONDS)){ return-1; }else{ return0; } } @Override publicStringtoString(){ returnDateFormat.getDateTimeInstance().format(newDate(delayTime)); } } }

java同步队列有哪些?数据结构-队列详解(8)

程序执行结果:

开始时间:2019-6-13 20:40:38

2019-6-13 20:40:39

2019-6-13 20:40:41

2019-6-13 20:40:43

结束时间:2019-6-13 20:40:43

非阻塞队列

ConcurrentLinkedQueue 是一个基于链接节点的无界线程安全队列,它采用先进先出的规则对节点进行排序,当我们添加一个元素的时候,它会添加到队列的尾部;当我们获取一个元素时,它会返回队列头部的元素。

它的入队和出队操作均利用 CAS(Compare And Set)更新,这样允许多个线程并发执行,并且不会因为加锁而阻塞线程,使得并发性能更好。

ConcurrentLinkedQueue 使用示例:

ConcurrentLinkedQueueconcurrentLinkedQueue=newConcurrentLinkedQueue(); concurrentLinkedQueue.add("Dog"); concurrentLinkedQueue.add("Cat"); while(!concurrentLinkedQueue.isEmpty()){ System.out.println(concurrentLinkedQueue.poll()); }

java同步队列有哪些?数据结构-队列详解(9)

执行结果:

Dog

Cat

可以看出不管是阻塞队列还是非阻塞队列,使用方法都是类似的,区别是底层的实现方式。

优先级队列

PriorityQueue 一个基于优先级堆的无界优先级队列。优先级队列的元素按照其自然顺序进行排序,或者根据构造队列时提供的 Comparator 进行排序,具体取决于所使用的构造方法。优先级队列不允许使用 null 元素。

PriorityQueue 代码使用示例:

Queue<Integer>priorityQueue=newPriorityQueue(newComparator<Integer>(){ @Override publicintcompare(Integero1 Integero2){ //非自然排序,数字倒序 returno2-o1; } }); priorityQueue.add(3); priorityQueue.add(1); priorityQueue.add(2); while(!priorityQueue.isEmpty()){ Integeri=priorityQueue.poll(); System.out.println(i); }

java同步队列有哪些?数据结构-队列详解(10)

程序执行的结果是:

3

2

1

PriorityQueue 注意的点:

  • PriorityQueue 是非线程安全的,在多线程情况下可使用 PriorityBlockingQueue 类替代;
  • PriorityQueue 不允许插入 null 元素。

相关面试题

1.ArrayBlockingQueue 和 LinkedBlockingQueue 的区别是什么?

答:ArrayBlockingQueue 和 LinkedBlockingQueue 都实现自阻塞队列 BlockingQueue,它们的区别主要体现在以下几个方面:

  • ArrayBlockingQueue 使用时必须指定容量值,LinkedBlockingQueue 可以不用指定;
  • ArrayBlockingQueue 的最大容量值是使用时指定的,并且指定之后就不允许修改;而 LinkedBlockingQueue 最大的容量为 Integer.MAX_VALUE;
  • ArrayBlockingQueue 数据存储容器是采用数组存储的;而 LinkedBlockingQueue 采用的是 Node 节点存储的。

2.LinkedList 中 add() 和 offer() 有什么关系?

答:add() 和 offer() 都是添加元素到队列尾部。offer 方法是基于 add 方法实现的,Offer 的源码如下:

publicbooleanoffer(Ee){ returnadd(e); }

3.Queue 和 Deque 有什么区别?

答:Queue 属于一般队列,Deque 属于双端队列。一般队列是先进先出,也就是只有先进的才能先出;而双端队列则是两端都能插入和删除元素。

4.LinkedList 属于一般队列还是双端队列?

答:LinkedList 实现了 Deque 属于双端队列,因此拥有 addFirst(E)、addLast(E)、getFirst()、getLast() 等方法。

5.以下说法错误的是?

A:DelayQueue 内部是基于 PriorityQueue 实现的B:PriorityBlockingQueue 不是先进先出的数据存储方式C:LinkedBlockingQueue 默认容量是无限大的D:ArrayBlockingQueue 内部的存储单元是数组,初始化时必须指定队列容量

答:C

题目解析:LinkedBlockingQueue 默认容量是 Integer.MAX_VALUE,并不是无限大的。

6.关于 ArrayBlockingQueue 说法不正确的是?

A:ArrayBlockingQueue 是线程安全的B:ArrayBlockingQueue 元素允许为 nullC:ArrayBlockingQueue 主要应用场景是“生产者-消费者”模型D:ArrayBlockingQueue 必须显示地设置容量

答:B

题目解析:ArrayBlockingQueue 不允许元素为 null,如果添加一个 null 元素,会抛 NullPointerException 异常。

7.以下程序执行的结果是什么?

PriorityQueuepriorityQueue=newPriorityQueue(); priorityQueue.add(null); System.out.println(priorityQueue.size());

java同步队列有哪些?数据结构-队列详解(11)

答:程序执行报错,PriorityQueue 不能插入 null。

8.Java 中常见的阻塞队列有哪些?

答:Java 中常见的阻塞队列如下:

  • ArrayBlockingQueue,由数组结构组成的有界阻塞队列;
  • PriorityBlockingQueue,支持优先级排序的无界阻塞队列;
  • SynchronousQueue,是一个不存储元素的阻塞队列,会直接将任务交给消费者,必须等队列中的添加元素被消费后才能继续添加新的元素;
  • LinkedBlockingQueue,由链表结构组成的阻塞队列;
  • DelayQueue,支持延时获取元素的无界阻塞队列。

9.有界队列和无界队列有哪些区别?

答:有界队列和无界队列的区别如下。

  • 有界队列:有固定大小的队列叫做有界队列,比如:new ArrayBlockingQueue(6),6 就是队列的大小。
  • 无界队列:指的是没有设置固定大小的队列,这些队列的特点是可以直接入列,直到溢出。它们并不是真的无界,它们最大值通常为 Integer.MAX_VALUE,只是平常很少能用到这么大的容量(超过 Integer.MAX_VALUE),因此从使用者的体验上,就相当于 “无界”。

10.如何手动实现一个延迟消息队列?

答:说到延迟消息队列,我们应该可以第一时间想到要使用 DelayQueue 延迟队列来解决这个问题。实现思路,消息队列分为生产者和消费者,生产者用于增加消息,消费者用于获取并消费消息,我们只需要生产者把消息放入到 DelayQueue 队列并设置延迟时间,消费者循环使用 take() 阻塞获取消息即可。完整的实现代码如下:

publicclassCustomDelayQueue{ //消息编号 staticAtomicIntegermessageNO=newAtomicInteger(1); publicstaticvoidmain(String[]args)throwsInterruptedException{ DelayQueue<DelayedElement>delayQueue=newDelayQueue<>(); //生产者1 producer(delayQueue "生产者1"); //生产者2 producer(delayQueue "生产者2"); //消费者 consumer(delayQueue); } //生产者 privatestaticvoidproducer(DelayQueue<DelayedElement>delayQueue Stringname){ newThread(newRunnable(){ @Override publicvoidrun(){ while(true){ //产生1~5秒的随机数 longtime=1000L*(newRandom().nextInt(5) 1); try{ Thread.sleep(time); }catch(InterruptedExceptione){ e.printStackTrace(); } //组合消息体 Stringmessage=String.format("%s,消息编号:%s发送时间:%s延迟:%s秒" name MESSAGENO.getAndIncrement() DateFormat.getDateTimeInstance().format(newDate()) time/1000); //生产消息 delayQueue.put(newDelayedElement(message time)); } } }).start(); } //消费者 privatestaticvoidconsumer(DelayQueue<DelayedElement>delayQueue){ newThread(newRunnable(){ @Override publicvoidrun(){ while(true){ DelayedElementelement=null; try{ //消费消息 element=delayQueue.take(); System.out.println(element); }catch(InterruptedExceptione){ e.printStackTrace(); } } } }).start(); } //延迟队列对象 staticclassDelayedElementimplementsDelayed{ //过期时间(单位:毫秒) longtime=System.currentTimeMillis(); //消息体 Stringmessage; //参数:delayTime延迟时间(单位毫秒) publicDelayedElement(Stringmessage longdelayTime){ this.time =delayTime; this.message=message; } @Override //获取过期时间 publiclonggetDelay(TimeUnitunit){ returnunit.convert(time-System.currentTimeMillis() TimeUnit.MILLISECONDS); } @Override //队列元素排序 publicintcompareTo(Delayedo){ if(this.getDelay(TimeUnit.MILLISECONDS)>o.getDelay(TimeUnit.MILLISECONDS)) return1; elseif(this.getDelay(TimeUnit.MILLISECONDS)<o.getDelay(TimeUnit.MILLISECONDS)) return-1; else return0; } @Override publicStringtoString(){ //打印消息 returnmessage "|执行时间:" DateFormat.getDateTimeInstance().format(newDate()); } } }

java同步队列有哪些?数据结构-队列详解(12)

以上程序支持多生产者,执行的结果如下:

生产者1,消息编号:1 发送时间:2019-6-12 20:38:37 延迟:2 秒 |执行时间:2019-6-12 20:38:39

生产者2,消息编号:2 发送时间:2019-6-12 20:38:37 延迟:2 秒 |执行时间:2019-6-12 20:38:39

生产者1,消息编号:3 发送时间:2019-6-12 20:38:41 延迟:4 秒 |执行时间:2019-6-12 20:38:45

生产者1,消息编号:5 发送时间:2019-6-12 20:38:43 延迟:2 秒 |执行时间:2019-6-12 20:38:45

......

总结

队列(Queue)按照是否阻塞可分为:阻塞队列 BlockingQueue 和 非阻塞队列。其中,双端队列 Deque 也属于非阻塞队列,双端队列除了拥有队列的先进先出的方法之外,还拥有自己独有的方法,如 addFirst()、addLast()、getFirst()、getLast() 等,支持首未插入和删除元素。队列中比较常用的两个队列还有 PriorityQueue(优先级队列)和 DelayQueue(延迟队列),可使用延迟队列来实现延迟消息队列,这也是面试中比较常考的问题之一。需要面试朋友对延迟队列一定要做到心中有数,动手写一个消息队列也是非常有必要的。

下一篇:Java IO 详解

往期精选(全集在wx公号)

分布式数据之缓存技术,一起来揭开其神秘面纱

分布式数据复制技术,今天就教你真正分身术

数据分布方式之哈希与一致性哈希,我就是个神算子

分布式存储系统三要素,掌握这些就离成功不远了

想要设计一个好的分布式系统,必须搞定这个理论

分布式通信技术之发布订阅,干货满满

分布式通信技术之远程调用:RPC

消息队列Broker主从架构详细设计方案,这一篇就搞定主从架构

消息中间件路由中心你会设计吗,不会就来学学

消息队列消息延迟解决方案,跟着做就行了

秒杀系统每秒上万次下单请求,我们该怎么去设计

【分布式技术】分布式系统调度架构之单体调度,非掌握不可

CDN加速技术,作为开发的我们真的不需要懂吗?

烦人的缓存穿透问题,今天教就你如何去解决

分布式缓存高可用方案,我们都是这么干的

每天百万交易的支付系统,生产环境该怎么设置JVM堆内存大小

你的成神之路我已替你铺好,没铺你来捶我

猜您喜欢: