3.6 循环队列在线视频

同学们大家好

我是云南大学信息学院教师孔兵

这一节我们继续讨论循环队列

队列的顺序表示和实现

循环队列是利用顺序映象实现队列的存储

看一下存储结构的定义

首先定义一个队列的容量100

队列的存储被定义为一个结构体

仍然采用动态申请空间的方法

获得队列的存储空间

结构体中包含三个成员

一个是指向数据元素的指针base

它指向队列分配空间存储空间的起始地址

我们把它当做一个数组名来使用

另外两个成员都是整型数front和rear

front中记录队头元素所在存储单元的下标

Rear记录队尾元素所在单元的下一个位置的下标

后面为了讨论的方便

我们仍然把它们称为循环队列中的头指针和尾指针

当然我们要知道，这实际上是存储下标的两个整型变量

这样的设计也是为了方便实现入队列和出队列操作

Typedef给这个结构体起了个类型名，SqQueue

下面我们通过图示来看一下

入队列和出队列操作当中的一些问题

先来看入队列操作

首先用SqQueue声明一个队列Q

队列的初始化也是分配队列存储空间

让Q.base指向分配空间的起始地址

队头指针Q.front和队尾指针Q.rear都初始化为0

这时Q.front==Q.rear

这个时候，队列当中没有元素，是一个空队列

我们约定，头指针始终指向队列头元素

也就是记录队头元素所在存储单元的下标

尾指针记录队尾元素所在单元的下一个位置的下标

假设现在队列中0，1，2.三个单元中有a，b，c三个元素

那么，这个时候

队头指针指示队头元素的位置Q.front=0

队尾指针指示队尾元素的下一个位置

Q.rear =3，这是队尾元素c的下一个位置

如果有一个元素入队列

那么这个元素应该存储到3号位置

也就Q.rear所指的位置

涉及到的两个主要语句是

Q.base[Q.rear]被赋值入队列元素e

Q.rear= Q.rear+1，让队尾指针指向下一个位置

这是因为入队列以后，队尾元素发生了变化

变为新入队的元素

那么应该按照约定

通过加1，让Q.rear指向当前队尾元素的下一个位置

下面看一下出队列

图①是上图ab两个元素出队列以后的情形

按约定队头指针Q.front指向队头元素的位置

出队列操作的时候，首先e=Q.base[Q.front];

让引用e被赋值出队列元素

利用e带回出队列元素

队头元素出队列以后

Q.front= Q.front+1，让Q.front增加一个位置

指向后一个位置，也就是指向新的队头元素

如果队列中最后一个元素c也出队列

如图②所示

那么，出队列后队列变空

队头指针Q.front和队尾指针Q.rear都为3

有Q.front==Q.rear

结合初始化时候的情形

我们看到

可以把Q.front==Q.rear作为队空的判断条件

图③是在图2的基础上

有d，e，f三个元素入站以后的情形

这个时候我们注意到

入队列完成后，Q.rear =6

实际上已经超出了分配给队列的存储空间范围

如果有元素要入队列，就不行了

但是从图中可以看到

Q.front=3

分配的空间中还有三个单元并没有被使用

从这儿我们注意到

顺序实现队列中的存在的一个问题

存储空间未能得到充分的利用

那么怎么充分地利用存储空间呢

一个办法是可以通过移动队列中的元素

把它们从后部移动到前部

这样后部空间就空出来了

比如把，D,E,F移动到0,1,2单元

自然，头尾指针要重新更新

用这样的方式，可以利用剩余的空间

但是这需要移动元素，效率上并不是很理想

我们的做法呢

是把顺序队列臆造为一个环状空间

如图所示，

就是说5号单元存储元素后

它的下个位置不是6，而是0号单元

Q.rear中记录0

那么，如果有新的元素要入队列

就可以放在0号单元

同时，让Q.rear指向下一个位置1

为了完成这样的臆造

我们在出入队列时

指针加1的语句要做一些变化

Q.rear =Q.rear+1

要变为Q.rear =(Q.rear+1)

对MAXQSIZE;求余

Q.front=Q.front+1要变为

Q.front= (Q.front+1)对MAXQSIZE求余

这样，就可以保证Q.front和Q.rear

始终在这样的环状空间当中变化

这样的处理以后

又引起了一个新的问题

就是队空和队满无法区分

从图上看一下

图①是队列中有三个元素的情况

如果现在有三个元素

G,H, K入队列,那么就应该变化为图②的情况

根据约定，Q.rear指向队尾元素k的下一个单元

所以Q.rear =3

这个时候

Q.front=Q.rear=3

如果在图①的基础上，把D, E, F三个元素出队列

那么，队列变化的情况如图③所示

这个时候，Q.front=0

注意到

Q.front=Q.rear=0

从图②③中我们看到

两种情形下，都有Q.front=Q.rear

那么二者相等的时候到底是队满还是队空

我们无法区分，为了解决这个问题

需要做了一点小小的设计

解决的办法是少用一个元素的存储空间

从图2可以看出，这个时候我们就说是队满了

虽然还有一个存储空间没有使用

这样，我们可以用

(Q.rear+1)%MAXQSIZE求余等于Q.front

作为队满的判定条件

仍然用Q.front==Q.rear作为队空的判定条件

这样呢，就解决了队空队满无法判断的问题

循环队列基本操作的实现比较简单

我们就不再课堂上讨论了

请同学结合教材学习

同学们，这节课就到这儿

我们下次课再见