队列也是一种“操作受限”的线性表，只支持两种基本操作：入队和出队。
队列的应用非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层的系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。
顺序队列和链式队列
用数组实现的队列叫顺序队列，用链表实现的队列叫链式队列。
顺序队列在没有空闲空间时，需要触发一次数据的搬移操作。
循环队列
将顺序队列首尾连接起来就是循环队列。要注意的点就是，队列判满的条件是
(tail + 1) % n = head
阻塞队列和并发队列
阻塞队列就是在队列的基础上增加了阻塞操作。简单来说，就是在队列为空的时候，出队操作会被阻塞，当队列满的时候，入队操作会被阻塞。其实，上面的定义，就是一个“生产者-消费者”模型。
这种模型，可以有效协调生产和消费的速度。当“生产者”生产速度过快，“消费者”来不及消费时，存储队列很快就会满了。这个时候，生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续生产。
而且不仅如此，基于阻塞队列，我们还可以协调“生产者”和“消费者”的个数，来提高数据处理的效率，比如，我们可以多配置几个“消费者”，来对应一个“生产者”。
并发队列：线程安全的队列我们叫做并发队列。最简单的实现方式就是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低。实际上，基于 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。
队列在线程池中的应用
当线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？各种处理策略又是如何实现的呢？
我们一般有两种处理策略一种是非阻塞队列，一种是阻塞队列。
阻塞队列又有两种实现方式，一种是无限排队等待，另一种就是基于数组的有限队列，这里，给数组队列设置一个合理的队列大小，是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。
关于如何实现无锁并发队列
可以使用 cas + 数组的方式实现。
队列的其他应用
分布式消息队列，如 kafka 也是一种队列。
网友评论