数据结构教程第十三课队列

教学目的:掌握队列类型的定义和链队列的表示与实现
教学重点:链队列的表示与实现
教学难点:链队列的表示与实现
教学内容:
一、队列的定义:
队列是一个先入先出的线性表。它只允许在表的一端插入元素，在另一端删除元素。就像日常生活中的排队，第一个加入队列，第一个离开。
在队列中，允许插入的末端称为队列的末端，允许删除的末端称为队列的头部。
抽象数据类型队列:
ADT队列{
数据对象:d = {ai | ai (-elemset，I = 1，2，...，N，n > = 0}
数据关系:R1 = {| ai N}
基本操作:
InitQueue(&Q)构造一个空队列Q
Destroyqueue(&Q)如果队列Q存在，清除队列(&Q)如果队列Q存在，清除Q到/[/k0如果Q是空队列，则返回TRUE否则返回FALSE
queuelength(Q)exists，返回Q的元素个数，即队列长度
GetHead(Q，&e) Q不是空队列，Q的头元素由e [/]返回插入队列，尾元素
出列(&Q，&e) Q不是空，删除Q的头元素，用e返回其值
链式队列——队列的链式表示和实现
链表表示的队列简称为链式队列。链式队列显然需要两个指针来分别指示队列的头和尾。队列表示和实现:
//存储表示
typedef struct qnode {
qelemtypedata；
struct QNode * next；
}QNode，* QueuePtr
typedef结构{
queue ptr front；
queue ptr rear；
} link queue；
//操作说明
状态初始化队列(链接队列& Q)
/构造一个空队列Q
状态销毁队列(链接队列& Q)
/如果队列Q存在，则销毁[/]状态清除队列(链接队列& Q)
/队列Q被清除为空队列
状态队列空(链接队列Q)
/队列Q存在，如果Q为否则，返回false
Status Queue length(Link Queue Q)
/Queue Q exists，并返回Q的元素个数，即队列的长度
Status GetHead (Link Queue Q，QLEMType & E)
/Q不是一个空队列，使用queue head元素
Status enqueue(Link Queue & Q，qelemtype)
/该元素返回Q和E，并插入队列尾元素[ LEMType & E)
//q是非[/k0/]队列，删除Q的队列头元素，用E返回值
状态队列遍历(link queue q，qelemtype visit ())
/q存在且不/[空。 一旦visit()失败，操作失败
/操作的实现
status init queue(link queue & q){
//构造一个空queue q
q . front = q . real =(queue ptr
if(！Q.front)退出(溢出)；
q . front-> next = NULL；
return OK；}
状态销毁队列(链接队列& Q){
/如果队列Q存在，销毁Q
while(Q . front){
Q . rear = Q . front-> next；
免费(q . front)；
q . front = q . rear；
} return OK；}
status enqueue(link Queue & Q，qelemtype){
/Queue Q存在，插入元素e的队列元素结尾
p =(Queue ptr)malloc(sizeof(qnode))为Q；
如果(！p)退出(溢出)；
p-> data = e；p-> next = NULL；
q . rear-> next = p；
q . rear = p；
return OK；}
状态出列(link queue & q，qelemtype & e) {
/q是非[/k0/]队列，删除q的队列头元素，用e返回其值
if (q.front = = q.real)返回错误；
p = q . front-> next；
e = p-> data；
q . front-> next = p-> next；
if(q . rear = = p)q . rear = q . front；
免费(p)；
return OK；}
三。总结
链队列的存储来表示
链队列的操作和实现。