引言
CPU资源有限，任务的处理速度与线程个数并不是线性正相关。过多的线程会导致CPU频繁切换，处理性能下降。
当我们向固定大小的线程池中请求一个线程时，如果线程池中没有空闲资源了，这个时候线程池如何处理这个请求？是拒绝请求还是排队请求？各种处理策略又是怎么实现的呢？
这就需要用到队列这个数据结构
如何理解队列
理解成，排队购票，排在前面的先买，排在后面的后买。即先进者先出（FIFO）。
队列跟栈非常相似，支持的操作也有限，最基本的也是两个：入队和出队，一端出队，另一端入队；所以队列也是一种操作受限的线性表数据结构。
顺序队列和链式队列
用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。
顺序队列
不理想的设计：
1 . 若使用顺序表的尾端插入实现enqueue操作，根据队列性质，出队操作应该在表的首端进行。为了维护顺序表的完整性（表元素在表前端连续存放），出队操作取出当时的首元素后，就需要把表中其余元素全部前移，这样就会是一个 O(n) 时间的操作。
2 . 反过来：从尾端出队是 O(1) 操作，但从首端入队就是 O(n) 时间操作，这种设计也不理想。
3 . 另一种是在队首元素出队后表中的元素不前移，但记住新队头位置。如果队列中没有空闲了，只需要在入队时，再集中触发一次数据的搬移操作。
链式队列
最简单的单链表只支持首端 O(1) 的操作，在另一端操作需要 O(n) 时间。不适合作为队列的实现基础。
考虑带表尾指针的单链表，它支持 O(1) 时间的尾端插入操作；再加上表首端的高效访问和删除，基于单链表实现队列就很容易。
示例
class LNode:
def __init__(self, elem, next_=None):
self.data = elem
self.next = next_
class QueueUnderflow(ValueError):
pass
class LQueue:
def __init__(self):
self._head = None
self._rear = None
def is_empty(self):
return self._head is None
def peek(self):
"""查看队列最早元素，不删除"""
if self._head is None: #是空队列
raise QueueUnderflow('in peek of Queue')
else:
return self._head.data
def dequeue(self):
"""删除队列头结点，并返回这个结点里的数据"""
if self._head == None:
raise QueueUnderflow("in dequeue")
e = self._head.data
self._head = self._head.next
return e
def enqueue(self, elem):
if self._head is None:#空表
self._head = LNode(elem, self._head)
self._rear = self._head
else:
self._rear.next = LNode(elem)
self._rear = self._rear.next
循环队列
一个具体的实现示例：基于Python的list实现顺序表示的循环队列。
考虑定义一个可以自定扩充存储结构的队列类。
注：不能直接利用list的自动存储扩充机制。两个原因：
1 . 队列元素的存储方式与list元素的默认存储方式不一致；list元素总在其存储器的最前面一段，而队列的元素可能是表里的任意一段，有时还分为头尾两段。
2 . list没有提供检测元素存储区容量的机制，队列操作中无法判断系统何时扩容。
示例
class SQueue():
def __init__(self, init_len = 8):
self._len = init_len #存储区长度
self._elems = [0] *init_len #元素存储
self._head = 0 #表头元素下标
self._num = 0 #元素个数
def is_empty(self):
return self._num == 0
def peek(self):
if self._num is None: #是空队列
raise QueueUnderflow('in peek of SQueue')
return self._elems[self._head]
def dequeue(self):
if self._num == 0:
raise QueueUnderflow('in dequeue of SQueue')
e = self._elems[self._head]
self._head = (self._head+1)%self._len
self._num -= 1
return e
def enqueue(self,e):
if self._num == self._len: #队满时
self._extend()
self._elems[(self._head+self._num)%self._len] = e
self._num += 1
def _extend(self):
old_len = self._len
self._len *= 2
new_elems = [0]*self._len #扩大元素存储区
for i in range(old_len): #将原有元素搬迁到新表里（最前面的位置）
new_elems[i] = self._elems[(self._head+1)%old_len]
self._elems, self._head = new_elems, 0
注解
1 . 队列对象的4个属性，_elems，_head，_num，_len的作用分别是：存放队列元素，记录队列首元素所在位置的下标，记录表中元素个数，记录当存储区的有效容量（便于换存储表）。
2 . 在_num = _len 的情况下（队满）出现入队操作，就扩大存储区；队空就是 _num == 0。
3 . 队列里的元素总保存在_elems里，从_head开始的连续位置中。
4 . 新入队的元素存入在 (_head + _num)%len 算出的位置；若需要把元素存入下标_len的位置时，改为在下标0位置存入。
5 . 在_extend函数中新元素尚未入队，但_extend在enqueue返回后，enqueue的最后两句语句将正常完成这个工作。
阻塞队列
阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。
注：可以用阻塞队列实现一个“生产者-消费者模型”。基于阻塞队列，可以通过协调“生产者”和“消费者”的个数，来提高数据的处理效率。
并发队列
在多线程情况下，会有多个线程同时操作队列，这个时候就会存在线程安全问题。
要实现一个线程安全的队列就需要并发队列。
最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。
解答引言
一般有两种处理策略。
- 第一种是非阻塞的处理方式，直接拒绝任务请求；
- 另一种是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理。
那如何存储排队的请求呢？
公平地处理每个排队的请求，先进者先服务，所以队列这种数据结构很适合来存储排队请求。
队列有基于链表和基于数组这两种实现方式。两种实现方式对于排队请求又有什么区别呢？
基于链表的实现方式
可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。
所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。
基于数组的实现方式
可以实现的是有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。
这时，设置一个合理的队列大小，就非常重要。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。
注：对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过
队列这种数据结构来实现请求排队。
思考
队列的其他应用
1 . 文件打印
2 . 万维网服务器
3 . Windows系统和消息队列
4 . 离散事件系统模拟