数据结构队列演示文稿

数据结构队列演示文稿目前一页\总数四十八页\编于十四点数据结构队列目前二页\总数四十八页\编于十四点3.4.1队列的概念一、什么是队列队列是限定仅能在表头进行删除、表尾进行插入的线性表。（a1,a2,...,ai-1,ai,ai+1,…,an）插入删除目前三页\总数四十八页\编于十四点4）元素按a1,a2,a3,...,an

顺序入队，第一个入队的元素为a1，最后一个入队的元素是an，第一个出队的元素为a1；

说明：1）表尾称作队尾，表头称为队头；2）a1为队头元素，an为队尾元素；3）在表尾插入元素操作，称为入队操作；在表头删除元素的操作，称为出队操作；5）队列具有先进先出的特点，又称为先进先出表（FIFO表）。入队列

a1a2a3an队头队尾出队列目前四页\总数四十八页\编于十四点自测题1一个队列的入列序列是1,2,3,4，则队列的输出序列是（）。A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,1目前五页\总数四十八页\编于十四点二、队列的抽象数据类型的定义InitQueue(&Q)结果:构造一个空队列Q。数据对象:D={ai|ai∈ElemSet，i=1,2,…,n}数据关系:R1={<ai-1,ai>}；约定a1为队头元素，an为队尾元素。基本操作:ADTQueue{}ADTQueueDestroyQueue(&Q)结果:销毁队列Q。条件:队列Q已存在。目前六页\总数四十八页\编于十四点

功能：若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则，返回ERROR。队列的基本操作：1）初始化操作InitQueue(&Q)功能：构造一个空队列Q；2）销毁操作DestroyQueue(&Q)功能：销毁已存在队列Q；3）置空操作ClearQueue(&Q)功能：将队列Q置为空队列；4）判空操作QueueEmpty(Q)功能：若队列Q为空，则返回True；否则，返回False；5）取队头元素操作GetHead(Q,&e)功能：取队头元素，并用e返回；6）入队操作EnQueue(&Q,e)功能：将元素e插入Q的队尾；7）出队操作DeQueue(&Q,&e)目前七页\总数四十八页\编于十四点在队列的顺序存储结构中，用一组连续存储单元依次存储从队头到队尾的数据元素.此外，还需附加两个变量：3.4.3队列的顺序存储和实现一、队列的顺序存储结构队头指针front：指示队头元素的位置；队尾指针rear：指示队尾元素的位置。空队列Q.rearQ.front012345Q.rearQ.frontJ1J2J3J1,J2和J3相继入队Q.rearQ.frontJ3J1和J2相继出队J4、J5和J6相继入队之后,J3和J4出队Q.rearQ.frontJ5J6问题：如何解决“假上溢”现象?目前八页\总数四十八页\编于十四点将顺序队列设想为首尾相连的环状空间。当Q.rear值超出队列空间的最大位置时，令Q.rear=0，使队列空间能“循环”使用。J6J4J5Q.rearQ.front312405543210Q.rearQ.frontJ6J5J41、循环队列循环使用空间的队列。目前九页\总数四十八页\编于十四点循环队列操作示意图目前十页\总数四十八页\编于十四点2）在（a)状态下，J6、J7、J8依次入队，队列如图（c），这时也有Q.front=Q.rear。540312J5Q.frontQ.rearJ4J3(a)Q.rear540312Q.frontJ5J6J7J8J3J4(c)队满2、队空、队满的判别1）在（a）状态下，J3、J4、J5依次出队，队列状态如图（b），这时有Q.front=Q.rear;仅凭Q.front=Q.rear是否成立，无法判断队列是空还是满。Q.frontQ.rear540312J3J4J5(b)队空目前十一页\总数四十八页\编于十四点2）少用一个存储单元，即当队列达到图(d)所示状态时，就认为队列已满，这时的条件是Q.front=(Q.rear+1)%6。如何判断循环队列队空、队满？

？Q.rear540312Q.frontJ5J6J7J3J4（d）两种方法：1）另设一个标志位以区分队空、队满。目前十二页\总数四十八页\编于十四点自测题2循环队列的优点是什么，如何判断“空”和“满”。【解答】循环队列解决了常规用0--m-1的数组表示队列时出现的“假溢出”（即队列未满但不能入队）。在循环队列中，我们仍用队头指针等于队尾指针表示队空，而用牺牲一个单元的办法表示队满：即当队尾指针加1（取模）等于队头指针时，表示队列满。也有使用全部单元，通过设标记来解决“空”和“满”的。目前十三页\总数四十八页\编于十四点3、循环队列的类型定义#defineMAXQSIZE100//最大队列长度

typedefstruct{

QElemType*base;//初始化时动态分配存储空间的基址

intfront;//队头指针，指向队头元素（队列不空）

intrear;//队尾指针，指向队尾元素的下一个位置（队列不空）}SqQueue;只是称为指针，实现时不一定用指针变量目前十四页\总数四十八页\编于十四点设Q为SqQueue类型的变量，用于存储队列。设为队列Q分配空间大小为MAXQSIZE=6。初始建队时，令Q.front=Q.rear=0。Q.frontQ.rear540312Q.base目前十五页\总数四十八页\编于十四点二、循环队列的基本操作算法1、初始化操作InitQueue_Sq(SqQueue&Q)参数：Q是存放队列的结构变量；功能：建一个空队列Q。Q.frontQ.rear540312Q.base#defineMAXQSIZE100//最大队列长度

typedefstruct{

QElemType*base;//基址

intfront;//指向队头元素

intrear;//指向队尾元素的下一个位置}SqQueue;目前十六页\总数四十八页\编于十四点StatusInitQueue_Sq(SqQueue&Q){

//构造一个空队列Q

Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));

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

Q.front=Q.rear=0;

returnOK;

}Q.frontQ.rear540312Q.base#defineMAXQSIZE100//最大队列长度

typedefstruct{

QElemType*base;//基址

intfront;//指向队头元素

intrear;//指向队尾元素的下一个位置}SqQueue;目前十七页\总数四十八页\编于十四点intQueueLength_Sq(SqQueueQ){

return（Q.rear–Q.front+MAXQSIZE）%MAXQSIZE;

}2、计算队列长度操作QueueLength_Sq(SqQueueQ)参数：Q是存放队列的结构变量；功能：计算队列的长度。Q.rear540312Q.frontJ5J6J7J3J4Q.rear目前十八页\总数四十八页\编于十四点3）修改队尾指针，使队尾指针指向队尾元素的下一个位置。Q.frontQ.rear540312J1J3J2元素e入队前Q.frontQ.rear540312J1J3J2e元素e入队后3、入队操作EnQueue_Sq(SqQueue&Q,QElemTypee)功能：将元素e插入队尾。主要步骤：1）Q是否已满，若满，返回ERROR；否则转2）；2）将元素e写入队尾；目前十九页\总数四十八页\编于十四点StatusEnQueue_Sq(SqQueue&Q,QElemTypee){

}if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;//队列满Q.base[Q.rear]=e;//将元素e插入队尾Q.rear=(Q.rear+1)%MAXQSIZE;//修改队尾指针returnOK;目前二十页\总数四十八页\编于十四点自测题3循环队列存储在数组A[0..m]中，则入队时的操作为（）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)目前二十一页\总数四十八页\编于十四点3）修改队头指针，删除队头元素。Q.frontQ.rear540312J1J3J2出队操作前Q.frontQ.rear540312J1J3J2出队操作后eJ14、出队操作DeQueue_Sq(SqQueue&Q,QElemType&e)功能：删除队头元素，用e返回其值。主要步骤：1）Q是否为空，若空，返回ERROR；否则，转2）；2）将队头元素赋值给e；目前二十二页\总数四十八页\编于十四点StatusDeQueue_Sq(SqQueue&Q,QElemType&e){

}if(Q.rear==Q.front)returnERROR;//队列空e=Q.base[Q.front];//将队头元素赋给eQ.front=(Q.front+1)%MAXQSIZE;//修改队头指针returnOK;目前二十三页\总数四十八页\编于十四点一、什么是链队列用链表存储的队列。为便于操作，一个链队列需要分别指示队头和队尾的两个指针。

J1∧Q.frontQ.rearJ2∧空链队列Q.frontQ.rear∧头结点3.4.2链队列——队列的链式存储结构和实现链队列的表头结点Q.front==Q.rear目前二十四页\总数四十八页\编于十四点二、链队列的类型定义typedefstructQNode{//链队列结点的类型定义

QElemTypedata;

structQNode*next;}QNode,*QueuePtr;typedefstruct{

//链队列表头结点的类型定义

QueuePtrfront;//队头指针，指向链表的头结点

QueuePtr

rear;//队尾指针，指向队尾结点}LinkQueue;//将头尾指针封装在一起的链队J1∧Q.frontQ.rearJ2∧目前二十五页\总数四十八页\编于十四点三、链队列基本操作算法1、初始化操作InitQueue_L(LinkQueue&Q):创建空的链队列。

Q.frontQ.reartypedefstructQNode{//链队列结点的类型定义

QElemTypedata;

structQNode*next;}QNode,*QueuePtr;typedefstruct{//链队列表头结点的类型定义

QueuePtrfront;//队头指针，指向链表的头结点

QueuePtr

rear;//队尾指针，指向队尾结点}LinkQueue;∧目前二十六页\总数四十八页\编于十四点if(!Q.front)exit(OVERFLOW)；Q.front

->next=NULL；returnOK；StatusInitQueue_L(LinkQueue&Q){}Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))；//申请头结点Q.frontQ.reartypedefstructQNode{//链队列结点的类型定义

QElemTypedata;

structQNode*next;}QNode,*QueuePtr;typedefstruct{//链队列表头结点的类型定义

QueuePtrfront;//队头指针，指向链表的头结点

QueuePtr

rear;//队尾指针，指向队尾结点}LinkQueue;∧目前二十七页\总数四十八页\编于十四点Q.frontQ.rear

销毁后J1∧Q.frontQ.rearJ2∧

销毁前2、销毁操作DestroyQueue_L(LinkQueue&Q)：回收空间。

typedefstructQNode{//链队列结点的类型定义

QElemTypedata;

structQNode*next;}QNode,*QueuePtr;typedefstruct{//链队列表头结点的类型定义

QueuePtrfront;//队头指针，指向链表的头结点

QueuePtr

rear;//队尾指针，指向队尾结点}LinkQueue;∧∧目前二十八页\总数四十八页\编于十四点StatusDestroyQueue_L(LinkQueue&Q){

}while(Q.front){

}//while

Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;returnOK;Q.frontQ.rear

销毁后J1∧Q.frontQ.rearJ2∧

销毁前∧∧目前二十九页\总数四十八页\编于十四点3、入队操作EnQueue_L(LinkQueue&Q,QElemTypee)Q.front∧J1∧Q.reare∧J1typedefstructQNode{//链队列结点的类型定义

QElemTypedata;

structQNode*next;}QNode,*QueuePtr;typedefstruct{//链队列表头结点的类型定义

QueuePtrfront;//队头指针，指向链表的头结点

QueuePtr

rear;//队尾指针，指向队尾结点}LinkQueue;目前三十页\总数四十八页\编于十四点p=(QueuePtr)malloc(sizeof(QNode))；if(!p)exit(OVERFLOW)；p->data=e；p->next=NULL；//申请新结点Q.rear->next=p；returnOK；StatusEnQueue_L(LinkQueue&Q，QElemTypee){}Q.rear

=p；//插入在队尾Q.front∧J1∧Q.reare∧J1目前三十一页\总数四十八页\编于十四点zhoujin0xin

SQ.frontQ.rear

pe=p->data=zhou

pe=p->data=jin

pe=p->data=xinQ.rear04、离开队列DeQueue_L(LinkQueue&Q，QElemType&e)

注意！目前三十二页\总数四十八页\编于十四点p=Q.front->next；e=p->data；//取第一个结点free(p)；returnOK；StatusDeQueue_L(LinkQueue&Q，QElemType&e){}Q.front->next=p->next；//删除第一个结点if(Q.front==Q.rear)returnERROR；if(Q.rear==p)Q.rear=Q.front；//若需要删除的队头结点就是尾结点J1∧Q.frontQ.rearJ2∧目前三十三页\总数四十八页\编于十四点自测题4用链接方式存储的队列，在进行删除运算时（）。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改目前三十四页\总数四十八页\编于十四点算法设计题1假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，不设头指针，试设计相应的入队列和出队列的算法。…Tail队头队尾目前三十五页\总数四十八页\编于十四点typedefstructLqueue{ElemTypedata;structLqueue*next;}Lqueue,*Queueptr;

voidQueueIn(Queueptrrear,ElemTypex){//入队列

s=(Queueptr)malloc(sizeof(LQueue));s->data=x;s->next=rear->next;//元素插入队尾

rear->next=s;rear=s;//求得新的队尾}

…Tail队头队尾目前三十六页\总数四十八页\编于十四点typedefstructLqueue{ElemTypedata;structLqueue*next;}Lqueue,*Queueptr;

…Tail队头队尾ElemTypeQueueOut(Queueptrrear){//出队列if(rear->next->next==rear)printf("队列为空");else{p=rear->next;q=p->next;p->next=q->next;x=q->data;if(q==rear)rear=p;free(q);//删除队头元素

return(x);}//else}

目前三十七页\总数四十八页\编于十四点算法设计题2要求完全利用循环队列中的元素空间，设置一个标志域tag，并以tag的值是0或１来区分尾指针和头指针相同时的队列状态是“空”还是“不空”。请编写与此结构相对应的入队和出队的算法。类型定义：typedefstruct{ElemTypedata[m];intrear,front;//队尾和队头指针

inttag;//标记,0为空,1为非空

}CycQueue;

目前三十八页\总数四十八页\编于十四点只设标志的循环队列的入队voidQueueIn(CycQueuecq,ElemTypex){if(cq.tag==1&&cq.front==cq.rear){printf(“队满\n”);exit(0);}else{cq.rear=(cq.rear+1)%m;cq.data[cq.rear]=x;if(cq.tag==0)cq.tag=1;//由空变不空标记

}//else}目前三十九页\总数四十八页\编于十四点只设标志的循环队列的出队voidQueueOut(CycQueuecq);{if(cq.tag==0){printf(“队空\n”);exit(0);}else{cq.front=(cq.front+1)%m;if(cq.front==cq.rear)cq.tag=0;//队列由不空变空

}//else}目前四十页\总数四十八页\编于十四点算法设计3用栈模拟队列请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x):元素x入ST栈；POP(ST,x)：ST栈顶元素出栈，赋给变量x；Sempty(ST)：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：

enqueue:插入一个元素入队列；dequeue:删除一个元素出队列；queue_empty：判队列为空。【上海交通大学1999二(12分)】【厦门大学2005六(15分)】目前四十一页\总数四十八页\编于十四点栈模拟队列——入队inttop1;∥top1是栈s1的栈顶指针，是全局变量intenqueue(stacks1,ElemTypex)∥用入栈模拟入队{if(top1==n&&!Sempty(s2)){printf(“栈满”);return(0);}∥s1满s2非空,这时s1不能再入栈

if(top1==n&&Sempty(s2))∥s2空，将s1退栈,再压栈到s2{while(!Sempty(s1)){POP(s1,x);PUSH(s2,x);}push(s1,x);return(1);∥x入栈，实现了队列元素的入队}目前四十二页\总数四十八页\编于十四点栈模拟队列——出队voiddequeue(stacks2,s1)∥s2是输出栈，将s2栈顶元素退栈，实现队列元素的出队{if(!Sempty(s2))∥栈s2不空，则直接出队

{POP(s2,x);printf(“出队元素为”,x);}elseif(Sempty(s1))∥处理s2空栈

{printf(“队列空”);exit(0);}∥若输入栈也空，则队空

else∥先将栈s1倒入s2中，再出队

{while(!Sempty(s1)){POP(s1,x);PUSH(s2,x);}POP(s2,x);∥s2退栈相当队列出队

printf(“出队元素”，x);}}∥结束算法dequue目前四十三页\总数