写点什么

精解四大集合框架:Queue 核心知识总结

用户头像
田维常
关注
发布于: 2020 年 11 月 02 日

关注Java 后端技术全栈”**


回复“面试”获取全套面试资料


Queue 用于模拟队列这种数据结构,队列通常是指“先进先出”(FIFO=first in first out)的容器。新元素插入(offer)到队列的尾部,访问元素(poll)操作会返回队列头部的元素。通常,队列不允许随机访问队列中的元素。



这种结构就相当于我们排队上车,先到的站在前面,先上车,后到的得等前面先上车了再上车。


排队进地铁站

排队打饭

排队买火车票

排队买东西

排队办理银行业务

排队…..



有点中国优良传统的美德的意思。扯远了!!!


Java 中的 Queue 的实现有三种方式:


  • 阻塞队列

  • 非阻塞队列

  • 双向队列


Queue 跟 List、Set 一样,也是继承了 Collection 接口。既然生活中的“排队”都那么多,所以 Queu 的使用场景也是非常多的,很典型的 JDK 自带的线程池中就大量使用了 Queue 来存储任务。


类图 UML



上面只是大致列了这几个场景的。


阻塞队列


阻塞队列是一个可以阻塞的先进先出集合,比如某个线程在空队列获取元素时、或者在已存满队列存储元素时,都会被阻塞。


说白了就是干等着,啥也干不了。排队上车的时候,你就只能一直站在在那里排队,你要是想去上厕所回来你的位置都不见了,还得重新排队。


BlockingQueue 接口常用的实现类如下:


  • ArrayBlockingQueue :基于数组的有界阻塞队列,必须指定大小。

  • LinkedBlockingQueue :基于单链表的无界阻塞队列,不需指定大小。

  • PriorityBlockingQueue :基于最小二叉堆的无界、优先级阻塞队列。

  • DelayQueue:基于延迟、优先级、无界阻塞队列。

  • SynchronousQueue :基于 CAS 的阻塞队列。


常用方法:


  • add():新增一个元索,假如队列已满,则抛异常。

  • offer():新增一个元素,假如队列没满则返回 true,假如队列已满,则返回 false。

  • put():新增一个元素,假如队列满,则阻塞。

  • element():获取队列头部一个元素,假如队列为空,则抛异常。

  • peek():获取队列头部一个元素,假如队列为空,则返回 null。

  • remove():执行删除操作,返回队列头部的元素,假如队列为空,则抛异常。

  • poll():执行删除操作,返回队列头部的元素,假如队列为空,则返回 null。

  • take():执行删除操作,返回队列头部的元素,假如队列为空,则阻塞。


非阻塞队列


非阻塞队列是使用 CAS(compare and set)机制实现,类似 volatile,并发性能好。


人太多了,很多现在开始流行取号,先取个号,看着离我这号太远了,我出去溜达溜达一下再来。


常用的阻塞队列有 PriorityQueue 和 ConcurrentLinkedQueue。


  • PriorityQueue :基于优先级的无界优先级队列

  • ConcurrentLinkedDeque:基于双向链表结构的无界并发队列。


双端队列(Deque)


Deque 是一个既可以在头部操作元素,又可以为尾部操作元素,俗称为双向(双端)队列。Deque 继承自 Queue,Deque 实现类有 LinkedList、 ArrayDeque、ConcurrentLinkedDeque 等等。在将 List 篇的时候,里面就说 LinkedList 是一种双向队列,其实它也是 Deque 的一种实现方式。


(⊙o⊙)…额…尴尬了,双向队列生活场景没想出来,留言区谁能帮我补充一下吗?蟹蟹


常用双向对垒的实现类有:


  • LinkedList:基于单链表的无界双端队列,允许元素为 null。

  • ArrayDeque:基于数组的有界双端队列,不允许 null。不是线程安全的。当作为栈使用时,性能比 Stack 好;当作为队列使用时,性能比 LinkedList 好。


原本打算写详细点,但是发现,一旦写详细了,便又是长篇长篇的了。还是慢慢来,步子迈大了还是有点疼。


用户头像

田维常

关注

关注公众号:Java后端技术全栈,领500G资料 2020.10.24 加入

关注公众号:Java后端技术全栈,领500G资料

评论

发布
暂无评论
精解四大集合框架:Queue核心知识总结