队列(queue)：队列是只允许在-端进行插入操作，而在另-端进行删除操作的线性表。队列是一种先进先出 (First In First Out) 的线性表，简称 FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。
队列
队列（Queue）与栈一样，是一种线性存储结构，它具有如下特点：
- 队列中的数据元素遵循“先进先出”（First In First Out）的原则，简称FIFO结构。
- 在队尾添加元素，在队头删除元素。
线性表有顺序存储和链式存储，栈是线性表，所以有这两种存储方式。队列作为一种特殊的线性表，也同样存在着这两种存储方式。
二、队列的顺序存储我们假设一个队列有 n 个元素，则顺序存储的队列需建立一个大于 n 的数组，并把队列的所有元素存储在数组的前 n 个单元，数组下标为0的一端即是队头。
队列的顺序存储
顺序存储的入队操作：
所谓的入队列操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为O(1)。
顺序存储的入队操作
顺序存储的出队操作：
队列与栈不同的是，队列元素的出队是在队头，即下标为0的位置，所以队列中的所有元素都得向前移动，以保证队列的队头，也就是下标为0的位置不为空，此时时间复杂度为O(n)
顺序存储的出队操作
我们发现队列的顺序存储与现实情况非常相似，大家排队做核酸，先来的人先去做，当第一个人做完核酸离队后，其他人都向前进一位。我们可以发现，现在我们是限制了元素必须存储在顺序表的前 n 个元素，如果我们不限制元素在顺序表的位置，该如何做呢。
三、首尾指针的顺序存储front 指针指向队头元素 ， rear 指针指向队尾元素的下一个位置。假设数组的长度为 5，初始状态，空队列时 front 与 rear指针均指向下标为0的位置；
空队列
然后入队a1、 a2、 a3、a4，front指针依然指向下标为0位置，而rear指针指向下标为4的位置。
入队
出队 a1、a2 ，则front指针指向下标为2的位置， rear 不变。
出队
再入队 a5，此时数组已经溢出了，但是下标为0，1的位置实际上是空闲的。
假溢出
由上图我们发现，队列的大小是5，但实际上我们只有3个元素，由于 rear 指针已经在数组尾部，再进行入队就发生了数组的越界，这就是顺序队列的“假溢出”现象。
四、循环队列解决假溢出的办法就是后面满了，就从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。
循环队列
我们接着处理上面入队 a5元素的操作，如果是循环队列，我们可以把 rear 指针指向下标0的位置。
循环队列
接着入队a6，将它放置于下标为0处， rear 指针指向下标为1处。
入队
接着入队a7，将它放置于下标为1的位置， rear 指针指向下标为2处。
入队
此时我们发现 rear 与 front 相等，队列却满了，这不就与空队列为空的判断条件冲突了吗；在实际开发中，我们会预留一个空位置，就是数组只有一个空位置时，我们就认为队列满了。
队满
由于 rear 可能比 front大，也可能比 front小，所以尽管它们只相差一个位置时就是队满的情况，但也可能是相差整整一圈。 我们假设队列的大小为QueueSize。
- 空队列：rear=front；
- 队列满：(rear 1) % QueueSize=front
- 队列元素的个数：(rear-front QueueSize) %QueueSize
队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已， 我们把它简称为链队列 。为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。
队列的链式存储结构
空队列时， front和 rear都指向头结点。
空队列
数据结构：
class Node<T>{
//数据
T data;
//下一个元素指针
Node next;
}
class Queue{
//头指针
Node front;
//尾指针
Node rear;
}
1、键盘的输入与输出，比如你微信聊天输入god，由于队列是先进先出所以出来就是 god，如果是栈就是 dog。
2、打印机的任务
3、编程语言中线程池的任务队列
4、现在很多的消息中间件MQ
5、图的遍历
,
