队列的定义
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列的特点就是先进先出(First In First Out)。
顺序队列
建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置。
如果没有两个指针，入队操作直接执行顺序表尾部插入操作，其时间复杂度为O(1)，出队操作直接执行顺序表头部删除操作，其时间复杂度为O(n)，
增加了front和rear指针，出队操作的时间复杂度也是O(1)了。
空队列：
往队列里面插入A：
继续插入元素：
将A和B出队：
继续将D、E、F、G入队：
由于队列暂时”已满”，G将无法入队，但是此时front前面实际上还有未被利用的空间，这称为"假上溢"现象。
之所以出现这样”假溢出”现象是因为顺序表队列的存储单元没有重复利用机制，而解决该问题的最合适的方式就是将顺序队列设计为循环结构。
“下溢”现象
当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
“真上溢”现象
当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
“假上溢”现象
由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为”假上溢”现象，如上面的图解。
循环队列
循环队列就是将顺序队列设计为在逻辑结构上首尾相接的循环结构，使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。自己真从MaxSize-1增1变到0，可用取余运算(rear+1)%MaxSize和(front+1)%MaxSize来实现（如果front和rear是从1开始的，则无需+1）。
这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列。
向循环队列插入A：
继续插入B、C（每次入队rear都在增1）：
将A、B、C出队（每次出队front都在增1）：
重新插入A、B、C（此时队列出现”假上溢”现象，使用(rear+1)%MaxSize计算rear）：
继续将A、B、C出队（此时队列出现”假上溢”现象，使用(front+1)%MaxSize计算front）：
重新插入直至队列出现”真上溢”现象，然后可以动态对循环队列进行扩展（并按照原来队列的次序复制元素数组）：
链式队列
基于链表的队列，要动态创建和删除节点，效率较低，但是可以动态增长，可以使用带头指针front和尾指针rear的单链表实现，front直接指向队头的第一个元素，rear指向队尾的最后一个元素。
队列采用的FIFO(first in first out)，新元素（等待进入队列的元素）总是被插入到链表的尾部，而读取的时候总是从链表的头部开始读取。每次读取一个元素，释放一个元素。所谓的动态创建，动态释放。因而也不存在溢出等问题。由于链表由结构体间接而成，遍历也方便。
空链式队列：
插入元素（入队）：
出队和入队都分别改变front和rear的指向即可。
优先队列
在某些情况下，有些应用系统要求不仅需要按照“先来先服务”的原则进行，而且还需按照任务的重要或紧急程度进行排队处理，此时就需要使用到优先队列。比如在操作系统中进行进程调度管理，每个进程都具备一个优先级值以表示进程的紧急程度，优先级高的进行先执行，同等级进程按照先进先出的原则排队处理，此时操作系统使用的便是优先队列管理和调度进程。
优先队列也是一种特殊的数据结构，队列中的每个元素都有一个优先级，按照排序可分类为：
- 降序优先级队列：每次出队的是队列当前具有最高优先级的元素。
- 升序优先级队列：每次出队的是队列当前具有最低优先级的元素。
优先队列的实现可以有三种方案：
- 有序数组
- 有序链表
- 也可以使用二叉树（二叉堆）实现
双端队列
双端队列可以在队列任意一端入队和出队。此外，经常还会有一个查看（Peek）操作，返回该端的数据而不将其出队。
队列的应用
- 异步数据的处理、传输；
- 短信群体发送 应用的发布订阅模式；
- 模拟真实的订单服务、售票，以及其他先到先服务的场景。
Java中的队列
非阻塞队列
- PriorityQueue
- ConcurrentLinkedQueue
阻塞队列
- ArrayBlockingQueue
- LinkedBlockingQueue
- PriorityBlockingQueue
- DelayQueue
- SynchronousQueue