队列与栈类似，也是一种运算受限的线性表。队列则被限定在表尾进行插入、在表头进行删除，这种数据结构，实现了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 | ? 阻塞 | ? 单端 | ? 是 | ? 环形数组 | ? 无锁 | ? 超强性能，支持多种生产者消费者模式； |
参考引用
- 本系列归档至《Java数据结构及算法实战》：https://github.com/waylau/java-data-structures-and-algorithms-in-action
- 《数据结构和算法基础（Java语言实现）》（柳伟卫著，北京大学出版社出版）：https://item.jd.com/13014179.html
?
