(16)--第三章第五节链队列的基本操作.pdf

01【链队列的存储结构】

目录02【构造一个空队列】

CONTENTS03【入队列】

04【出队列】

01链队列的存储结构

链队列的存储结构

用链表表示的队列简称为链队列。

一个链队列显然需要分别指示队头和队尾的两个指针。

Q.rear

Q.front

…/\

为了操作方便，添加一个头结点，并令头指针指向头结点，

因此链队列为空的条件是：头指针和尾指针均指向头结点

空队列Q.front/\

Q.rear

队列的链式存储结构

//结点类型

typedefstructQNode

{QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;

//链队列类型

typedefstruct{

QueuePtrfront;//队头指针

QueuePtrrear;//队尾指针

}LinkQueue;

02构造一个空队列

构造一个空队列

1.问题分析

•操作名称：InitQueue(Q)Q.front/\

•操作结果：构造一个空队列QQ.rear

算法思想：

1)申请头结点的存储空间，让队头和队尾指针都指向头结点

2)头结点的指针域设为NULL

构造一个空队列

2.算法描述

//构造一个空队列Q

StatusInitQueue(LinkQueueQ)

{//申请头结点的内存空间

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

if(!Q.front)exit(OVERFLOW);//存储分配失败

Q.front-next=NULL;

returnOK;

}

03入队列

入队列p

Q.front

a1a2…an/\e/\

1.问题分析

•操作名称：EnQueue(Q,e)Q.rear

•初始条件：队列Q已存在

•操作结果：插入元素e为Q的新的队尾元素

算法思想：

1)申请新元素的结点空间，若申请不成功则退出，

若申请成功，则结点的数据域为e,指针域为空；

2)将新生成的结点链接到队尾之后，作为新的队尾

3)队尾指针移向新