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

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

实际上，这些问题并不复杂，其底层的数据结构就是我们本篇文章所学习的知识。

如何理解"队列"呢？？？

其实队列就想排队买票是一样的，先来的先买，后来的后买，不允许插队。先进先出，这就是典型的队列。

之前的文章讲过栈，栈有两个基本操作，入栈push()，出栈pop()。队列和栈相似，操作都受限制的。队列也是有两个基本操作，入队enqueue()：放一个数据到队列尾部，出队dequeue()：从队列头取一个元素。

image.png

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

队列的概念很好理解，基础操作也是很好掌握的，同时队列的应用也是非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列，在很对底层的系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列Disruptor、Liunx环形缓存，都用到了循环并发队列；Java concurrent并发包利用ArrayBlockingQueue来实现公平锁的。

顺序队列和链式队列

我们知道了，栈和队列一样，也是一种抽象的数据结构。也知道它的特性了。那么该如何实现一个队列呢？
在关于栈的那篇文章中说过，栈可以用数组来实现，也可以用链表来实现。用数组实现的栈叫做顺序栈，用链表实现的栈叫链式栈。同样，队列也可以使用数组实现或者是使用链表实现，使用数组实现的叫做顺序队列，用链表实现的队列叫做链式队列。

下面我们就是用数组实现一个队列，Java代码如下：

// 用数组实现的队列
public class ArrayQueue {
  // 数组：items，数组大小：n
  private String[] items;
  private int n = 0;
  // head 表示队头下标，tail 表示队尾下标
  private int head = 0;
  private int tail = 0;

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

  // 入队
  public boolean enqueue(String item) {
    // 如果 tail == n 表示队列已经满了
    if (tail == n) return false;
    items[tail] = item;
    ++tail;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果 head == tail 表示队列为空
    if (head == tail) return null;
    // 为了让其他语言的同学看的更加明确，把 -- 操作放到单独一行来写了
    String ret = items[head];
    ++head;
    return ret;
  }
}

对于使用数组实现队列相比使用实现栈要复杂一点，接下来我们一起理解一下实现的思路：
对于栈来说，只需要一个栈顶指针就可以了。但是对于队列来讲，需要两个指针：一个是head指针，指向队头，一个tail指针，指向队尾。

接下来，我们一起理解一下：
结合下图，当a,b,b,d依次入队后，队列中的head指针指向下标为0的位置，tail指针指向下标为4的位置。

image.png

当我们调用两次出队的操作之后，队列中head指针指向下标为2的位置，tail指针不变

image.png

大家肯定发现了，随着不停的入队、出队操作，head和tail都会持续往后移动。当tail移到最右边的时候，即使队列中还有空闲空间，也无法继续往队列里添加数据了。该如何解决呢？这就会用到我们之前文章中说过的，数组删除操作会导致数据不连续的问题的解决方法了，那就是数据搬移。但是每次出队操作都会删除数组下标为0的元素，就要搬移整个队列中的数据，这样出队的时间复杂度就会从原来的O(1)变成O(n)。所以我们需要优化一下，我们在出队的时候不用搬移数据。如果没空间了，我们只需要在入队的时候，在集中触发一次数据搬移操作。借助这个思想，出队的函数dequeue()保持不变，我们稍加改造一下入队函数enqueue()的实现，就可以解决刚才的问题
Java代码如下：

   // 入队操作，将 item 放入队尾
  public boolean enqueue(String item) {
    // tail == n 表示队列末尾没有空间了
    if (tail == n) {
      // tail ==n && head==0，表示整个队列都占满了
      if (head == 0) return false;
      // 数据搬移
      for (int i = head; i < tail; ++i) {
        items[i-head] = items[i];
      }
      // 搬移完之后重新更新 head 和 tail
      tail -= head;
      head = 0;
    }
    
    items[tail] = item;
    ++tail;
    return true;
  }

image.png

这种实现的过程中，出队的时间复杂度仍然是O(1)，但是入队操作的时间复杂度还是O(1)么？我们可以根据之前的文章，自己分析一下。

接下来我们再来看一下基于链表的队列实现方式：
基于链表的实现方式，我们还是需要两个指针：head指针和tail指针，他们分别指向链表的第一个结点和最后一个结点。如下图所示，入队时，tail->next=new_node,tail=tail->next;出队时head=head->next。示意图如下：

image.png

循环队列

刚才用数组实现队列的时候，当tail=n的时候，就会有数据搬移的操作，入队操作的效率就会受到影响，所以我们想用另一种方法解决这个问题。那就是循环队列，顾名思义，循环队列就是一个环状的，就是将刚刚的数组的头和尾连接到一起，组成一个环形的队列，可以参考下图：

image.png

如上图，我们可以看见队列的大小为8，head现在指向4的位置，tail指向7的位置，如果现在有a，b两个元素需要入队，a就会放到7的位置，而这时tail不更新为8，而是更新为0，在将b放在下标为0的位置上，这样就避免的数据搬移的操作。这种情况是很好理解的，但是编码程度上会比非循环队列难得多。关键的代码就是需要正确的判断队满和队空的条件

image.png

在非循环队列中，我们判断队满的条件是tail == n，队空的条件是head == tail。接下来我们总结一下循环队列的队满和对空的判断条件。
对空的判断条件还是head == tail，但是队满的条件就不一样了，是(tail+1)%n = head
但是有一个问题，就是当队满的时候，上图中tail指针位置是没有存储数据，所以循环队列会浪费一个数据的存储空间。
代码如下：

public class CircularQueue {
  // 数组：items，数组大小：n
  private String[] items;
  private int n = 0;
  // head 表示队头下标，tail 表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为 capacity 的数组
  public CircularQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入队
  public boolean enqueue(String item) {
    // 队列满了
    if ((tail + 1) % n == head) return false;
    items[tail] = item;
    tail = (tail + 1) % n;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果 head == tail 表示队列为空
    if (head == tail) return null;
    String ret = items[head];
    head = (head + 1) % n;
    return ret;
  }
}

阻塞队列和并发队列

队列相关的知识基本上就是理论知识，平时的应用开发上也很少会用上，因为队列这种数据结构很基础。但是有一些特殊的队列的应用就比较广泛了，比如阻塞队列和并发队列
阻塞队列就是在队列的基础上添加了阻塞操作。解释一下：就是当队空的时候，从队头取数据就会被阻塞，因为当前队列中没有数据可以取，所以需要等队列中有数据了才能返回。当队满的时候，入队操作就会被阻塞，需要等队列中有空闲位置后在进行入队操作，再返回。

image.png

上述的操作其实就是一个"生产者-消费者模型"，所以我们可以使用阻塞队列，轻松实现一个"生产者-消费者模型"！

这种基于阻塞队列实现的"生产者-消费者模型"，可以有效的协调生产和消费的速度。当生产者生产过快，消费者来不及消费的时候，队列就会满，这时候就会阻塞队列，等消费者消费了之后，在唤醒生产者。。。

不仅如此，基于阻塞队列，我们还可以协调“生产者”和“消费者”的个数，来提高数据处理效率。根据前面的例子我们可以考虑配置多个消费者，来应对一个生产者。

image.png

接下来一起了解一下，多线程的情况下，会有多个线程同时操作队列，这时候就会存在线程安全问题，那又如何保证线程安全呢？

线程安全的队列我们又叫做并发队列，最简单的方法就是在入队enqueue()和出队dequeue()方法上面加锁，但是锁的力度大，并发度会降低，同一时刻只允许一个存或取的操作。实际上，基于数组的循环队列，利用CAS原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更广泛的原因。

解答开篇的问题，如果线程池中没有空闲的资源了，我们一般有两种策略，第一：非阻塞处理方式，直接拒绝任务请求；第二：阻塞处理方式，将请求排队，等有空闲线程时，取出排队的请求继续处理。

那如何存储排队请求呢？
我们为了公平处理每个排队的请求，先进者先服务，就会用到队列这种数据结构来存储请求。前面说过队列又有两种实现方式，基于链表的的实现方式和基于数组的实现方式。

二者又有什么区别呢？
基于链表的实现方式，可以实现一个无限量的无界队列，但是可能到时排队的请求过多，导致响应时间过长。所以针对响应时间敏感的系统，用链表方式实现的队列就不合适了。而基于数组实现的有界队列，队列有大小，所以线程池中排队的请求超过队列的大小时，接下来的请求就会直接别拒绝，所以针对响应时间敏感的系统，这种方式就相对合适了。不过，设置一个合理的队列大小也是很有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。

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