1如何理解“队列”

        先进者先出，这就是典型的“队列”。

        队列跟栈十分相似，最基本的操作也只有两个：

        入队：放一个元素到队列尾部。

        出队：从队列头部取一个元素。

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

        作为一种非常基础的数据结构，它的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。

    2顺序队列和链式队列

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

        我们先用数组来实现。

        它需要两个指针：头指针head和为指针tail。

        简单的出队操作如下图所示（出队略，自行脑补，哈哈）：

        随着不停地进行入队、出队操作，head和tail都会持续往后移动，当tail移动到最右边，即使数组中海油空闲空间，也无法继续往队列中添加数据了。

        这个问题该如何解决呢？

        很简单，在入队时稍微加一个判断就好了（出队不用判断哦）。当队列的tail指针移动到数组的最右边后，如果有新的数据入队，我们可以将head到tail之间的数据，整体搬移到数组中0到tail-head的位置。因为只有在tail指针移动到数组最右边时才会进行一次整体的搬移，所以时间复杂度平摊下来依然是O(1)。（如果每次入队都搬移的话，时间复杂度就会从原来的O(1)变成O(n)）

        搬移如下图所示：

        数组实现的代码如下：

        运行结果：

        戳这里下载源代码。

        接下来用链表实现，同样需要两个指针head和tail。

        在实现的过程中，我发现自己之前写代码的一个问题，就是入队出队功能都写在主函数中并没有封装，这样复用性就太差了。从这次链表的实现开始，我要优化自己的代码，以后将功能都封装在类中~

        代码：

        运行结果：

        戳这里下载源代码。

    3循环队列

        循环队列，顾名思义，它长得像一个环。队列原本是有头有尾的一条直线，现在我们把它的首尾相连，连成了一个环，如下图所示。

        上图中队列的大小为8，当前head=4,tail=7。此时一个新元素a入队，将会被放到下标为7的位置，tail更新成了0而不是8。当又有一个新元素b入队时，将它放到下标为0的位置，tail更新成了1。如下图所示：

        循环队列的好处是，避免了数据搬移操作。

        下面用代码来实现它。实现循环队列的两个关键点在于：

        1，确定队空条件：head==tail。

        2，确定队满条件：(tail+1)%n=head。

        如下图所示，是队满的一种情况：

        我们发现，tail指向的位置实际上是没有存储数据的，所以循环队列会浪费一个数组的存储空间。（如果把这个也存了，就无法判断循环队列的队空与队满）

        我写的代码如下（用数组实现）：

        运行结果：

        戳这里下载源代码。

    4阻塞队列和并发队列

        实际上，队列这种数据结构很基础，平时的业务开发基本都不会直接用到。而一些具有特殊特性的队列应用却比较广泛，比如阻塞队列和并发队列。

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

        不难看出，上述的定义就是一个“生产者-消费者模型”。我们可以用阻塞队列，轻松实现一个生产者消费者模型！

        这种基于阻塞队列实现的“生产者-消费者模型”，可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了。这个时候生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续“生产”。

        而且基于阻塞队列，我们还可以通过协调“生产者”和“消费者”个数，来提高数据的处理效率。比如前面的例子，我们可以多配置几个“消费者”，来应对一个“生产者”。但是在多线程情况下，多个线程同时操作队列，会存在安全问题。而基于数组的循环队列，利用CAS原子操作，可以实现非常高效出现的并发队列。这也是循环队列比链式队列应用更加广泛的原因，后面会详细说并发队列的应用~（其实最简单直接的方式是在入队和出队操作上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。）

    5请求线程

        当线程池中没有空闲线程，新的任务请求线程资源时，我们一般有两种处理策略：1）非阻塞的处理方式，直接拒绝任务请求；2）阻塞的处理方式，将请求排队，等有空闲线程时，取出排队的请求继续处理。

        如何存储排队的请求呢？

        为了公平起见，我们肯定要先进先出，所以队列这种数据结构很适合存储排队请求。

        那我们该用数组还是链表来实现呢？

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

        用数组可以实现一个大小有限的队列，这样当线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝。这样的方式对响应时间敏感的系统来说比较合适。但是要注意哦，设置一个合理的队列大小也是非常重要的，队列太大会导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。

    内容小结

        队列最大的特点就是先进先出，主要的两个操作是入队和出队。它既可以用数组实现（顺序队列），也可以用链表实现（链式队列）。用数组实现队列会有数据搬移操作，而若用数组实现循环队列则避免了数据搬移的操作。循环队列是重点，代码实现的关键是确定好队空和队满的判定条件。除此之外，还学习了集中高级的队列结构，阻塞队列、并发队列，底层都还是用队列这种数据结构，但是在它之上附加了很多其他功能。阻塞队列就是入队、出队操作可以阻塞，并发队列要注意队列的操作多线程安全。