队列
# 队列基础
队列
队列跟栈一样，也是一种操作受限的线性表数据结构。
作为一种非常基础的数据结构，队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。
它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等
# 顺序队列
用数组实现的队列叫作顺序队列
指针
- 队头指针——出队，右移，加一
- 队尾指针——入队，右移，加一
- 队列满与空
- 当head==tail时队列空。
- 当tail位于数组末尾时，没有空间在提供给入队的元素
- 若head位于最前面，则是真正的队满
- 若head位于中间位置，则是虚假的队满，称为假溢出
数据搬移——解决假溢出现象
随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当 tail 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。
- 解决办法
如果没有空闲空间了，我们只需要在入队时，再集中触发一次数据的搬移操作
# 循环队列
循环队列可以避免数据搬移
队满判断--size 为数组大小
==$(tail+1)%size=head$==
队空判断
==$tail=head$==
队头，队尾指针增加
==$tail=(tail+1)%size$==
==$head=(head+1)%size$==
# 链式队列
特征
- 空间无限大，不受约束。
- 只允许在队尾，即尾指针处插入(入队)，即尾插法。
- 只允许在队头，即头指针处，出队。
# 阻塞队列和并发队列
阻塞队列
阻塞队列其实就是在队列基础上增加了阻塞操作
就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；
如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。
并发队列
线程安全的队列我们叫作并发队列
实现方式1——加锁
最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。
实现方式2——CAS原子操作
实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。
考虑使用CAS实现无锁队列，则在入队前，获取tail位置，入队时比较tail是否发生变化，如果否(==这说明刚刚没有其他进程实现了入队操作==)，则允许入队，反之，本次入队失败。出队则是获取head位置，进行cas。
# 队列在线程池等有限资源池中的应用
实际上，对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。
问题
当我们向固定大小的线程池中请求一个线程时，如果线程池中没有空闲资源了，这个时候线程池如何处理这个请求？是拒绝请求还是排队请求？各种处理策略又是怎么实现的呢？
解答
请求处理
第一种是非阻塞的处理方式，直接拒绝任务请求；
另一种是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理。
处理排队请求
我们希望公平地处理每个排队的请求，先进者先服务，所以==队列==这种数据结构很适合来存储排队请求。
- 基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。
- 而基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。
