3.5 队列和链队列在线视频

同学们，大家好

这一节我们讨论队列

队列也是一种操作受限的线性表

也是插入和删除受限

队列中，限定在表的一端进行插入

这一端称为队尾

也就是线性序列an的这一端

在表的另一端进行删除

这一端称为队头，就是线性表a1这一端

这样的限制，使线性表具有先进先出的特征

就是说在队列当中

先插入的先删除

后面讨论中

我们把队列的插入称为入队列

队列中的删除称为出队列

下面我们看一下队列的实现

队列也是一种线性结构

那么线性表能采用的存储方式

队列也能使用

我们首先讨论一下链队列

队列的链式表示和实现

链队列中

同样是用单链表来实现队列的存储

如图所示，单链表中带有一个头结点

头结点的指针指向a1结点

以此类推，形成a1到an的单链表

链队列中，队头元素a1

队尾元素是an

因为，入队列的插入操作在队尾

出队列的删除操作在队头

为了方便队列的插入和删除

我们利用到了两个指针

其中队头指针Q.front

指向头结点

队尾指针Q.rear

指向队尾an结点

这样的设计对于队列的插入和删除操作带来了便利

我们看一下图①，图①的队列当中只有头结点

这个时候是一个空队列

队列初始化后也是这个样子

队头指针Q.front和队尾指针Q.rear都指向头结点

两个指针相等

这实际上给出了，空队列的判定条件

就是Q.front==Q.rear

图②一个元素x入队列后的情形

根据队列的约定，Q.rear 指针指向队尾元素

那么当一个元素入队列的时候

就应该把存储该元素的结点

插入到Q.rear所指结点之后

我们首先申请一个结点

让指针p指向它

假设入队列的元素是x

则把x存入该结点

入队列操作主要就是两个语句

Q. rear->next=p; 让队尾结点的指针指向新插入的结点

把新结点插入队尾结点之后

Q. rear=p; 让队尾指针指向新插入的结点

因为新结点插入以后

它变成了新的队尾结点

图③是又插入一个y结点以后的情形

图④给出了出队列的例子

从链队列的设计来看，如果是出队列的话

那么出队列的元素就是首元结点当中的数据元素

我们需要的操作就是把首元结点从队列当中删除

看一下具体的操作语句

p=Q.front->next;

让指针p，指向首元结点

也就是我们要删除的这个结点

Q.front->next=p->next;

这是让头结点的next指针指向首元结点的下一个结点

也就是队列当中新的首元结点

这里有一个问题，我们要注意一下

就是说当队列中只有一个结点的时候

队尾指针指向这个唯一的结点

如果这个时候有出队列的操作

那么出队列以后，队列就为空了

这种情况，为了避免队尾指针悬空导致错误的操作

我们需要重置队尾指针一下Q. rear

让队尾指针指向头结点

下面我们看一下链队列的定义和基本操作的实现

在链队列的存储定义当中

我们首先定义了链队列列中每个结点的存储结构

每个结点被定义成一个结构体

结构体中包含两个成员

一个是存储数据元素的data

一个是指向其后继的指针next

Typedef给这个结构体取了个类型名Qnode,

声明了指向结构体的一个指针类型名QueuePtr,

链队列本身也被定义为一个结构体

结构体中包含两个成员

Front和rear

如图中所示

这是两个指向队头和队尾的指针

这样的设计我们前面提到过

是为了方便队列的入队列和出队列的操作

Typedef给这个结构体取了一个类型名

linkqueue.下面看一下入队列的实现

入队列操作的函数是enqueue

它的返回值是函数执行的状态

涉及到两个参数

一个是入队列的对象队列Q

一个是入队列的元素e

首先malloc函数申请一个结点用p指向它

申请失败则退出

申请成功，做结点的初始化

随后两个语句，图中讨论过

就是把申请的结点插入到队列的尾部

随后返回OK，表示入队列成功

下面看一下出队列操作

出队列函数DeQueue的返回值也是函数执行的状态

涉及到的参数也是两个

一个是要出队列的对象队列Q

一个是引用e，用来带回出队列的元素

如果Q.front==Q.rear

意味着队列为空

不能出队列

返回error

随后3个语句是从链队列中删除一个结点的操作

前面图中讨论过

如果Q.rear==p，意味着

链队列当中只有一个元素

出队列以后，队列为空

我们需要对Q.rear进行调整

Q.rear=Q.front；让队尾指针指向头结点

如果链队列中有多个结点

则不需要调整

最后把删除结点用Free释放

返回OK表示出队列成功

同学们

这一节关于队列和链队列的讨论

我们就到这儿

下节课再见