文章来源：http://blog.seclibs.com/数据结构之队列/
上一篇文章说了一种“功能受限”的顺序表——栈，现在再来说一个 “功能受限”的顺序表 ——队列（queue）。
队列也是一个常用的数据结构，在大部分资源有限的情况下，当没有空闲资源的时候，基本上都是使用队列这种数据结构来实现请求排队的。
队列，顾名思义，就是排的一条队，比如在买票的时候排的一条队伍，先来的先买，后来的后买，不允许插队，也就是先进先出的方式，栈是后进先出的方式。
栈支持入栈（push）和出栈（pop）两种操作，队列也是类似的，支持入队（enqueue）和出队（dequeue）两种操作，入队就是在尾部追加一个数据，出队就是在头部取走一个数据。
队列作为一种非常基础的数据结构，应用是非常广泛的，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。
队列在实现上跟栈也是类似的，可以使用数组或链表来进行实现，使用数组实现的叫做顺序队列，使用链表实现的叫做链式队列。但是栈只需要一个栈顶指针top就可以了，队列则需要头部head指针和尾部tail指针两个来标识。
比如说a、b、c、d四个数据入队以后，head指针将指向下标为0的位置，tail指针指向下标为4的位置
当进行两次出队的操作后，head指针将指向下标为2的位置
那如果不断的往后走，一直到下标为7后，不能再继续增加了怎么办，那就可以使用数组实现时的数据移动的方式，将数据向前迁移，那如果每进行一次出栈就迁移一次，那不就相当于一直在删除下标为0的元素，然后将整个队列都拷贝一边，操作的时间复杂度就为O(n)了呀，其实完全可以用另一种思路，在每次出栈的时候不进行迁移数据的操作，而是在数据入栈的时候，发现没有位置了，再将所有的数据向前迁移，这样时间复杂度就变成了O(1)，即队列未满时，直接入队，时间复杂度为O(1)，当队列已满时，也就是tail=n时，时间复杂度变为了O(n)，如果将最后一次的n次迁移，平均到前面的n-1次上，那它们的均摊时间复杂度就变为了O(1)。
上面说的是顺序队列，对于链式队列来说，就更加容易了，因为不会涉及到队满的情况了，只需要处理好指针的移动问题就可以了。
但是它还有一个比较严重的问题，因为它的长度是可以无限长的，所以当请求的任务特别多时，后面的任务将会等待相当长的时间，这对于对时间比较敏感的系统来说，是会出问题的。
顺序队列因为大小有限，如果请求的任务超过了队列长度，将会直接将后续的任务拒绝掉，这对于对时间比较敏感的系统来说，是比较合理的方式，但是如何设置队列的大小又是一个问题，队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。
前面顺序队列的实现时，当tail=n时，会有大量数据迁移的操作，如果使用循环队列就可以完美的解决这个问题了。
循环队列，顾名思义，就是将队列的首尾相连，组成环状
就拿上图来说，这个循环队列n=8，当前head=4，tail=7，当我们再插入一个数据的时候，会插入到下标为7的位置，tail将会向后挪一个，到达了0的位置，再插入数据，依旧像上面说的一样执行，tail将指向了下标为1的地方。
通过这样的方法，就节省了很多数据迁移的操作，但是在代码实现上就会更加的复杂，其中最关键的地方还是确定好队空和队满的判定条件。
队列为空的条件仍然是head=tail，那什么情况下是队满呢？
在一般情况下，很明显的可以看出来，当tail+1=head的时候，即为队满
但是还有一个情况比较特殊，并不适用这个规则，就是当head=0，tail=7时，此时再插入一个数据的时候，观察图可以发现，此时tail将等于head，但是tail=head的时候，是我们所说的队列为空的时候，这也就是为什么循环队列会浪费一个数组空间的原因；这个情况明显已经属于队满的情况了，如果套用上面的公式，tail+1=8，head=0，并不满足我们前面所提到的常规情况。
那么如何才能将tail+1在最大的情况下等于0呢，这里可以引入取余的方法。当tail=7时，tail+1=8，将它与n=8取余，8%8=0，就可以满足这个要求了，通用的公式就变成了(tail+1)%n=head，那一般情况满不满足这个公式呢，因为在一般情况下，tail+1都是小于n的，只有在上面所说的特殊情况时tail+1=n，所以不管怎么取余都是tail+1本身，也就是等于head了，所以队满的条件为(tail+1)%n=head。
上面在解释的时候也说了循环队列会浪费一个数组空间的原因，那如果我们专门用一个记录队列大小的值size，当这个值与数组大小相等时，表示队列已满，当tail达到最底时，size不等于数组大小时，tail就指向数组第一个位置。当出队时，size- -，入队时size++。
这种的记录方法跟之前实现栈时候的思路类似，但是这样依旧会新创建一个内存空间来存放size值，最后消耗的大小是一样的。
到这里基础的队列就说完了，但是这样基础的队列在实际的业务开发中都不大会直接用到，常用的是一些比较特殊的队列，比如阻塞队列和并发队列。
阻塞队列其实就是在正常的队列操作中加上了阻塞操作，当队列为空时，在对头取数据的时候，会被阻塞，因为队列中还没有任何可以取的数据，直到队列中有数据时，才会取出数据并返回；如果队列已经满了，那插入数据将会被阻塞，直到有空闲位置后，将数据插入才会返回。
通过阻塞队列，很轻松就可以实现“生产者 – 消费者模型”，它可以有效的协调生产与消费的速度，当生产过快的时候，队列就无法再加入了，生产者就会被阻塞，直到出现空余位置的时候才会继续生产。
那我们设想一个场景，如果消费者方面已经不需要这个东西了，那生产方还是在不断的往进放东西，这样就会造成极大的浪费，这样的情况让我想起了我们现在全面深化改革的一点——供给侧结构性改革，不再让供给方无限的供给了，要在可能快出现问题的时候，便让供给方减少供给，以便让资源得到更好的利用。
插了点题外话，我们继续说阻塞队列，为了让数据更加高效的处理，我们还可以协调供给者和消费者的的数量。
那并发队列又是什么，并发队列就是在多线程的情况下，由于有多个线程同时操作，可能会存在一些安全问题，为了实现线程安全的队列就是并发队列，与阻塞队列类似，并发队列就是在入队和出队上加锁，同一时刻仅允许一个存或取的操作，但是锁粒度大并发度就会比较低，这个也是一个需要协调的东西。
实际上，基于数组的循环队列，利用 CAS 原子操作 (Compare & Set，或是 Compare & Swap)，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。
参考文档
极客时间-数据结构与算法之美
文章首发公众号和个人博客
公众号：无心的梦呓（wuxinmengyi）
