博客

1.概述

1.1 Queue

队列是数据结构中比较重要的一种类型（是一种数据结构），它支持

FIFO

，

尾部添加

、

头部删除

（先进队列的元素先出队列），跟我们生活中的排队类似。

队列是一种比较特殊的线性结构。它

只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作

。进行插入操作的端称为队尾，进行删除操作的端称为队头。

有特殊情况吗？比如在前端进行插入操作？有，JDK在1.6的时候新增了一个双向队列Deque，用来实现更灵活的队列操作。比如可以在前端插入数据。

队列中最先插入的元素也将最先被删除，对应的最后插入的元素将最后被删除。因此队列又称为“先进先出”（FIFO—first in first out）的线性表，与栈(FILO-first in last out)刚好相反。

java中的

Queue接口

就实现了队列的功能，Queue接口与List、Set同一级别，都是继承了

Collection接口

。LinkedList虽然是个数组，但是也实现了Queue接口(通过

Deque接口

间接实现)，因此，可以当做Queue来用。

图中我们可以看到，最上层是

Collection接口

，

Queue满足集合类的所有方法，都是非阻塞的

：

add(E e)：增加元素；
remove(Object o)：删除元素；
clear()：清除集合中所有元素；
size()：集合元素的大小；
isEmpty()：集合是否没有元素；
contains(Object o)：集合是否包含元素o。

BlockingQueue接口继承Queue接口，也扩展了一些方法：

put(E e);   //阻塞
take();    //阻塞

知道这个原理，可以帮助我们记忆一些特性，比如辨别是否阻塞方法，那么联想 add(E e)既然是Collection接口定义的，那么一般就是非阻塞的，因为同样的实现Collection接口的ArrayList也是非阻塞的。

1.2 Deque

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

两个方法。

2. 阻塞队列

2.1 BlockingQueue

阻塞队列（BlockingQueue）是一个支持两个附加操作的队列。这两个附加的操作是：在队列为空时，获取元素的线程会等待队列变为非空。当队列满时，存储元素的线程会等待队列可用。

阻塞队列常用于生产者和消费者的场景，生产者是往队列里添加元素的线程，消费者是从队列里拿元素的线程。阻塞队列就是生产者存放元素的容器，而消费者也只从容器里拿元素。

阻塞队列实现了阻塞接口

BlockingQueue

。


java.util.concurrent

中加入了

BlockingQueue

接口和五个阻塞队列类。

方法介绍

阻塞队列提供了四种处理方法：

• 一直阻塞
  
  
  当阻塞队列满时，如果生产者线程往队列里put元素，队列会一直阻塞生产者线程，直到拿到数据，或者响应中断退出。
  

  
  当队列空时，消费者线程试图从队列里take元素，队列也会阻塞消费者线程，直到队列可用。
  

• 超时退出
  
  
  当阻塞队列满时，队列会阻塞生产者线程一段时间，如果超过一定的时间，生产者线程就会退出。
  

  
  当阻塞队为空时，队列会阻塞消费者线程一段时间，如果超过一定的时间，消费者线程就会退出。
  

非阻塞方法

remove、element、offer 、poll、peek 其实是属于Queue接口

。 而阻塞方法

put

、

take

是定义在

BlockingQueue接口

中

阻塞队列的成员：

下面分别简单介绍一下：

• ArrayBlockingQueue：
  
  
  是一个用
  
数组

  实现的有界阻塞队列，此队列按照先进先出（FIFO）的原则对元素进行排序。
  
支持公平锁和非公平锁

  。
  

  
  构造函数必须指定大小
  
  
  
  【注：每一个线程在获取锁的时候可能都会排队等待，如果在等待时间上，先获取锁的线程的请求一定先被满足，那么这个锁就是公平的。反之，这个锁就是不公平的。公平的获取锁，也就是当前等待时间最长的线程先获取锁】
  

  详情参见：
  
  《ArrayBlockingQueue》
  

• LinkedBlockingQueue：
  
  
  一个由
  
链表

  结构组成的有界队列，此队列按照先进先出的顺序进行排序。
  
  
  
  有界队列，如果不指定大小，则此队列的默认长度为
  
Integer.MAX_VALUE

  。
  

  有的文章说LinkedBlockingQueue是无界的，可能是基于构造函数是否必须指定大小的角度来说的，但是由于内部有默认值，严格来说是仍然是有界的

  详情参见：
  
  《LinkedBlockingQueue》
  

• PriorityBlockingQueue：
  
  
  一个支持线程优先级排序的无界队列，默认自然序进行排序，也可以自定义实现compareTo()方法来指定元素排序规则，不能保证同优先级元素的顺序。
  

  
  但需要注意的是PriorityBlockingQueue并不会阻塞数据生产者(无界的，队列永远不会满，无法触发队列满阻塞)，而只会在没有可消费的数据时，阻塞数据的消费者(即可以触发空阻塞)。
  
  因此使用的时候要特别注意，生产者生产数据的速度绝对不能快于消费者消费数据的速度，否则时间一长，会最终耗尽所有的可用堆内存空间。

• DelayQueue：
  
  
  一个实现
  
PriorityBlockingQueue

  实现
  
延迟获取

  的无界队列，在创建元素时，可以指定多久才能从队列中获取当前元素。只有延时期满后才能从队列中获取元素。
  

  DelayQueue可以运用在以下应用场景：
  
  
1.缓存系统的设计

  ：可以用DelayQueue保存缓存元素的有效期，使用一个线程循环查询DelayQueue，一旦能从DelayQueue中获取元素时，表示缓存有效期到了。
  
  
2.定时任务调度

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

• SynchronousQueue：
  
  
  一个不存储元素的阻塞队列，每一个put操作必须等待take操作，否则不能添加元素。支持公平锁和非公平锁。SynchronousQueue的一个使用场景是在线程池里。Executors.newCachedThreadPool()就使用了SynchronousQueue，这个线程池根据需要（新任务到来时）创建新的线程，如果有空闲线程则会重复使用，线程空闲了60秒后会被回收。
  

2.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：
  
  
  一个由链表结构组成的双向阻塞队列。队列头部和尾部都可以添加和移除元素，多线程并发时，可以将锁的竞争最多降到一半。
  

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

3. 非阻塞队列

内置的不阻塞队列：

PriorityQueue

和

ConcurrentLinkedQueue


PriorityQueue 和 ConcurrentLinkedQueue 类在 Collection Framework 中加入两个具体集合实现。

• 
PriorityQueue

  类实质上维护了一个有序列表。加入到 Queue 中的元素根据它们的天然排序（通过其 java.util.Comparable 实现）或者根据传递给构造函数的 java.util.Comparator 实现来定位。

• 
ConcurrentLinkedQueue

  是基于链接节点的、
  
线程安全

  的队列。并发访问不需要同步。因为它在队列的尾部添加元素并从头部删除它们，所以只要不需要知道队列的大 小，ConcurrentLinkedQueue 对公共集合的共享访问就可以工作得很好。收集关于队列大小的信息会很慢，需要遍历队列。

  入队和出队操作均利用
  
CAS

  （compare and set）更新，这样允许多个线程并发执行，并且不会因为加锁而阻塞线程，使得并发性能更好。

没有实现的阻塞接口的LinkedList： 实现了

java.util.Queue

接口和

java.util.AbstractQueue

接口

在另一篇文章中看到的类关系图，可以与前文的结合来看：

4.疑问，到底什么是阻塞队列

区分阻塞队列和非阻塞队列的关键因素是什么？

按照大多数文章的介绍，阻塞队列支持阻塞特性，在队列满或为空时会阻塞，但是我想到队列必须是线程安全的，阻塞队列（前文表格中的那5个阻塞队列）都是利用悲观加锁，互斥做到线程安全的，貌似加锁在某种程度上也等价于阻塞，巧合的是非阻塞队列（比如ConcurrentLinkedQueue）又是利用乐观锁实现线程安全的，乐观锁可以理解成未加锁。

在《

JAVA中的阻塞队列和非阻塞队列

》一文中，介绍非阻塞队列时有如下：

基于锁的算法会带来一些活跃度失败的风险。如果线程在持有锁的时候因为阻塞I/O、页面错误、或其他原因发生延迟，很可能所有的线程都不能工作了。一个线程的失败或挂起不应该影响其他线程的失败或挂起，这样的算法称为

非阻塞算法

；如果算法的每一个步骤中都有一些线程能够继续执行，那么这样的算法称为

锁自由

（lock-free）算法。在线程间使用

CAS

进行协调，这样的算法如果能构建正确的话，它既是非阻塞的，又是锁自由的。java中提供了基于CAS非阻塞算法实现的队列，比较有代表性的有

ConcurrentLinkedQueue

和

LinkedTransferQueue

，它们的性能一般比阻塞队列的好。

那么如果回答什么是阻塞队列，什么是非阻塞队列时，是不是2个要素都要提及？

4.1 答案

阻塞队列，是指多线程访问竞争资源时，当竞争资源已被某线程获取时，其它要获取该资源的线程需要阻塞等待！

虽然队列满了，会休眠，出队发现为空，就等待，也是阻塞，但不是阻塞队列的核心概念！

参见

《JUC回顾之-ArrayBlockingQueue底层实现和原理》

参考：

https://www.cnblogs.com/bjxq-cs88/p/9759571.html 什么是阻塞队列？

https://www.cnblogs.com/lemon-flm/p/7877898.html

https://baijiahao.baidu.com/s?id=1649350860832492296&wfr=spider&for=pc