队列的定义表示实现

队列的定义表示实现第1页，共30页，2023年，2月20日，星期四3.2队列只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。1.定义一、概念：例如：队列Q=(a1,a2,a3,…，an)在队尾插入元素称为入队；在队首删除元素称为出队。队头元素队尾元素允许插入的一端为队尾，允许删除的一端为队头。2第2页，共30页，2023年，2月20日，星期四与线性表相同，仍为一对一关系。顺序队或链队，以循环顺序队更常见。只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。3.存储结构：4.运算规则：5.实现方式：2.逻辑结构：3第3页，共30页，2023年，2月20日，星期四二、队列的抽象数据类型定义ADTQueue{

数据对象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

数据关系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

约定a1

端为队列头，an端为队列尾。基本操作：

}ADTStack4第4页，共30页，2023年，2月20日，星期四（1）初始化队列InitQueue(&Q)（2）入队EnQueue(&Q,e)（3）出队DeQueue(&Q,&e)（4）获取队头元素内容GetHead(Q,&e)（5）判断队列是否为空QueueEmpty(Q)基本操作:建队列、判断队列是否为空、入队、出队、读队头元素值，等等。5第5页，共30页，2023年，2月20日，星期四链队列类型定义：

typedefstruct{QueuePtrfront;//队头指针

QueuePtrrear;//队尾指针

}LinkQueue;结点类型定义：

typedefstructQNode

{QElemType

data;//元素

structQNode

*next;

//指向下一结点的指针}

Qnode,*QueuePtr;关于整个链队的总体描述链队中任一结点的结构三、队列的表示和实现1.单链队列//-----队列的链式存储结构-----6第6页，共30页，2023年，2月20日，星期四a1∧an…Q.frontQ.rearQ.frontQ.rear∧空队列为了操作方便，添加一个头结点，令头指针指向头结点。Q.front==Q.rear7第7页，共30页，2023年，2月20日，星期四

StatusInitQueue(LinkQueue&Q){//构造一个空队列

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

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

Q.front->next=NULL;

returnOK;}//-----基本操作的算法描述-----建队操作——构造空队列Q8第8页，共30页，2023年，2月20日，星期四Q(队尾)(队首)fronta1a2a3^rearp链队会满吗？一般不会，因为删除时有free动作。除非内存不足！入队（尾部插入）：rear->next=S;rear=S;出队（头部删除）：p=front->next;

front->next=p->next;free(p);Se^链队列的入队和出队操作9第9页，共30页，2023年，2月20日，星期四

StatusEnQueue(LinkQueue&Q,QElemTypee){

//插入元素e为Q的新的队尾元素

p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);//存储分配失败

p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}10第10页，共30页，2023年，2月20日，星期四

StatusDeQueue(LinkQueue&Q,QElemType&e){

//若队列不空，则删除Q的队头元素，

//用e返回其值，并返回OK；否则返回ERRORif(Q.front==Q.rear)returnERROR;

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

if(Q.rear==p)Q.rear=Q.front;

//一定要考虑

free(p);returnOK;}11第11页，共30页，2023年，2月20日，星期四队列的顺序存储结构如下图所示：附设两个指针front和rear分别指示队列头元素的位置和队列尾元素的下一个位置约定：初始化建空队列时，令front=rear=0；2.顺序队列12第12页，共30页，2023年，2月20日，星期四（2）空队列的特征？约定：front=rear问题：（1）怎样实现入队和出队操作？核心语句如下：入队(尾部插入)：Q[rear]=e;rear++;

出队(头部删除)：e=Q[front];front++;

（3）队列会满吗？极易装满！因为数组通常有长度限制，而其前端空间无法释放。有假溢出现象。如图：13第13页，共30页，2023年，2月20日，星期四解决假溢出的途径———采用循环队列在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但实际上数组中还有空位置，这就叫“假溢出”。讨论：什么叫“假溢出”？如何解决？将存储队列元素的一维数组首尾相接，形成一个环状。14第14页，共30页，2023年，2月20日，星期四a3a2a10123N-1rearfront循环队列（臆造）顺序队列a3a2a1frontrear

0123..N-115第15页，共30页，2023年，2月20日，星期四新问题：在循环队列中，队空时front=rear；队满时也会有front=rear；判决条件将出现二义性！解决方案有二：①使用一个计数器记录队列中元素个数（即队列长度）；②人为浪费一个单元，约定：队列头指针在队列尾指针的下一位置上作为队列呈“满”状态的标志。则队满特征可改为front=(rear+1)%N（N为最大队列长度）；

实际中常选用方案2（人为浪费一个单元）16第16页，共30页，2023年，2月20日，星期四建队核心语句：Q.base=(QElemType*)malloc(sizeof(QElemType）*MAXQSIZE);

//分配空间关于整个顺序队的总体描述#defineMAXQSIZE100//最大队列长度

typedefstruct{QElemType*base;//队列的基址

intfront;//队头指针

intrear;//队尾指针

}SqQueue//-----循环队列——队列的顺序存储结构-----17第17页，共30页，2023年，2月20日，星期四队空条件:front=rear(初始化时：front=rear)队满条件：front=(rear+1)%N(N=MAXQSIZE)队列长度：L=（N＋rear－front）%N

J2J3 J1J4

J5frontrear问3：在具有N个单元的循环队列中，队满时共有多少个元素？N-1个6问1：左图中队列MAXQSIZEN=？问2：左图中队列长度L=？518第18页，共30页，2023年，2月20日，星期四例1.一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置?J2J3 J1J4

J5front=1rear=0解：由图可知，队头和队尾指针的初态分别为front=1和rear=0。删除4个元素后front=5；再插入4个元素后，rear=(0+4)%6=4

front=5J6J5J7J8J9rear=4rear=0front=519第19页，共30页，2023年，2月20日，星期四例2.Q[0…10]是一个循环队列，初始状态为front=rear=0,画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。d,e,b,g,h入队d,e出队i,j,k,l,m入队b出队n,o,p入队20第20页，共30页，2023年，2月20日，星期四讨论：循环队列的基本操作如何实现？以建队、入队和出队三种基本操作为例1）初始化一个空队列算法要求：生成一空队列算法操作：为队列分配基本容量空间设置队列为空队列，其特征即：

front=rear=0（也可为任意单元，如1，2，…）21第21页，共30页，2023年，2月20日，星期四建队的完整算法：StatusInitQueue(SqQueue&Q){

//初始化空循环队列Q

Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType）);//分配空间

if(!Q.base)

exit(OVERFLOW);

Q.front=Q.rear=0;

//置空队列

returnOK;}//InitQueue;22第22页，共30页，2023年，2月20日，星期四算法说明：向循环队列的队尾插入一个元素分析：(1)插入前应当先判断队列是否满？

if((Q.rear+1)%MAXQSIZE)==Q.front)returnERROR;(2）插入动作

Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;2）入队操作队列尺寸先存放元素，后移动队尾指针23第23页，共30页，2023年，2月20日，星期四StatusEnQueue(SqQueue&Q,QElemTypee){//向循环队列q的队尾加入一个元素e

if((Q.rear+1)%MAXQSIZE==Q.

front)returnERROR;

//队满则上溢

Q.

base[Q.

rear]=e;//新元素e入队

Q.rear=(Q.rear+1)%MAXQSIZE;//指针后移returnOK;}//EnQueue;入队操作完整算法24第24页，共30页，2023年，2月20日，星期四3）出队操作算法说明：删除队头元素，返回其值e分析：（1）在删除前应当判断队列是否空？

if(Q.front==Q.rear)returnERROR;

（2）删除动作分析：

前面约定指针front指向队首元素的位置，故：

e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;队列尺寸先取出元素，后移动队头指针25第25页，共30页，2023年，2月20日，星期四StatusDeQueue(SqQueue&Q,QElemType&e){//若队列不空，删除循环队列q的队头元素，//由e返回其值，并返回OKif(Q.

front==Q.

rear)returnERROR;//队列空e=Q.

base[Q.front];

Q.

front=(Q.front+1)%MAXQSIZE;returnOK;}//DeQueue出队操作完整算法26第26页，共30页，2023年，2月20日，星期四例3：编写一个算法，利用栈和队列的基本运算将指定队列中的内容进行逆转。分析：假设为循环队列。建立一个临时栈temps，将指定队列Q中的所有元素出队并入栈到temp