开发者社区> waylau> 正文

【Java数据结构及算法实战】系列007:Java队列01——Queue概述

简介: 列与栈类似,也是一种运算受限的线性表。队列则被限定在表尾进行插入、在表头进行删除,这种数据结构,实现了FIFO(First In First Out,先进先出)或者是LILO(Last In Last Out,后进后出)的方式工作。
+关注继续查看

队列与栈类似,也是一种运算受限的线性表。队列则被限定在表尾进行插入、在表头进行删除,这种数据结构,实现了FIFO(First In First Out,先进先出)或者是LILO(Last In Last Out,后进后出)的方式工作。

 

 

 

下图很形象将队列比作是实现生活中的排队。排在队列前面的总是会最先得到处理,而排在队列后面的总是最后得到处理。

 

 

 

image

 

 

 

1.   队列的基本概念

 

 

 

 

 

在对队列有了基本的认识之后,我们再来看下队列的基本概念。

 

 

 

进行插入操作这一端被称为队尾(tail),相对地,把另一端称为队首(head)。向一个队列插入新元素又称作入队(enqueue)。它是把新元素放到队尾元素的之后,使之成为新的队尾元素。从一个队列中删除元素又称作出队(dequeue)。它是把队首元素删除掉,使其相邻的元素成为新的队首元素。

 

 

 

 

 

 

 

2.   Java对于队列的支持

 

 

 

在Java中,提供了java.util.Queue<E>接口以支持队列。根据实现不同,队列又可以分为以下几种场景。

 

 

 

 

 

2.1.     是否阻塞

 

阻塞是指当队列空时,消费资源是否阻塞;当队列(有界队列)满时,插入数据是否阻塞。

 

 

 

Java提供了java.util.concurrent.BlockingQueue<E>接口以表示阻塞队列。常见的阻塞队列有:

 

 

 

l  ArrayBlockingQueue

 

l  LinkedBlockingQueue

 

l  DelayQueue

 

l  PriorityBlockingQueue

 

l  SynchronousQueue

 

l  LinkedBlockingDeque

 

l  等等

 

2.2.     单端还是双端

 

单端还是双端,相比于单端队列,双端队列可以从队列的两头分别进行入队和出队操作。

 

 

 

Java提供了java.util.Deque<E>接口以表示双端队列。常见的双端队列有:

 

 

 

l  ArrayDeque

 

l  ConcurrentLinkedDeque

 

l  LinkedList

 

l  LinkedBlockingDeque

 

l  等等

 

 

 

2.3.     是否有界

 

 

 

判断一个队列是否有界的依据是,队列在初始化时是否设置了容量。以ArrayBlockingQueue为例,ArrayBlockingQueue在初始化时,强制要求以容量作为构造函数的参数之一,这便是有界的。LinkedList是无界的,队列的长度会随着入队的元素的增多而不断增长。

 

 

 

LinkedBlockingQueue比较特殊,在初始化时可以指定容量也可以不指定容量。当初始化LinkedBlockingQueue指定容量时,是有界队列;当初始化LinkedBlockingQueue未指定容量时,其内部会以Integer.MAX_VALUE值作为容量。当然,因为Integer.MAX_VALUE值非常大,近似无限大,因此LinkedBlockingQueue未指定容量时也可以近似认为是无界队列。

 

 

 

在实际项目中,推荐优先选择使用有界队列。因为无界队列可能产生OOM(Out Of Memory,内存溢出)问题,OOM对系统是致命的。

 

 

 

2.4.     内部数据结构

 

队列的内部数据结构对使用者而言应该是透明的,使用者关注内部数据结构。主要是关注数据结构对业务运行的影响。队列的内部数据结构有数组、链表、堆等,不同数据结构会影响GC、CPU缓存,大长时间运行后,使用链表会产生大量的碎片,对GC造成很大的压力;内存连续的空间,也更有利于CPU缓存的发挥。

 

 

 

根据存储结构的不同,队列还分为以下几种:

 

 

 

l  用顺序表实现的队列称为顺序队列

 

l  用链表实现的队列称为链队列

 

 

 

2.5.     是否无锁

 

加锁的开锁是巨大的,在高并发场景下,无锁的性能一般有锁的数倍。

 

2.6.     其他特殊功能

 

有很多队列都有特殊的功能,来满足特殊的场景。如SynchronousQueue没有缓存用于handoff场景(下文介绍);PriorityQueue、PriorityBlockingQueue支持按优先级入队;DelayedQueue支持延时出队;Disruptor除具有超强的性能外,还支持多消费者复杂的消费模式。

 

 

 

 

 

基于上面的场景,整理了下表最常用的10个队列的实现。

 

 

 

表1-1 最常用的10个队列的实现

                                                                                                                                                                                                                                                                                                

   

队列

   
   

是否阻塞

   
   

单端还是双端

   
   

是否有界

   
   

内部数据结构

   
   

是否无锁

   
   

特殊功能

   
 

ArrayBlockingQueue

 
 

阻塞

 
 

单端

 
 

 
 

数组

 
 

有锁

 
 

NA

 
 

LinkedBlockingQueue

 
 

阻塞

 
 

单端

 
 

 
 

链表

 
 

有锁

 
 

NA

 
 

SynchronousQueue

 
 

阻塞

 
 

单端

 
 

 
 

单一元素

 
 

有锁

 
 

支持HandOff功能;

 
 

LinkedTransferQueue

 
 

阻塞

 
 

单端

 
 

 
 

链表

 
 

有锁

 
 

功能为LinkedBlockingQueue与SynchronousQueue的超集;

 
 

PriorityBlockingQueue

 
 

阻塞

 
 

单端

 
 

 
 

 
 

有锁

 
 

支持优先级队列;

 
 

DelayQueue

 
 

阻塞

 
 

单端

 
 

 
 

 
 

有锁

 
 

支持延时出队;

 
 

LinkedBlockingDeuqe

 
 

阻塞

 
 

双端

 
 

 
 

链表

 
 

有锁

 
 

NA

 
 

ConcurrentLinkedQueue

 
 

非阻塞

 
 

单端

 
 

 
 

链表

 
 

有锁

 
 

NA

 
 

ConcurrentLinkedDeque

 
 

非阻塞

 
 

双端

 
 

 
 

链表

 
 

有锁

 
 

NA

 
 

Disruptor

 
 

阻塞

 
 

单端

 
 

 
 

环形数组

 
 

无锁

 
 

超强性能,支持多种生产者消费者模式;

 

 

参考引用

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Java数据解析---SAX
一、Sax解析 是从头到尾逐行逐个元素读取内容,修改较为不便,但适用于只读的大文档。 Sax采用事件驱动的方式解析文档。简单点说,如同在电影院看电影一样,从头到尾看一遍就完了,不能回退(Dom可来来回回读取) 在看电影的过程中,每遇到一个情节,一段泪水,一次擦肩,你都会调动大脑和神经去接收或...
625 0
Java数据解析之JSON
Java数据解析之JSON文章大纲一、JSON介绍二、常见框架介绍与实战三、Studio中GsonFormat插件使用四、项目源码下载(含参考资料)五、参考文档 一、JSON介绍 简介  JSON 的全称是 JavaScript Object Notation,是一种轻量级的数据交换格 式。
2029 0
【Java数据结构】哈希表——学习笔记
概念、哈希冲突的概念、对于哈希冲突的理解、如何避免哈希冲突——哈希函数设计、、如何避免哈希冲突——负载因子调节、如何解决哈希冲突、解决冲突——闭散列、解决冲突——开散列/哈希桶、冲突严重时的解决办法、Hash桶实现HashMap、性能分析、哈希表和Java类集的关系
30 0
【Java数据结构及算法实战】系列011:数组实现的优先级队列PriorityQueue
【Java数据结构及算法实战】系列011:数组实现的优先级队列PriorityQueue
22 0
《机器学习实战》决策树(ID3算法)的分析与实现
============================================================================================ 《机器学习实战》系列博客是博主阅读《机器学习实战》这本书的笔记,包含对其中算法的理解和算法的Pyt...
985 0
机器学习实战:K近邻算法(源码分析)
学习机器学习的总结: 先把代码放到这儿,话说一句一句看着打真的好累,还好可以通过debug一步一步观察变量,理解顿时快了许多。
1056 0
非阻塞同步算法实战(二):BoundlessCyclicBarrier
相比上一篇而言,本文不需要太多的准备知识,但技巧性更强一些。因为分析、设计的过程比较复杂繁琐,也限于篇幅,所以,主要展示如何解决这些需求,和讲解代码。另外,所讲的内容也是后一篇实战中需要用到的一个工具类。
96 0
业务实战中经典算法的应用
业务实战中经典算法的应用
80 0
+关注
waylau
大道至简! https://waylau.com/
268
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载