本讲内容
队列的定义
队列的操作
队列的实现
队列的应用
思考题：当我们向固定大小的线程池中请求一个线程时，如果线程池中没有空闲资源了，这个时候线程池如何处理这个请求？是拒绝请求还是排队请求？各种处理策略又是怎么实现的呢？
队列的定义
是一种操作受限的线性表。先进先出，后进后出的特性
队列的操作
入队和出队
栈：只需要一个栈顶指针，进行出栈和入栈
队列：需要一个对头指针，用于出队，一个队尾指针，用于入队
队列的出队和入队
队列的实现
跟栈一样，队列可以用数组来实现，也可以用链表来实现。
用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。
同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。
// 用数组实现的队列
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，队空不可出队
队满条件：tail == n，队满不可入队
问题：
随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当 tail 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了
回想下讲数组删除操作时，会对删除元素的后续元素进行搬移操作，而如果每删除一个元素都搬移后面的所有元素，会导致操作开销较大，性能差，因此选择在多次删除后，进行一次总的搬移。这在JVM中的垃圾回收机制中有体现。
而对于队列的操作，和上面的思想是一致的，即当对头元素到达数组末位时，即使数组内还有空位置可以存储数据，也无法再入队了。这时候我们就要执行数据搬移
什么时候进行数据搬移？
最简单的，每次出队，会空出一个元素，此时执行一次搬移。
但这种方法的问题也很明显，就是操作频繁，使得出队的时间复杂度由O（1）升至O（n）
那怎么降低时间复杂度呢？
数据搬移实际是为了腾挪出空间，用以存储后来入队的元素。保证数组内有空余空间时，顺序队列仍可以执行入队操作。所以数据搬移的时机就出现了，即在入队的时候，发现队列末尾没有空间了，则执行一次数据搬移。
改进后的入队方法如下：
// 入队操作，将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;
}
顺序队列数据搬移
TODO：基于链表的队列实现
循环队列
基于数组实现的顺序队列会存在需要进行数据搬移的问题，入队操作性能收到影响，而如何避免进行数据搬移呢？
循环队列
队空条件：head == tail
队满条件：(tail+1)%n==head
阻塞队列和并发队列
这两种队列应用还是比较广泛的
阻塞队列：队列基础上加上阻塞的特性
即队满时不可入队，阻塞，等队列有空位时进行入队
队空时不可出队，阻塞，等队列有元素时进行出队
生产者 - 消费者模型
基于阻塞队列实现的“生产者 - 消费者模型”，可以有效地协调生产和消费的速度。同时还可以通过协调“生产者”和“消费者”的个数，来提高数据的处理效率。
多消费者的阻塞队列
在多线程情况下，会有多个线程同时操作队列，这个时候就会存在线程安全问题，那如何实现一个线程安全的队列呢？
线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。
TODO：CAS （Compare and Swap，即比较再交换，无锁操作）
参考：http://ifeve.com/compare-and-swap/
https://www.jianshu.com/p/ab2c8fce878b
CAS比较交换的过程可以通俗的理解为CAS(V,O,N)，包含三个值分别为：V 内存地址存放的实际值；O 预期的值（旧值）；N 更新的新值。当V和O相同时，也就是说旧值和内存中实际的值相同表明该值没有被其他线程更改过，即该旧值O就是目前来说最新的值了，自然而然可以将新值N赋值给V。反之，V和O不相同，表明该值已经被其他线程改过了则该旧值O不是最新版本的值了，所以不能将新值N赋给V，返回V即可。当多个线程使用CAS操作一个变量时，只有一个线程会成功，并成功更新，其余会失败。失败的线程会重新尝试，当然也可以选择挂起线程。
CAS的实现需要硬件指令集的支撑。
队列的应用
队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。
思考题解答：
方法一：非阻塞的处理方式，直接拒绝任务请求；
方法二：阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理。
基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。
而基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。
网友评论