蹲厕所的熊

benjaminwhx

说说队列Queue

2018-05-05 作者: 吴海旭


  1. 1、简介
  2. 2、队列
    1. 2.1、Queue
    2. 2.2、Deque
  3. 3、阻塞队列
    1. 3.1、BlockingQueue
      1. ArrayBlockingQueue
      2. LinkedBlockingQueue
      3. PriorityBlockingQueue
      4. SynchronousQueue
      5. DelayQueue
    2. 3.2、BlockingDeque
    3. 3.3、TransferQueue

1、简介

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

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

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

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<? super E> c):移除此队列中所有可用的元素,并将它们添加到给定 collection 中。
  • drainTo(Collection<? super E> c, int maxElements):最多从此队列中移除给定数量的可用元素,并将这些元素添加到给定 collection 中。

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

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

  • ArrayBlockingQueue:一个由数组结构组成的有界阻塞队列。
  • LinkedBlockingQueue:一个由链表结构组成的有界阻塞队列。
  • PriorityBlockingQueue:一个支持优先级排序的无界阻塞队列。
  • SynchronousQueue:一个不存储元素的阻塞队列。
  • DelayQueue:一个使用优先级队列实现的无界阻塞队列。

ArrayBlockingQueue

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

ArrayBlockingQueue fairQueue = new  ArrayBlockingQueue(1000, true);

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

public ArrayBlockingQueue(int capacity, boolean fair) {
    if (capacity <= 0)
        throw new IllegalArgumentException();
    this.items = new Object[capacity];
    lock = new ReentrantLock(fair);
    notEmpty = lock.newCondition();
    notFull =  lock.newCondition();
}

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先说到这里,下面我会另起一文重点说说阻塞队列的那些个实现类的原理。



坚持原创技术分享,您的支持将鼓励我继续创作!



分享

评论