队列：队列在线程池等有限资源池中的应用

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

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

极客时间对应地址
GitHub地址

一、如何理解 队列

先进先出即为队列。与栈的先进后出有明显区别，刚开始还容易混淆。

栈呢，只支持两个基本操作，入栈push()和出栈pop()。队列和栈非常相似，也只支持两个操作，入队enqueue()和出队dequeue()

• 入队enqueue：放一个数据到队列尾部
• 出队dequeue：从队列头部取一个元素

image

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

二、顺序队列和链式队列

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

1. 顺序队列

下面是Java语言中基于数组的实现方式：

/**
 * 使用数组实现的队列
 *
 * @author : zyf
 * @since : 2019-01-02 13:57
 **/
public class ArrayQueue {

    /**
     * 数组：items，数组大小：n
     */
    private String[] items;
    private int n = 0;

    /**
     * head 表示队头在数组中的下标
     * tail 表示队尾在数组中的下标
     */
    private int head = 0;
    private int tail = 0;

    /**
     * 申请一个大小为 capacity 的数组
     * @param capacity
     */
    public ArrayQueue(int capacity) {
        items = new String[capacity];
        this.n = capacity;
    }

    /**
     * 入队
     * @param item
     * @return
     */
    public boolean enqueue(String item){
        if(tail == n){
            //填满了
            return false;
        }
        
        items[tail++] = item;
        return true;
    }

    public String dequeue(){
        if(head == tail){
            //表示队列为空
            return null;
        }

        return items[head++];
    }
}

队列的数组实现比栈的数组实现略显复杂，对于栈来说，我们只需要一个栈顶指针就可以了。但是队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。

image image

在学习数组这一节中，也遇到过类似的问题，就是数组的删除操作会导致数组中的数据不连续。数组的解决方式是，每次删除后，都会进行 数据搬移。这里我们每次进行出队操作，实际上都相当于删除下标为 0 的数据，那么就要搬移整个队列中的数据。（就像切黄瓜一样，从一头开始，一手切，另一手不停的向菜刀方向推）那么出队操作的时间复杂度就由 ○(1) 变为 ○(n)，我们该如何优化呢？

实际上我们在出队时可以不用搬移数据。如果没有空闲时间了，我们只需要在入队时，再集中触发一次数据的搬移操作。

    /**
     * 入队  版本2
     *
     * @param item
     * @return
     */
    public boolean enqueue(String item) {
       if (tail == n) {
            //当 tail == n && head==0 为true时，
            // 说明对头在数组0位置队尾在数组末尾，此时数组是占满状态
            //返回false 表示不可再添加数据了
            if (head == 0) return false;

            //如果head不等于0，而队尾处于数组末尾，说明执行过出队操作
            //那么需要进行数据迁移，将head位置的元素，移到数组0位置
            for (int i = head; i < tail; i++) {
                items[i - head] = items[I];
            }

            //数据搬移完毕，更新 head 和 tail 这两个指针
            tail -= head;
            head = 0;
        }

        //数据搬移完毕，（或 tail != n 无需搬移）
        //执行添加操作
        items[tail++] = item;
        return true;
    }

image

• 时间复杂度：
  • 出队： ○(1)
  • 入队：加权平均分析法：○(n)

2. 链式队列

基于链表的实现，我们同样需要两个指针：head指针和tail指针。它们分别指向链表的第一个结点和最后一个结点。

import exception.EmptyQueueException;

/**
 * 基于链表实现的队列
 *
 * @author : zyf
 * @since : 2019-01-02 15:30
 **/
public class LinkedQueue {
    private Node head;
    private Node tail;

    public void enqueue(Node newNode){
        if(head == null){
            head = newNode;
        }else {
            tail.setNext(newNode);
        }
        tail = newNode;
    }

    public Node dequeue(){
        if(head == null){
            throw new EmptyQueueException();
        }
        Node result = this.head;

        head = head.getNext();
        return result;
    }
}

三、循环队列

对于刚刚使用数组来实现队列的方式，当 tail==n 时，会有 数据搬移 操作，这样入队操作性能就会受到影响，那有没有办法能够避免数据搬移呢？

循环队列 可以解决上述问题，顾名思义，它很像一个环。原本数组有头有尾，似一条直线，现将数组首尾相连，即为环。

image

上图中可以看到，此队列大小 n = 8; 图中状态 head = 4; tail = 7;。当有一个新的元素 a 入队时，我们放入下标为 7 的位置。此时我们不将 tail 更新为 8，而是将其在环中后移一位，到下标为 0 的位置。当再有一个元素 b 入队时，将 b 放入下标为 0 的位置，然后 tail+1 更新为 1。

a，b 依次入队后，循环队列中的元素变成下图所示：

image

如此我们成功避免了数据办已操作，但是循环队列代码实现比较复杂，容易出现bug，最关键的是 确定好 队空和队满 的判定条件。

• 队列为空时的判断条件：head == tail
• 队列装满时的判断条件：head == (tail+1)%n
  • 如果自己思考的话，我能想到的是：(head + tail) == (n-1) || (head - tail) == 1

image image

因为循环队列满时，tail 指向的位置实际上是没有存储数据的，所以循环队列会浪费一个数组的存储空间。

package loop;

import exception.EmptyQueueException;

/**
 * 循环队列
 *
 * @author : zyf
 * @since : 2019-01-02 18:04
 **/
public class LoopQueue {
    private String[] items;
    private int n;
    private int head;
    private int tail;


    public LoopQueue(int n) {
        items = new String[n];
        this.n = n;
        head = 0;
        tail = 0;
    }

    public boolean enqueue(String item){
        //根据推导出的 (tail+1)%n=head 判断是否已满
        if((tail+1)%n == head){
            return false;
        }

        //没满的话
        //存值
        items[tail] = item;
        // tail 后移一位，并且在后移时要注意判断边界问题
        if(tail == n - 1){
            tail = 0;
        }else {
            tail++;
        }

        return true;
    }

    public String dequeue(){
        //出队之前，要判断边界问题
        if(head == tail){
            //说明队列为空
            throw new EmptyQueueException();
        }
        //出队，tail都不用动。。。
        String item = items[head];
        if(head == n-1){
            head = 0;
        }else {
            head++;
        }

        return item;
    }
}

import loop.LoopQueue;
import org.junit.Before;
import org.junit.Test;

/**
 * 测试循环队列
 *
 * @author : zyf
 * @since : 2019-01-02 18:16
 **/
public class TestLoopQueue {
    private LoopQueue loopQueue;

    @Before
    public void prepare(){
        loopQueue = new LoopQueue(5);
    }

    @Test
    public void t1(){
        loopQueue.enqueue("a");
        loopQueue.enqueue("b");
        loopQueue.enqueue("c");
        loopQueue.enqueue("d");
        //被装满了后，e f 就装不进去了
        loopQueue.enqueue("e");
        loopQueue.enqueue("f");

        try {
            String fromQueue = null;
            do {
                fromQueue = loopQueue.dequeue();
                System.out.println(fromQueue);
            }while (fromQueue != null);
        }catch (RuntimeException e){
            System.out.println("队列被取光了");
        }
    }
}

image

四、 阻塞队列和并发队列

前面的内容，基本上都是些理论内容，而在实际开发中，一般也不会从零开始写一个队列，甚至不会直接用到，但是 阻塞队列 并发队列 等具有特殊特性的队列应用却很广泛。

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

image

这实际上就定义了一个 生产者-消费者模型。基于阻塞队列实现的 生产者-消费者模型 可以有效地协调生产和消费的速度。

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

image

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

image

五、解答开篇

线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？各种处理策略又是如何实现的呢？
一般有两种处理策略。第一种是非阻塞的处理方式，直接拒绝任务请求；
另一种是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理。

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

基于数组和基于链表这两种实现方式对于排队请求又有什么区别呢？
基于链表的实现方式，可以实现一个支持无限排队的 无界队列（unbounded queue），但是可能导致过多的请求排队等待，请求处理的响应时间过长。所以针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。
基于数组实现的 有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过设置一个合理的队列大小也是非常有讲究的。队列太大导致等待请求过多，队列太小会导致无法充分利用系统资源、发挥最大性能。

实际上，对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过 队列 这种数据结构来实现请求排队

六、课后思考

1. 除了线程池这种池结构会用到队列排队请求，你还知道哪些类似的池结构或者场景中会用到队列的排队请求呢？
2. 今天讲到并发队列，关于如何无锁并发队列，你怎么看？

答：

1. 分布式消息队列（是不是那个 RabbitMQ？）
2. 使用CAS（比较和替换）实现无锁队列，入队前获取 tail 位置，入队时比较 tail 是否发生变化，如果否，则允许入队，反之入队失败。