栈和队列的应用 —— 顺序队列

栈和队列的应用 —— 顺序队列

在只有一个车道的单行道上，小汽车呈线性排列，只能从一端进，从另一端出，先进先出（First In First Out，FIFO）。

这种先进先出的线性序列，被称为“队列”。

队列也是一种线性表，只不过它是操作受限的线性表，只能在两端操作：从一端进，从另一端出。进的一端被称为队尾（rear），出的一端被称为队头（front）。

队列可以采用顺序存储，也可以采用链式存储。

【顺序队列】

队列的顺序存储指用一段连续的空间存储数据元素，用两个整型变量记录队头和队尾元素的下标。

顺序队列的数据结构定义（动态分配）：

在顺序队列定义好了之后，还要先定义一个最大的分配空间，顺序结构都是如此，需要预先分配空间，

因此可以采用宏定义：

#define Maxsize 100  //预先分配空间，这个数值根据实际需要预估并确定
1

结构体定义也可以采用静态分配形式，使用一个定长数组存储数据元素，用两个整型变量记录队头和队尾元素的下标。

顺序队列的数据结构定义（静态分配）：

注意： 队列只能从一端进，从另一端出，不允许在中间进行查找、取值、插入、删除等操作，先进先出是人为规定的，如果破坏了此规则，就不是队列了。

【完美图解】

假设现在顺序队列Q分配了6个空间，然后进行入队和出队操作（Q.front和Q.rear都是整型下标）。

① 开始时为空队，Q.front = Q.rear;

② 元素a1 进队，放入队尾Q.rear的位置，Q.rear后移一位。

③ 元素a2 进队，放入队尾Q.rear的位置，Q.rear后移一位。

④ 元素a3 、a4 、a5 分别按顺序进队，队尾Q.rear依次后移。

⑤ 元素a1 出队，队头Q.front后移一位。

⑥ 元素a2 出队，队头Q.front后移一位。

⑦ 元素a6 进队，放入队尾Q.rear的位置，Q.rear后移一位。

⑧ 元素a 7 进队，此时队尾Q.rear已经超过了数组的最大下标，无法再进队，但是前面明明有两个空间，却出现了队满的情况，这种情况被称为“假溢出”。

进行完 步骤 ⑦ 后，队尾Q.rear要后移一个位置，此时已经超过了数组的最大下标，即Q.rear+1=Maxsize（最大空间数6），那么如果前面有空闲，Q.rear就可以转向前面下标为0的位置

元素a7 进队，被放入队尾Q.rear的位置，然后Q.rear后移一位，

元素a8 进队，被放入队尾Q.rear的位置，然后Q.rear后移一位

这时，虽然队列空间已存满，但是出现了一个大问题：当队满时，Q.front=Q.rear，这和队空的条件一模一样，无法区分到底是队空还是队满。
如何解决呢？有两种办法：

• 一种办法是设置一个标志，标记队空和队满；
• 另一种办法是浪费一个空间，当队尾Q.rear的下一个位置是Q.front时，就认为队满，

到达尾部又向前存储的队列被称为循环队列，为了避免“假溢出”，顺序队列通常采用循环队列。