数据结构学习笔记（四）队列

大家好，经过前三篇数据结构文章的学习。对于数组和链表以及线性结构的应用——栈有了初步的认识，这篇文章趁热打铁学习线性结构的另外一种应用——队列

概念

队列(Queue)是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。综上，只要能满足“先进先出”条件的线性表，称之为队列。

概念看完了我们接着来。首先看队列有几种形式，第一种静态队列和第二种动态队列。类似于栈的两种形式，静态队列是用数组实现的，而动态队列的核心是链表。

静态队列

我们知道队列有几个专有名词：前端(front)、后端(rear)、队尾、队头、入队。那如何创建一个队列呢？

类似排队买票，有队头队尾买完票走掉，和新来的人排在队伍的后方。在这里，我用一个数组来模拟人们排队买票的情景，首先指定一个元素指向队伍最前面的那个人，自然就有另一个元素代表队尾。当队伍后方有人来排队的时候，需要将队尾元素指向这个人，有人离开队伍时，应该将队头变量指向离开的人的后一个人。

在前面的三篇笔记中，无论是链表还是栈都预留了一个“无意义”的结点，来充当头结点或尾结点。这里我们也保留这个优良传统，我们定义，队尾变量永远指向最后一个有效元素的后一个元素。

现在我们有一个长度为6的数组，它的下标自然为0、1、2、3、4、5

front保存了队头的下标值，rear保存了队尾最后一个有效元素的下一个元素的下标值。

第一种情况，front为0，rear为5指向数组的最后一个元素，当再进行入队操作时，首先把值存入当前r保存的下标值对应的元素中，然后把rear加一，但是，如果再加一，数组就会越界。然而此时又不宜如栈那样，进行存储再分配扩大数组空间，因为队列的实际可用空间并未占满。

第二种情况，f指向队头，r指向最后一个有效元素的下一个元素，每次入队r都会加一，假如现在r增加到了4，想进行出队操作(此时队列中有4个元素)，需要将f增加，f增加到了2，此时相当于只剩2个元素，删除了前两个元素，这样就会造成我们被删除的位置永远无法再被利用，就会造成空间的浪费。所以，一般的数组就达不到要求了，所以静态队列需要用循环队列。

循环队列

在正式学习循环队列之前，先要弄清楚几个问题：

根据前面的描述，创建循环队列需要2个参数来确定front，rear。

1.两个参数代表的含义始终是一样的吗？

在这里两个参数在不同的场合下有不同的含义：

(1)初始化队列时：front和rear都是0

(2)队列非空时：front代表队列的第一个元素，rear则代表的是最后一个有效元素的下一个元素

(3)队列为空时，front和rear的值相等，但不一定是0

2.如何判断队列为空?

这个问题简单，front的值和rear相等即可

3.如何判断队列已满

再循环队列中，如果每个结点都放上元素，front和rear就会重合，这样无法判断队列的当前状态了，所以一个长度为N的队列存放N-1个元素，对应代码(rear + 1) % len == f 判断这个表达式的布尔值即可。

实战

老规矩，先定义队列的基本结构

类似于上文的创建空队列的方法，将front和rear的值都等于0，分配的空间赋给pBase

定义一些循环队列基本的函数

其中，入队的写法要注意先判断当前队列是否已满。队列不是满的状态下，

把值放在rear下标对应的元素里。而后，将rear的值通过rear+1和长度取余的方式，让rear往后走一个

全部代码

END