队列(Queue)：具有先进先出的特性，支持在队尾插入元素，在队头删除元素的特性。
队列是一种操作受限的线性表数据结构，包含两个操作，入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。
用数组实现的队列，我们叫作顺序队列，用链表实现的队列，我们叫作链式队列。
队列的数组实现
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
|
public class ArrayQueue {
private String[] items;
private int n = 0;
private int head = 0;
private int tail = 0;
public ArrayQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
public boolean enqueue(String item) {
if (tail == n) {
if (head == 0) return false;
for (int i = head; i < tail; ++i) {
items[i-head] = items[i];
}
tail -= head;
head = 0;
}
items[tail] = item;
++tail;
return true;
}
public String dequeue() {
if (head == tail) return null;
String ret = items[head];
++head;
return ret;
}
}
|
队列的链表实现
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
| public class LinkedQueue {
private Node head = null;
private Node tail = null;
private static class Node {
int value;
Node next;
public Node(int value) {
this.value = value;
this.next = null;
}
}
public boolean enqueue(int value) {
Node newNode = new Node(value);
if (head == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
return true;
}
public int dequeue() {
if (head == null) {
return -1;
}
Node node = head.next;
int value = node.value;
head = node;
return value;
}
}
|
循环队列
具有队头指针和队尾指针，指示队列元素所在的位置，避免删除元素时移动大量元素。
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
| public class CircularQueue {
private String[] items;
private int n = 0;
private int head = 0;
private int tail = 0;
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;
if (head == tail) return null;
String ret = items[head];
head = (head + 1) % n;
return ret;
}
}
|
阻塞队列
阻塞队列其实就是在队列基础上增加了阻塞操作。
在队列为空的时候，从队头取数据会被阻塞；队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。
生产者 - 消费者模型
当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了。这个时候，生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续“生产”。
并发队列
线程安全的队列我们叫作并发队列。
直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。
问题
线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？各种处理策略又是如何实现的呢？
两种处理策略;
第一种是非阻塞的处理方式，直接拒绝任务请求；另一种是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理
队列两种实现方式对于排队请求有什么区别呢？
基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。
而基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。
对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。