说说队列Queue

蹲厕所的熊 转载请注明原创出处,谢谢!

1、简介

Queue(队列):一种特殊的线性表,它只允许在表的前端(front)进行删除操作,只允许在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。

每个元素总是从队列的rear端进入队列,然后等待该元素之前的所有元素出队之后,当前元素才能出对,遵循先进先出(FIFO)原则。

下面是Queue类的继承关系图:

图中我们可以看到,最上层是Collection接口,Queue满足集合类的所有方法:

add(E e):增加元素;

remove(Object o):删除元素;

clear():清除集合中所有元素;

size():集合元素的大小;

isEmpty():集合是否没有元素;

contains(Object o):集合是否包含元素o。

2、队列

2.1、Queue

Queue:队列的上层接口,提供了插入、删除、获取元素这3种类型的方法,而且对每一种类型都提供了两种方式,先来看看插入方法:

add(E e):插入元素到队尾,插入成功返回true,没有可用空间抛出异常 IllegalStateException。

offer(E e): 插入元素到队尾,插入成功返回true,否则返回false。

add和offer作为插入方法的唯一不同就在于队列满了之后的处理方式。add抛出异常,而offer返回false。

再来看看删除和获取元素方法(和插入方法类似):

remove():获取并移除队首的元素,该方法和poll方法的不同之处在于,如果队列为空该方法会抛出异常,而poll不会。

poll():获取并移除队首的元素,如果队列为空,返回null。

element():获取队列首的元素,该方法和peek方法的不同之处在于,如果队列为空该方法会抛出异常,而peek不会。

peek():获取队列首的元素,如果队列为空,返回null。

如果队列是空,remove和element方法会抛出异常,而poll和peek返回null。

当然,Queue只是单向队列,为了提供更强大的功能,JDK在1.6的时候新增了一个双向队列Deque,用来实现更灵活的队列操作。

2.2、Deque

Deque在Queue的基础上,增加了以下几个方法:

addFirst(E e):在前端插入元素,异常处理和add一样;

addLast(E e):在后端插入元素,和add一样的效果;

offerFirst(E e):在前端插入元素,异常处理和offer一样;

offerLast(E e):在后端插入元素,和offer一样的效果;

removeFirst():移除前端的一个元素,异常处理和remove一样;

removeLast():移除后端的一个元素,和remove一样的效果;

pollFirst():移除前端的一个元素,和poll一样的效果;

pollLast():移除后端的一个元素,异常处理和poll一样;

getFirst():获取前端的一个元素,和element一样的效果;

getLast():获取后端的一个元素,异常处理和element一样;

peekFirst():获取前端的一个元素,和peek一样的效果;

peekLast():获取后端的一个元素,异常处理和peek一样;

removeFirstOccurrence(Object o):从前端开始移除第一个是o的元素;

removeLastOccurrence(Object o):从后端开始移除第一个是o的元素;

push(E e):和addFirst一样的效果;

pop():和removeFirst一样的效果。

可以发现,其实很多方法的效果都是一样的,只不过名字不同。比如Deque为了实现Stack的语义,定义了push和pop两个方法。

3、阻塞队列

3.1、BlockingQueue

BlockingQueue(阻塞队列),在Queue的基础上实现了阻塞等待的功能。它是JDK 1.5中加入的接口,它是指这样的一个队列:当生产者向队列添加元素但队列已满时,生产者会被阻塞;当消费者从队列移除元素但队列为空时,消费者会被阻塞。

先给出BlockingQueue新增的方法:

put(E e):向队尾插入元素。如果队列满了,阻塞等待,直到被中断为止。

boolean offer(E e, long timeout, TimeUnit unit):向队尾插入元素。如果队列满了,阻塞等待timeout个时长,如果到了超时时间还没有空间,抛弃该元素。

take():获取并移除队首的元素。如果队列为空,阻塞等待,直到被中断为止。

poll(long timeout, TimeUnit unit):获取并移除队首的元素。如果队列为空,阻塞等待timeout个时长,如果到了超时时间还没有元素,则返回null。

remainingCapacity():返回在无阻塞的理想情况下(不存在内存或资源约束)此队列能接受的元素数量,如果该队列是无界队列,返回Integer.MAX_VALUE。

drainTo(Collection c):移除此队列中所有可用的元素,并将它们添加到给定 collection 中。

drainTo(Collection c, int maxElements):最多从此队列中移除给定数量的可用元素,并将这些元素添加到给定 collection 中。

BlockingQueue最重要的也就是关于阻塞等待的几个方法,而这几个方法正好可以用来实现生产-消费的模型

从图中我们可以知道实现了BlockingQueue的类有以下几个:

ArrayBlockingQueue:一个由数组结构组成的有界阻塞队列。

LinkedBlockingQueue:一个由链表结构组成的有界阻塞队列。

PriorityBlockingQueue:一个支持优先级排序的无界阻塞队列。

SynchronousQueue:一个不存储元素的阻塞队列。

DelayQueue:一个使用优先级队列实现的无界阻塞队列。

ArrayBlockingQueue

ArrayBlockingQueue是一个用数组实现的有界阻塞队列。此队列按照先进先出(FIFO)的原则对元素进行排序。默认情况下不保证访问者公平的访问队列,所谓公平访问队列是指阻塞的所有生产者线程或消费者线程,当队列可用时,可以按照阻塞的先后顺序访问队列,即先阻塞的生产者线程,可以先往队列里插入元素,先阻塞的消费者线程,可以先从队列里获取元素。通常情况下为了保证公平性会降低吞吐量。我们可以使用以下代码创建一个公平的阻塞队列:

访问者的公平性是使用可重入锁实现的,代码如下:

LinkedBlockingQueue

LinkedBlockingQueue是一个用链表实现的有界阻塞队列。此队列的默认和最大长度为Integer.MAX_VALUE。此队列按照先进先出的原则对元素进行排序。

PriorityBlockingQueue

PriorityBlockingQueue是一个支持优先级的无界队列。默认情况下元素采取自然顺序排列,也可以通过比较器comparator来指定元素的排序规则。元素按照升序排列。

SynchronousQueue

SynchronousQueue是一个不存储元素的阻塞队列。每一个put操作必须等待一个take操作,否则不能继续添加元素。SynchronousQueue可以看成是一个传球手,负责把生产者线程处理的数据直接传递给消费者线程。队列本身并不存储任何元素,非常适合于传递性场景,比如在一个线程中使用的数据,传递给另外一个线程使用,SynchronousQueue的吞吐量高于LinkedBlockingQueue 和 ArrayBlockingQueue。

DelayQueue

DelayQueue是一个支持延时获取元素的无界阻塞队列。队列使用PriorityQueue来实现。队列中的元素必须实现Delayed接口,在创建元素时可以指定多久才能从队列中获取当前元素。只有在延迟期满时才能从队列中提取元素。我们可以将DelayQueue运用在以下应用场景:

缓存系统的设计:可以用DelayQueue保存缓存元素的有效期,使用一个线程循环查询DelayQueue,一旦能从DelayQueue中获取元素时,表示缓存有效期到了。

定时任务调度。使用DelayQueue保存当天将会执行的任务和执行时间,一旦从DelayQueue中获取到任务就开始执行,从比如TimerQueue就是使用DelayQueue实现的。

3.2、BlockingDeque

BlockingDeque(阻塞双端队列)在Deque的基础上实现了双端阻塞等待的功能。和第2节说的类似,BlockingDeque也提供了双端队列该有的阻塞等待方法:

putFirst(E e):在队首插入元素,如果队列满了,阻塞等待,直到被中断为止。

putLast(E e):在队尾插入元素,如果队列满了,阻塞等待,直到被中断为止。

offerFirst(E e, long timeout, TimeUnit unit):向队首插入元素。如果队列满了,阻塞等待timeout个时长,如果到了超时时间还没有空间,抛弃该元素。

offerLast(E e, long timeout, TimeUnit unit):向队尾插入元素。如果队列满了,阻塞等待timeout个时长,如果到了超时时间还没有空间,抛弃该元素。

takeFirst():获取并移除队首的元素。如果队列为空,阻塞等待,直到被中断为止。

takeLast():获取并移除队尾的元素。如果队列为空,阻塞等待,直到被中断为止。

pollFirst(long timeout, TimeUnit unit):获取并移除队首的元素。如果队列为空,阻塞等待timeout个时长,如果到了超时时间还没有元素,则返回null。

pollLast(long timeout, TimeUnit unit):获取并移除队尾的元素。如果队列为空,阻塞等待timeout个时长,如果到了超时时间还没有元素,则返回null。

removeFirstOccurrence(Object o):从队首开始移除第一个和o相等的元素。

removeLastOccurrence(Object o):从队尾开始移除第一个和o相等的元素。

从图中我们可以知道实现了BlockingDeque的类有:

LinkedBlockingDeque:一个由链表结构组成的双向阻塞队列。

3.3、TransferQueue

TransferQueue是JDK 1.7对于并发类库新增加的一个接口,它扩展自BlockingQueue,所以自然保持着阻塞队列的所有特性。

有人这样评价它:TransferQueue是是ConcurrentLinkedQueue、SynchronousQueue (公平模式下)、无界的LinkedBlockingQueues等的超集。

TransferQueue对比与BlockingQueue更强大的一点是,生产者会一直阻塞直到所添加到队列的元素被某一个消费者所消费(不仅仅是添加到队列里就完事)。新添加的transfer方法用来实现这种约束。顾名思义,阻塞就是发生在元素从一个线程transfer到另一个线程的过程中,它有效地实现了元素在线程之间的传递(以建立Java内存模型中的happens-before关系的方式)。

我们来看看该接口提供的标准方法:

tryTransfer(E e):若当前存在一个正在等待获取的消费者线程(使用take()或者poll()函数),使用该方法会即刻转移/传输对象元素e并立即返回true;若不存在,则返回false,并且不进入队列。这是一个不阻塞的操作。

transfer(E e):若当前存在一个正在等待获取的消费者线程,即立刻移交之;否则,会插入当前元素e到队列尾部,并且等待进入阻塞状态,到有消费者线程取走该元素。

tryTransfer(E e, long timeout, TimeUnit unit):若当前存在一个正在等待获取的消费者线程,会立即传输给它;否则将插入元素e到队列尾部,并且等待被消费者线程获取消费掉;若在指定的时间内元素e无法被消费者线程获取,则返回false,同时该元素被移除。

hasWaitingConsumer():判断是否存在消费者线程。

getWaitingConsumerCount():获取所有等待获取元素的消费线程数量。

其实transfer方法在SynchronousQueue的实现中就已存在了,只是没有做为API暴露出来。SynchronousQueue有一个特性:它本身不存在容量,只能进行线程之间的元素传送。SynchronousQueue在执行offer操作时,如果没有其他线程执行poll,则直接返回false.线程之间元素传送正是通过transfer方法完成的。

TransferQueue相比SynchronousQueue用处更广、更好用,因为你可以决定是使用BlockingQueue的方法(例如put方法)还是确保一次传递完成(即transfer方法)。在队列中已有元素的情况下,调用transfer方法,可以确保队列中被传递元素之前的所有元素都能被处理。

从图中我们可以知道实现了TransferQueue的类有:

LinkedTransferQueue:一个由链表结构组成的无界阻塞队列。

好了,队列的API先说到这里,下面我会另起一文重点说说阻塞队列的那些个实现类的原理。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180513G01O6H00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

同媒体快讯

扫码关注腾讯云开发者

领取腾讯云代金券