队列的定义

在现实生活中，像队列的例子就是我们平时的排队买票，先来的先买，后来的只能站在末尾，不允许插队。

队列的特征是，先进先出。跟栈一样，队列也是一种操作受限的线性表数据结构。

队列的基本操作：

入列：在队列尾部添加一个元素
出列：从队列头部移除一个元素

09 | 队列：队列在线程池等有限资源池中的应用 - 图2
队列跟栈一样，也是一种操作受限的线性表数据结构。

队列的实现

基于数组实现的队列

//基于数组实现的队列
function Queue(){
    var items = [];
    //入队
    this.enqueue = function(elem){
        items.push(elem);
    }
    //出队
    this.dequeue = function(){
        return items.shift();
    }
    //返回队列最前面的项
    this.front = function(){
        return items[0];
    }
    //队列是否为空
    this.isEmpty  = function(){
        return items.length == 0;
    }
    //队列的长度
    this.size = function(){
        return items.length;
    }
    //打印队列
    this.print = function(){
        console.log(items.toString());
    }
}

基于链表实现的队列：

https://github.com/wangzheng0822/algo/blob/master/javascript/09_queue/QueueBasedOnLinkedList.js

循环队列

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

我们可以看到，图中这个队列的大小为 8，当前 head=4，tail=7。当有一个新的元素 a 入队时，我们放入下标为 7 的位置。但这个时候，我们并不把 tail 更新为 8，而是将其在环中后移一位，到下标为 0 的位置。当再有一个元素 b 入队时，我们将 b 放入下标为 0 的位置，然后 tail 加 1 更新为 1。所以，在 a，b 依次入队之后，循环队列中的元素就变成了下面的样子：

通过这样的方法，我们成功避免了数据搬移操作。看起来不难理解，但是循环队列的代码实现难度要比前面讲的非循环队列难多了。要想写出没有 bug 的循环队列的实现代码，我个人觉得，最关键的是，确定好队空和队满的判定条件。

阻塞队列和并发队列

阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。

而且不仅如此，基于阻塞队列，我们还可以通过协调“生产者”和“消费者”的个数，来提高数据的处理效率。

线程安全的队列我们叫作并发队列。

解答开篇

1.线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？各种处理策略又是如何实现的呢？
我们一般有两种处理策略。第一种是非阻塞的处理方式，直接拒绝任务请求；另一种是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理。那如何存储排队的请求呢？
我们希望公平地处理每个排队的请求，先进者先服务，所以队列这种数据结构很适合来存储排队请求。

2.队列有基于链表和基于数组这两种实现方式。这两种实现方式对于排队请求又有什么区别呢？
基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。
而基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。
除了前面讲到队列应用在线程池请求排队的场景之外，队列可以应用在任何有限资源池中，用于排队请求，比如数据库连接池等。实际上，对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。