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

原创
04/22 19:51
阅读数 82

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

 

 

 

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

 

 

 

 

 

 

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

 
 

阻塞

 
 

单端

 
 

 
 

环形数组

 
 

无锁

 
 

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

 

 

参考引用

 

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部