# 队列

队列是只允许一端进行插入（入队或进队），一端进行删除（出队或离队）的线性表。即先进先出$FIFO$。

队列允许插入的一端就是队尾，允许删除的一端就是队头。

队列和栈是逻辑结构和物理结构没有不同，只是操作方式不同。

## 顺序队列

分配一块连续的存储单元存放队列中的元素，并附设两个指针，队头指针和队尾指针，队头指针指向队头元素，队尾指针指向队尾元素的下一个位置。

### 顺序队列操作

#### 顺序队列插入

如果出队，则前面的空间会空闲，但是假如队尾指针会依照插入而不断加$1$，则我们的队尾指针最后会指向最后一个区域，计算机不知道前面是怎么样，所以就认为空间已经满了，实际上没有。这就是假溢出。

#### 顺序队列删除

当如果我们必须保证所有的存储空间被利用，可以定义一个$size$表明队列当前的长度，就可以完全利用所有空间。

## 循环队列

对于顺序队列假溢出的解决的方法就是使用模运算，将队尾指针不仅仅是加一，而是加一后再取整个静态数组大小$MAXSIZE$的模，这样如果队列尾指针超过了范围也仍能回到最开始插入数据。这时候物理结构虽然是线性的，而逻辑上已经变成了环型的了。

所以与此同时，队列已满的条件也不再是队尾指针$=MAXSIZE$了，而是队尾指针的下一个指针是队头指针，这里最后一个存储单元是不能存储数据的，因为如果存储了数据那么头指针就等于尾指针，这在我们的定义中是空队列的意思。但是如何判断满队？

1. 牺牲最后的一个存储单元。入队少用一个队列单元。队满条件：$(rear+1)\%MAXSIZE==front$，队空条件$front==rear$，从而队列元素个数$=(rear+MAXSIZE-front)\%MAXSIZE$。
2. 增设一个用来表示数据个数的成员。队满条件$length==MAXSIZE$，队空条件$length==0$。队空和队满都是$front==rear$。
3. 可以定义一个$int$类型的$tag$，当进行删除操作就置$tag$为$0$，插入操作时置$tag$为$1$，只有删除才可能队空，只有插入才可能队满，所以就可以根据这个来判断。队空和队满都是$front==rear$。

## 链队

定义链队需要定义一个队头指针和一个队尾指针，队头指向队头结点，队尾指向队尾结点，即单链表最后一个结点，这跟顺序存储不同。

由于带头节点的链表对于出队比较简单，所以一般都定义为带头节点的链表。

## 双端队列

双端队列：只允许从两端插入、两端删除的线性表。

输入受限的双端队列：只允许从一端插入，两端删除的线性表。

输入受限的双端队列：只允许从一端删除，两端插入的线性表。

## 队列应用

### 树的层次遍历

1. 根结点入队。
2. 若队空（所有结点都已处理完毕)，则结束遍历，否则重复三操作。
3. 队列中第一个结点出队，并访问之。若其有左孩子，则将左孩子入队；若其有右孩子，则将右孩子入队，返回二。

+ 图的广度优先遍历。
+ 进程争用$FCFS$策略。

### 计算机系统

+ 解决$CPU$与外设速度不匹配问题。
+ 解决请求处理机问题。