队列（定义，基本操作，顺序存储，链式存储）

1.队列的定义

队列( Queue）是只允许在一端进行插入，在另一端删除的线性表。
特点：先进入队列的元素先出队。（先进先出）First ln First Out ( FIFO)

1.重要术语

①队头：允许册除的一端。
②队尾：允许插入的一端。
③空队列

2.基本操作

1. InitQueue(&Q):初始化队列，构造一个空队列Q。
2. DestroyQueue(&Q):销毁队列。销毁并释放队列Q所占用的内存空间。
3. EnQueue(&Q,x):入队，若队列Q未满，将x加入，使之成为新的队尾。
4. DeQueue(&Q,&x):出队，若队列Q非空，删除队头元素，并用x返回。
5. GetHead(Q,&x):读队头元素，若队列Q非空，则将队头元素赋值给x。
6. QueueEmpty(Q):判队列空，若队列Q为空返回true，否则返回false。

2.队列的顺序存储

用静态数组存放数据元素，设置队头/队尾(front/rear)指针。

①rear：指向队尾元素的后一个位置(下个应该插入的位置)
②front：指向队头元素。

1.基本操作

1.初始化

2.判空

3.入队（循环队列）

模运算将无限的整数域映射到有限的整数集合{0,1,2,…, b-1}上，将存储空间在逻辑上变成了“环状”。
因此将这种存储空间在为环状的队列称为循环队列。

循环队列已满的条件：队尾指针的再下一个位置是队头，即$(Q.rear+1)\%MaxSize==Q.front$.
代价：牺牲一个存储单元。

4.出队

5.读队头

2.判断队列已满/已空

①使用模运算的方式：
计算队列元素个数：$(rear+MaxSize-front)\%MaxSize$
队列已满的条件：队尾指针的再下一个位置是队头，即$(Q.rear+1)\%MaxSize==Q.front$.

②在队列的结构体定义中加入一个size变量记录当前队列的长度
插入成功size++;
删除成功size–;

③结构体中设置一个标记变量tag,记录最近一次操作为删除或者插入
每次删除操作成功时，都令tag=0;
每次插入操作成功时，都令tag=1;
只有删除操作，才可能导致队空。
只有插入操作，才可能导致队满。
队满条件：$front==rear\&\&tag==1$
队空条件：$front==rear\&\&tag==0$

3.队列的链式存储

1.基本操作（带头结点）

1.初始化

2.判空

3.入队

4.出队

5.队满条件

链式存储：一般不会队满，除非内存不足。

4.双端队列

只允许从两端插入、两端删除的线性表。
在栈中合法的输出序列，在双端队列中必定合法。

1.输入受限的双端队列

允许从两端删除、从一端插入的队列。

2.输出受限的双端队列

允许从两端插入、从一端删除的队列。