队列在线程池等有限资源池中的应用
本文创作灵感来源于 极客时间 王争老师的《数据结构与算法之美》课程，通过课后反思以及借鉴各位学友的发言总结，现整理出自己的知识架构，以便日后温故知新，查漏补缺。
是什么
什么是队列
- 队列也是一种操作受限的线性数据结构，只提供入列和出列两种操作，遵循先进先出原则：先入列的元素优先出列
- 队列中又区分了普通队列，循环队列，阻塞队列以及并发队列。不同的类型有着不同的实际应用，尤其是在底层系统，框架和中间件中发挥着巨大作用。
为什么
为什么有队列这种数据结构
- 特定的数据结构是为了解决特定的某一类问题，而队列这种特殊的线性数据结构也有着其特殊的作用。正如栈遵循的先入先出原则一样，现实生活中的排队现象就是队列的一个很好体现。先排队的人，优先享受服务，后排队的人，要等前面的人都被服务过之后，才轮到自己。
怎么办
怎么学习队列这种数据结构
- 队列根据其实现方式的不同又区分了顺序队列和链式队列，而从功能上又区分普通队列，循环队列，阻塞队列和并发队列。
顺序队列
- 顺序队列：队列实现的方式是数组。简单实现代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52class ArrayQueue{
private String[] queueList;//队列
private int first;//队头元素下标
private int last;//队尾元素下标
private int n;//队列大小
//初始化队列
public ArrayQueue(int length){
this.queueList = new String[length];
this.first = 0;
this.last = 0;
this.n = length;
}
//入队
public boolean enQueue(String item){
//队尾元素下标等于队列长度，说明队列末尾不能入队了
if(last == n){
/**
* 队头元素下标不为0，说明当前数组前面有空余位置，
* 这个时候需要对队列中的元素搬移位置，使得队列中的
* 元素都从数组的第一个位置排列
*/
if(first != 0){
for(int i = first;i < last; i++){
queueList[i-first] = queueList[i];
}
last = last - first;
first = 0;
queueList[last] = item;
last++;
return true;
}else{
return false;
}
}else {
return false;
}
}
//出列
public String deQueue(){
//判断队列是否为空
if(first == last){
return null;
}else{
String item = queueList[first];
first++;
return item;
}
}
}
用数组实现的队列，每次出列的时候，取出数组中下标为 first 的元素，然后 first 自增一。每次入列的时候，数组下标为 last 的位置存储元素，last 自增一。出列的情况，我们只需判断当时的队列是否为空队列就够了。但是，入列的时候，由于出列导致 first 值一直在自增，入列导致 last 值也在自增，那么数组势必会存储到最后一个元素，而数组的前面由于出列，空余出了一些位置。所以，这个时候我们就需要把数组中的元素整体搬移到数组的最前面，为后续入列提供空间。数据搬移的时候，我们要考虑好边界条件：first 值不等于 0 且 last 值等于数组的长度
链式队列
- 链式队列：队列实现的方式是链表。简单实现代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42class LinkQueue{
class Node{
String data;//数值域
Node next;//指针域
}
private Node first;//队列头结点
private Node last;//队列尾节点
//初始化队列
public LinkQueue(){
this.first.next = null;
this.last.next = null;
}
//入列
public boolean enQueue(Node node){
//空队列
if(first.next == null && last.next == null){
first.next = node;
last.next = node;
return true;
}else{
last.next.next = node;
last.next = node;
return true;
}
}
//出列
public Node deQueue(){
//判断是否为空列
if(first.next == null && last.next == null){
return null;
}else{
Node node = first.next;
node.next = null;//释放内存
first.next = first.next.next;
return node;
}
}
}
链式队列中，我们需要额外创建两个节点，一个是头节点一个是尾节点，分别指向第一个元素和最后一个元素。队列为空的条件就是两个指示节点都指向 null 。由于链表可以自由的申请内存空间，所以链式队列理论上是可以无限大的。
循环队列
- 循环队列顾名思义就是一个环形的队列，首尾相连。相对于普通的数组实现的队列来说，我们不用在做数据搬移的工作了，只要队列未满，我们就可以直径二入队。简单实现代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36class CircularQueue{
private String[] queueList;//队列
private int first;//队头元素下标
private int last;//队尾元素下标
private int n;//队列大小
//初始化队列
public CircularQueue(int length){
this.queueList = new String[length];
this.first = 0;
this.last = 0;
this.n = length;
}
//入队
public boolean enQueue(String item){
if((last + 1) % n == first){
return false;
}else {
queueList[last] = item;
last = (last + 1) % n;
return true;
}
}
//出列
public String deQueue(){
if(first == last){
return null;
}else{
String item = queueList[first];
first = (first + 1) % n;
return item;
}
}
}
从代码中我们发现两个公式 (last + 1) % n 和 (first + 1) % n。通过对比发现，当队列满的时候：(last + 1) % n = first。从而得出上述两个出列与入列时候的标识位获取新值的公式。注：上述循环链表中的最后一个位置是不能存储元素的，因为一旦入队，last == first 就成立了，队列就是一个空列，但是实际上是已经存储满了。
阻塞队列和并发队列
- 阻塞队列就是对队列的操作添加了受限条件：当队列为空的时候，出队操作就会被阻塞；如果队列满了，那么入列操作就会阻塞。这正好是一个消费者与生产者的模型。
- 并发队列就是线程安全的队列，简单的操作就是在入队出队的操作上加锁。王争老是提到基于数组的循环队列，利用CAS原子操作，可以实现非常搞笑的并发队列。这个概念我还是第一次听过，接下来我会好好查找资料，研究一番，后续单独在写一篇文章记录。
队列在线程池等有限资源池中的应用
- 非阻塞方式，直接拒绝请求
- 阻塞方式，将请求排队，依次分配资源。
- 对大部分有限资源的请求使用，当没有资源的时候，都是基于队列的形式实现排队请求的。
- 链表实现了无界队列，但是肯能会导致过多的请求排队，导致请求时间过长，对于敏感系统来说弊端很大。
- 数组实现了有界队列，当请求数量超过队列拥有资源的数量的时候，新的i请求会被拒绝。但是，如何恰当的分配队列数组的大小，也是一个很复杂的实现。
总结
初入算法学习，必是步履蹒跚，一路磕磕绊绊跌跌撞撞。看不懂别慌，也别忙着总结，先读五遍文章先，无他，唯手熟尔~
与诸君共勉