队列

定义

队列

只允许在一端进行插入，另一端进行删除的线性表。

队列的实现同样有顺序队列和链式队列；链式队列的队头指针在链表头，即元素从队头连接到队尾。

假溢出

在顺序队列的实现中，设置头尾指针（索引），由于其先进先出的特性，若有元素出队，队尾指针也会逐渐增大，这就导致顺序表的底端存在空间无法利用，而队头指针溢出的情况，被称为假溢出。

循环队列

循环队列借助索引的模运算解决假溢出的问题，可以充分的利用顺序表的存储空间。

设循环队列的头尾指针为 $front$ 和 $rear$

操作	关系	备注
初始	$front=rear=0$
头指针加一	$front=(front+1)\%MaxSize$	出队
尾指针加一	$rear=(rear+1)\%MaxSize$	入队
队列长度	$(rear - front + MaxSize) \% MaxSize$	括号内可能不需要加一个最大长度，负数取模的效果应该相同
队空	$front=rear$

caution

入队时先将值送入队尾元素，再移动，即队尾指针指向队尾元素的下一个位置；

出队时先取队头元素，再移动。

由于队空的条件是头尾指针相同，队满就需要其他状态来表示，有三种方式：

1. 牺牲一个单元来区分，即队尾到里队头还有一个单位时就认为队满，条件为 $(rear+1)\%MaxSize==front$；
2. 额外使用一个变量来存储队列元素个数；
3. 增加一个标志，若因删除导致相同，则为队空，若因插入导致相同，则为队满。

功能

1. 存储和管理数据：存储和管理数据，最早进入队列的元素将首先被处理；
2. 缓冲区：队列常常被用作缓冲区，用于平衡生产者和消费者之间的速度差异；
3. 调度任务：如处理消息队列、作业队列等；通过将任务按顺序排列在队列中，可以确保它们按照特定的顺序进行处理；
4. 广度优先搜索：在图论和算法中，队列常用于广度优先搜索（BFS）；
5. 层次遍历：根节点入队，出队直到队列为空，每次出队时按照从左到右的顺序将该节点的孩子入队。
6. 等待处理：用于在并发编程中管理资源的访问。多个线程或进程可以将请求放入队列中，等待其他线程或进程来处理它们。这样可以有效地控制资源的访问顺序，避免竞争条件和冲突。

双端队列

双端队列

两边都可以进行入队和出队操作的队列，也可以对双端队列其中一端进行操作限制，如在一端仅允许入队，而在另一端允许入队和出队

好像没啥用。