数据结构与算法：队列：队列在线程池等有限资源池中的应用

我们都知道，CPU资源是有限的，任务的处理速度与线程个数并不是线性正相关。相反，过多的线程反而会导致CPU频繁切换，处理性能下降。所以线程池的大小一般都是综合考虑要处理任务的特点和硬件环境，来事先设置的。

当我们向固定大小的线程池中请求一个线程时，如果线程池中没有空闲资源了，这个时候线程池如何处理这个请求？是拒绝请求还是排队请求？各种处理策略又是怎么实现的呢？

实际上，这些问题并不复杂，其底层的数据结构就是我们今天要了解的内容， 队列（queue） 。

1.什么是队列？

可以把队列想象成排队买票，先来的先买，后来的人只能站末尾，不允许插队。 先进者先出，这就是典型的“队列” 。

栈只支持两个基本操作：入栈push（）和出栈pop（）。队列和栈非常相似，支持的操作也很有限， 最基本的操作 也是 两个 ： 入队enqueue（） ，放一个数据到队列尾部；出队 dequeue（） ，从队列头部取一个元素。

所以，队列和栈一样，也是一种 操作受限的线性表数据结构。

2.顺序队列和链式队列

跟栈一样，队列可以用数组实现，也可以用链表来实现。用 数组实现 的队列叫做 顺序队列 ，用 链表实现 的队列叫做 链式队列 。

3.循环队列

顾名思义，循环队列长得有点 像一个环 。原本数组是有头有尾的，是一条直线。现在，我们把首尾相连，扳成一个环。

假如一个队列大小为8，当前队头指针head=4，队尾指针tail=7,。当又有一个新的元素a入队时，我们放入下标为7的位置，但是此时，tail不会更新为8，而是会在 环中后移一位 ，移到下标为0的位置。通过这样的操作，就可以 避免顺序队列 进行操作会遇到的 数据搬移操作 。但是循环队列的实现比较难，需要确定好 队空和队满的判定条件 。

在 顺序队列 中， 队满 的判断条件是 tail=n ， 队空 的判断条件是 head=tail 。那么，针对循环队列的话，如何判断队空和队满呢？

队空 的判断条件仍然是 head=tail ，但是队满的判断稍微有点复杂。 队满 的判断条件是 （tail+1）%n=head ，当队满的时候， tail指向的位置 是 没有存储数据 的，因此，循环队列会 浪费一个数组 的 存储空间 。

4.阻塞队列和并发队列

阻塞队列其实就是在队列基础上 增加 了 阻塞操作 。在队列为空的时候，从队头 取数据 就会被 阻塞 。因为此时还 没有数据可取 ，直到队列中有了数据才能返回；如果队列满了，那插入数据的操作就会被阻塞，直到队列中有空闲位置再插入数据，然后再返回。

上述定义其实就是一个“生产者-消费者模型”。可以使用阻塞队列实现一个“生产者-消费者模型”。

基于阻塞队列实现的“生产者-消费者模型”，可以有效地 协调 生产和消费的 速度 。也可以通过协调“生产者”和“消费者”的个数，来 提高数据的处理效率 。

在多线程情况下，会有多个线程同时操作队列，这个时候，就会存在 线程安全问题 ，如何实现一个线程安全的队列呢？

线程安全的队列 叫做 并发队列 。最简单直接的实现方式是 直接在enqueque（）、dequeque（）发布方法上加锁 ，但是 锁粒度大并发度会比较低 ， 同一时刻 仅允许 一个存或取 操作。实际上，基于数组的 循环队列 ，利用 CAS原子 操作，可以实现非常 高效的并发队列 。这也是循环队列比链式队列应用更加广泛的原因。

5.解答开篇

线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？各种策略又是如何实现的呢？

一般有 两种处理策略 。第一种是 非阻塞的处理方式 ， 直接拒绝 任务请求；另一种是 阻塞的处理方式 ，将请求 排队 ，等到有 空闲线程 时， 取出排队的请求 去继续 处理 。那么，如何处理排队的请求呢？

我们希望 公平地 处理每个排队的请求， 先进者先服务 ，所以 队列 这种数据结构就很适合来存储排队的请求。

基于链表的 链式队列 ，可以实现一个支持 无限排队 的 无界队列 ，但是可能会导致 过多的请求排队 等待，请求处理的 响应时间过长 。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是 不合适 的。

而基于 数组实现 的 有界队列 ，队列的 大小有限 ，所以线程池中排队的请求 超过队列大小 时，接下来的请求就 会被拒绝 ，这种方式对响应时间敏感的系统来说，就 相对更加合理 。不过，设置一个 合理的队列大小 ，也是 非常讲究 的。队列 太大 导致 等待的请求太多 ，队列 太小 会导致 无法充分利用系统资源 ，发挥最大性能。

除此之外， 队列 可以应用在任何 有限资源池 中，用于 排队请求 ，比如 数据库连接池 等。实际上，对于大部分 资源有限的场景 ，当没有空闲资源时，基本都可以通过“队列”这种数据结构来实现请求排队。

6.内容小结

队列 最大的 特点 就是 先进先出 ，主要的操作是 入队 和 出队 。既可以用 数组实现， 也可以用 链表实现 。用 数组 实现的是 顺序队列 ，用 链表 实现的叫 链式队列 。还有一种像 环 一样的 循环队列 。在 数组 实现 队列 的时候，会有 数据搬移 的操作，要想 解决数据搬移 的问题，我们就 需要像环一样的循环队列 。

循环队列 的实现 关键 要确定好 队空 和 队满 的 判定条件 。

除此之外，还有几种高级队列， 阻塞队列 、 并发队列 ， 底层 都是 队列 这种数据结构，只不过是在之上 附加了 很多 其他功能 。 阻塞队列 就是 入队、出队操作可以阻塞 ， 并发队列 就是队列操作 多线程安全 。