当我们向固定大小的线程池中请求一个线程的时候，如果线程池中没有空闲资源了，这个时候线程池如何处理这个请求？是拒绝请求还是排队请求？各种处理策略又是怎么实现的呢？
如何理解队列？
队列可以理解成我们买包子，先到的人先买，后来的人后买。先入先出，后入后出。
和栈类似，队列也只有两个操作，一个是入队列enqueue，把元素加入到队列的尾部，一个是出队列dequeue，把元素从队列的头部移除。
出入队列
顺序队列和链式队列
- 顺序队列
/**
* SequenceQueue
*/
public class SequenceQueue {
String[] queue;
//head是队列的头部位置
int head;
//bottom是队列的尾部位置
int bottom;
int length;
SequenceQueue(int n) {
queue = new String[n];
head = 0;
bottom = 0;
length = n;
}
//出队列
String deQueue() {
if (head >= bottom) {
System.out.print("队列为空，不能够再出队列");
return null;
}
String item = queue[head];
head++;
return item;
}
//入队列
boolean enQueue(String item) {
if (bottom >= length) {
System.out.print("队列已满，不能够再添加数据");
return false;
}
queue[bottom] = item;
bottom++;
return true;
}
}
- 链式队列
/**
* ChainQueue
* 写的很简陋，不知道链式队列有没有设置大小的需求，所以画蛇添足的加上去了。
*/
public class ChainQueue {
// head表示队列头部
Item head;
// bottom表示队列尾部
Item bottom;
int length = 0;
int max;
Item dummy = new Item("");
ChainQueue(int n) {
head = dummy;
bottom = dummy;
max = n;
}
// 入队列
boolean enQueue(Item newItem) {
if (length >= max) {
System.out.print("队列已满，不能再添加数据");
return false;
}
bottom.next = newItem;
bottom = bottom.next;
length++;
return true;
}
// 出队列
Item deQueue() {
if (head.next == null || length <= 0) {
System.out.print("队列为空，不能够移除数据");
return null;
}
Item temp = head;
head = head.next;
length--;
return temp;
}
}
class Item {
Item next;
String content;
Item(String content) {
this.content = content;
}
}
不管是顺序栈还是链式栈，我们都需要两个指针，一个指向栈头，一个指向栈尾。
对于顺序栈来说存在栈满的情况，根据我们前面学到的知识，我们可以把栈中的数据统一向栈头移动。
顺序链移动数据
// 入队列
boolean enQueue(String item) {
if (bottom == max) {
if (head == 0) {
System.out.print("队列已满，不能够再添加数据");
return false;
}
for (int i = head; i < bottom; i++) {
queue[i - head] = queue[head];
}
bottom = max - head;
head = 0;
}
queue[bottom] = item;
bottom++;
return true;
}
循环队列
循环队列如下图所示
循环队列
写好一个循环队列的关键是判断好队列为空和满的情况。
- 队列为空：head == tail
- 队列为满: (tail + 1)/length == head
/**
* CircleQueue
*/
public class CircleQueue {
String[] circleQueue;
int head;
int tail;
int length;
CircleQueue(int length) {
this.length = length;
head = 0;
tail = 0;
}
//出队列
String deQueue() {
if (head == tail) {
System.out.print("队列为空，不能取出数据");
return null;
}
return circleQueue[tail--];
}
//入队列
boolean enQueue(String item) {
//对于环形队列，需要使用如下来判断队列是否满
if ((tail + 1) % length == head) {
System.out.print("队列已满，不能插入数据");
return false;
}
circleQueue[tail] = item;
//环形队列的核心，如果超过队列的范围，那么从队列头重新开始，这样就不用移动数据了
tail = (tail + 1)/length;
return true;
}
}
阻塞队列和并发队列
阻塞队列就是在队列的基础上增加了阻塞的操作，即队列为空的时候，从队列头取数据会被阻塞，直到队列不为空的时候再获取。当队列满的时候，从队列尾插入数据会被阻塞，直到队列不满的时候再插入。
上述定义即为一个生产者消费者模型，因此使用阻塞队列能够很容易的实现该模型。
使用阻塞线程就必然涉及到多线程下队列的插入删除功能，这个时候就需要使用并发队列了。最简单的方式就是在enQueue()和deQueue()方法中加锁。但是锁的并发粒度比较低，同一时刻只能够进行一次操作。基于数组的循环队列，使用CAS操作就可以实现非常高效的并发队列，这也是循环队列比链式队列使用更广泛的原因。
队列如何在线程池中使用
当线程池中线程已经全部被使用的情况下，如果有新的消息传过来，有两种方式进行处理，一种是直接拒绝，第二种是将其保存在队列中。
- 链式队列无限长，可能会导致缓存的待处理消息较多，对于那些响应时间敏感的系统来说并不适用。
- 顺序队列长度有限，可以将其长度选为一个较小的值，从而实现对消息的较短时间内相应。
对于大多数资源有限的场景，没有空闲资源的时候，都可以通过队列这种数据结构来进行请求排队。
