Queue整理

队列就是一种特殊的线性表,它只允许在表的头部进行删除操作,在表的尾部进行插入操作。

队列是Java开发中常用的工具,JDK中提供了多种类供我们使用,本文是对这些类的整理。

Queue是JDK中所有队列类的公共接口,它拥有6对方法,分别对应在尾部插入元素、删除头部元素、获取头部元素,但是对于操作失败的处理有所不同:

一类是抛出异常:

  • add(e):插入元素。如果插入成功,返回true,否则抛出IllegalStateException异常。
  • remove():删除元素。如果删除成功,返回头部被删除的元素,否则抛出NoSuchElementException异常。
  • element():获取元素。如果队列不为空,返回头部元素,否则抛出NoSuchElementException异常。

一类是返回特殊的值:

  • offer(e):插入元素。如果插入成功,返回true,否则返回false
  • poll():删除元素。如果删除成功,返回头部被删除的元素,否则返回null
  • peek():获取元素。如果队列不为空,返回头部元素,否则返回null

Queue

有多个继承自Queue的接口,分别为BlockingQueueTransferQueueDequeBlockingDeque

下面分不同接口的实现类来分别进行总结。

Queue

直接实现Queue接口的类不多,如下图所示,只有PriorityQueueConcurrentLinkedQueue

Queue

PriorityQueue

PriorityQueue是一个基于堆的有序无界队列,插入到其中的元素经过堆排序形成一个有序的结构,每次删除元素都从堆的顶部删除。

ConcurrentLinkedQueue

ConcurrentLinkedQueue是一个基于链表的无界队列,插入元素时添加到链表的尾部,删除元素时摘除链表的头结点并返回,元素的顺序遵循先进先出原则。ConcurrentLinkedQueue是一个线程安全的类。

BlockingQueue

BlockingQueue又名阻塞队列,它在Queue接口的基础上添加了阻塞操作的方法。即:

  • 当队列满时,队列会阻塞插入元素的线程,直到队列不满
  • 当队列空时,队列会阻塞删除元素的线程,直到队列不空

它添加的方法分为两类:

一类是一直阻塞的方法:

  • put(e):插入元素。如果队列满了,等待队列空出位置。等待过程中如果中断线程,抛出InterruptedException异常。
  • take():删除元素。如果队列为空,等待队列有元素进入。等待过程中如果中断线程,抛出InterruptedException异常。

一类是带有超时的阻塞方法:

  • offer(e, time, unit):插入元素。如果队列满了,等待队列空出位置,或者等待时间超时。如果成功插入元素则返回true,如果等待时间超时则返回false。等待过程中如果中断线程,抛出InterruptedException异常。
  • poll(time, unit):删除元素。如果队列为空,等待队列有元素进入,或者等待时间超时。如果元素删除成功则返回被删除的元素,如果等待时间超时则返回null。等待过程中如果中断线程,抛出InterruptedException异常。

BlockingQueue的实现类如下图所示:

BlockingQueue

ArrayBlockingQueue

ArrayBlockingQueue是一个基于数组的有界阻塞队列,它在新建时需要指定队列的容量。

ArrayBlockingQueue使用Condition信号量来达到阻塞的目的。默认对锁的抢占是非公平的,可以在新建时指定公平锁。

LinkedBlockingQueue

LinkedBlockingQueue是一个基于链表的有界阻塞队列,它的默认容量为Integer.MAX_VALUE,在新建时可以指定容量。

LinkedBlockingQueue对插入和删除两个操作分配了两个锁,降低了这两个操作竞争锁而阻塞线程的概率,提高了执行效率。

DelayQueue

DelayQueue是一个支持延时获取元素的无界阻塞队列。队列中的元素必须实现Delayed接口,在创建元素时可以指定多久才能从队列中获取当前元素,只有在延迟期满时才能从队列中提取元素。

DelayQueue中包含了一个PriorityQueue用于维护元素的顺序。

PriorityBlockingQueue

PriorityBlockingQueue是一个基于堆的有序无界阻塞队列。

PriorityBlockingQueue只使用了一个notEmpty信号量,因为PriorityBlockingQueue是一个无界队列,因此插入元素不需要等待队列不满

SynchronousQueue

SynchronousQueue是一种特殊的队列,队列中不存储元素。put方法会一直阻塞直到有另外的线程调用take方法获取元素,take方法也类似,只有另外的线程调用put方法插入元素take方法才会返回。

SynchronousQueue相当于是一个线程同步工具。

TransferQueue

TransferQueue接口是对SynchronousQueue的一种抽象,它定义了生产者和消费者线程相互阻塞的操作。它定义了几个方法:

  • tryTransfer(e):尝试将元素交给消费者线程
  • transfer(e):一直阻塞,等待将元素交给消费者线程
  • tryTransfer(e, timeout, unit):等待将元素交给消费者线程,一定时间后返回
  • hasWaitingConsumer():判断是否有等待的消费者线程
  • getWaitingConsumerCount():获得消费者线程的数量

TransferQueue

LinkedTransferQueue

LinkedTransferQueueTransferQueue的实现类,它综合了LinkedBlockingQueueSynchronousQueue的功能。LinkedTransferQueue通过CAS保证线程安全性,相比于LinkedBlockingQueue提高了效率。

transfer方法需要等待消费者线程消费元素。put方法判断是否有等待的消费线程,如果有则直接将元素交给消费线程,否则将元素添加到队列中,不会一直等待消费者线程。

Deque

Deque被称为双端队列。和队列相比,双端队列可以在头部和尾部都进行插入和删除操作。它定义了以下方法:

头部操作方法,根据失败操作的处理分为两类:

抛出异常

  • addFirst(e):在头部插入元素,如果队列已满则抛出IllegalStateException异常。
  • removeFirst():在头部删除元素,如果队列为空则抛出NoSuchElementException异常。
  • getFirst():获取头部元素,如果队列为空则抛出NoSuchElementException异常。

返回特殊值

  • offerFirst(e):在头部插入元素,如果插入成功则返回true,队列已满则返回false
  • pollFirst():在头部删除元素,如果队列为空则返回null,否则返回队列头部的元素。
  • peekFirst():获取头部元素,如果队列为空则返回null,否则返回队列头部的元素。

尾部操作方法,根据失败操作的处理分为两类:

抛出异常

  • addLast(e):在尾部插入元素,如果队列已满则抛出IllegalStateException异常。
  • removeLast():在尾部删除元素,如果队列为空则抛出NoSuchElementException异常。
  • getLast():获取尾部元素,如果队列为空则抛出NoSuchElementException异常。

返回特殊值

  • offerLast(e):在尾部插入元素,如果插入成功则返回true,队列已满则返回false
  • pollLast():在尾部删除元素,如果队列为空则返回null,否则返回队列头部的元素。
  • peekLast():获取尾部元素,如果队列为空则返回null,否则返回队列头部的元素。

Queue相比,Deque有几个相等的方法:

Queue中的方法 Deque中相等的方法
add(e) addLast(e)
offer(e) offerLast(e)
remove() removeFirst()
poll() pollFirst()
element() getFirst()
peek() peekFirst()

Stack相比,Deque有几个相等的方法:

Stack中的方法 Deque中相等的方法
push(e) addFirst(e)
pop() removeFirst()
peek() peekFirst()

Deque

ArrayDeque

ArrayDeque是一个基于数组的无界双端队列。

LinkedList

LinkedList是一个基于双向链表的无界双端队列。

ConcurrentLinkedDeque

ConcurrentLinkedDeque是一个基于双向链表的无界双端队列。它是一个线程安全类。

BlockingDeque

BlockingDeque是阻塞双端队列,即队列为空时在队列两端的删除操作都会被阻塞,队列已满时在队列两端的插入操作都会被阻塞。

相比于DequeBlockingDeque定义了一些阻塞方法:

头部操作方法,根据是否有超时时间分为两类:

一直阻塞:

  • putFirst(e):在头部插入元素。如果队列满了,等待队列空出位置。等待过程中如果中断线程,抛出InterruptedException异常。
  • takeFirst():在头部删除元素。如果队列为空,等待队列有元素进入。等待过程中如果中断线程,抛出InterruptedException异常。

超时时间:

  • offerFirst(e, time, unit):在头部插入元素。如果队列满了,等待队列空出位置,或者等待时间超时。如果成功插入元素则返回true,如果等待时间超时则返回false。等待过程中如果中断线程,抛出InterruptedException异常。
  • pollFirst(time, unit):在头部删除元素。如果队列为空,等待队列有元素进入,或者等待时间超时。如果元素删除成功则返回被删除的元素,如果等待时间超时则返回null。等待过程中如果中断线程,抛出InterruptedException异常。

尾部操作方法,根据是否有超时时间分为两类:

一直阻塞:

  • putLast(e):在尾部插入元素。如果队列满了,等待队列空出位置。等待过程中如果中断线程,抛出InterruptedException异常。
  • takeLast():在尾部删除元素。如果队列为空,等待队列有元素进入。等待过程中如果中断线程,抛出InterruptedException异常。

超时时间:

  • offerLast(e, time, unit):在尾部插入元素。如果队列满了,等待队列空出位置,或者等待时间超时。如果成功插入元素则返回true,如果等待时间超时则返回false。等待过程中如果中断线程,抛出InterruptedException异常。
  • pollLast(time, unit):在尾部删除元素。如果队列为空,等待队列有元素进入,或者等待时间超时。如果元素删除成功则返回被删除的元素,如果等待时间超时则返回null。等待过程中如果中断线程,抛出InterruptedException异常。

BlockingDeque

LinkedBlockingDeque

LinkedBlockingDeque是一个基于链表的有界阻塞双端队列。

https://docs.oracle.com/javase/8/docs/api/index.html
https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/BlockingQueue.html
https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/TransferQueue.html
https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/BlockingDeque.html
https://juejin.im/post/6844903657436086285
https://juejin.im/post/6844903662460878861
https://juejin.im/post/6844903600431480840