数据结构-基于C语言的描述第2版课件 第3章 栈和队列

DATASTRUCTUREDATASTRUCTUREDataStructureBYPENGBO

栈和队列是两种特殊的线性结构。从逻辑结构看，栈和队列是线性表；从操作角度看，栈和队列基本操作是线性表操作子集，是操作受限制的线性表，比一般线性表更简单。第3章主要内容栈和队列第章3《数据结构–基于C语言的描述》（第2版）-清华大学出版社DATASTRUCTUREDATASTRUCTUREDataStructureBYPENGBO第3章主要内容3.1

栈3.2

队列栈和队列第章3《数据结构–基于C语言的描述》（第2版）-清华大学出版社3.1栈

栈的特点在于必须按“后进先出”规则进行操作。与线性表相比，其插入和删除操作受到更多的约束和限定。

3.1栈3.1.1栈的类型定义●栈的定义栈示意图a1a2an出栈入栈栈顶栈底

栈是限定仅在表尾进行插入或删除的线性表。允许进行插入或删除的一端称为栈顶，它将随栈中元素增减而浮动；另一端称为栈底，其指针是固定的，不随栈中元素增减而移动。当栈中没有元素时称为空栈。

例如：铁路调度站A是一个栈。

铁路调度示意图

调度站A轨道C轨道B

栈的操作规则是“后进先出”。栈又称后进先出线性表，简称LIFO表3.1栈3.1.1栈的类型定义●栈的抽象数据类型定义ADTStack{Data：

D={ai|ai

ElemSet,i=1,2,…,n,n≥0}（具有相同类型的数据元素集合）

Relation：

R={<ai-1,ai>|ai-1,ai

D,i=2,…,n}（约定an端为栈顶，a1端为栈底）

Operation：

……Push(&S,e)

初始条件：栈S已经存在。操作结果：插入元素e为S的新栈顶元素。

Pop(&S,&e)

初始条件：栈S已经存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。

……}ADTStack3.1栈3.1.2栈的存储表示及操作实现

把自栈底到栈顶的元素按照逻辑次序依次存放在一组地址连续的存储单元里的方式称为栈的顺序存储结构，简称顺序栈，同时附设指针top指示栈顶元素在数组中的位置。

toptop=-1栈空43210a1top43210a1

入栈a5a4a3a2a1toptop=4栈满43210a3a2a1topa4、a5

出栈43210●顺序栈的定义顺序栈中栈顶指针和栈中元素之间的关系3.1栈3.1.2栈的存储表示及操作实现●顺序栈的类型定义#defineSTACK_INIT_SIZE100 //栈存储空间的初始分配量#defineSTACK_INCREMENT10 //栈存储空间的分配增补量typedefstruct{ElemType *elem; //栈存储空间基地址int top; //栈顶指针，栈非空时指向栈顶元素int stacksize; //当前分配存储容量（以ElemType为单位）}SqStack;3.1栈3.1.2栈的存储表示及操作实现

初始化操作●顺序栈的操作实现voidInitStack_Sq(SqStack&S){//构造一个空顺序栈SS.elem=newElemType[STACK_INIT_SIZE];if(!S.elem)Error("Overflow!"); //存储分配失败S.top=-1;S.stacksize=STACK_INIT_SIZE;}//InitStack_Sq算法3-1时间复杂度O(1)。

销毁操作3.1栈3.1.2栈的存储表示及操作实现●顺序栈的操作实现voidDestroyStack_Sq(SqStackS){//释放顺序栈S所占用的存储空间delete[]S.elem;S.top=-1;S.stacksize=0;}//DestroyStack_Sq算法3-2时间复杂度O(1)。

清空操作3.1栈3.1.2栈的存储表示及操作实现●顺序栈的操作实现voidClearStack_Sq(SqStack&S){//重置顺序栈S为空栈S.top=-1;}//ClearStack_Sq算法3-3时间复杂度O(1)。

求栈长操作3.1栈3.1.2栈的存储表示及操作实现●顺序栈的操作实现intStackLength_Sq(SqStackS){//返回顺序栈S的长度return(S.top+1);}//StackLength_Sq算法3-4时间复杂度O(1)。

取栈顶元素值操作3.1栈3.1.2栈的存储表示及操作实现●顺序栈的操作实现voidGetTop_Sq(SqStackS,ElemType&e){//若顺序栈S为空，则给出相应信息并退出运行；否则用e返回栈顶元素值if(S.top==-1)Error("StackEmpty!");e=S.elem[S.top];}//GetTop_SqS.top==-1表明栈已空，此时若再作取栈顶元素值操作，则将因栈中无元素可“取”而发生溢出，称为“下溢”。栈的下溢常用来作为程序的控制条件。算法3-5时间复杂度O(1)。

入栈操作3.1栈3.1.2栈的存储表示及操作实现●顺序栈的操作实现算法3-6voidPush_Sq(SqStack&S,ElemTypee){//插入元素e，作为新的栈顶元素if(S.top==(S.stacksize-1)) //若当前存储空间已满，则增加空间

Increment(S);S.elem[++S.top]=e; //栈顶指针先加1，再将e压入栈顶}//Push_SqvoidIncrement(SqStack&S){//为顺序栈S扩充STACK_INCREMENT个元素的空间newstack=newElemType[S.stacksize+STACK_INCREMENT];//增加存储分配if(!newstack)Error("Overflow!"); //存储分配失败for(i=0;i<=S.top;i++)newstack[i]=S.elem[i]; //腾挪原空间中的数据到newstack中delete[]S.elem; //释放元素所占用的原空间S.elemS.elem=newstack; //移交空间首地址S.stacksize+=STACK_INCREMENT; //扩充后的顺序栈的最大空间}//Increment没有上溢，时间复杂度O(1)。发生上溢，时间复杂度O(n)。

出栈操作3.1栈3.1.2栈的存储表示及操作实现●顺序栈的操作实现算法3-7voidPop_Sq(SqStack&S,ElemType&e){//若顺序栈S为空，给出相应信息并退出运行；否则用e返回栈顶元素值并修改栈顶指针if(S.top==-1)Error("StackEmpty!"); //栈空，给出相应信息并退出运行e=S.elem[S.top--];}//Pop_Sq时间复杂度O(1)。链栈没有栈满问题3.1栈3.1.2栈的存储表示及操作实现●链栈的定义

栈的链式存储结构称为链栈。通常用单链表表示，并以单链表的头部做为栈顶，进行入栈和出栈操作。非空链栈Sa1a2an∧datanext栈顶栈底空链栈S∧

例如：一个非负十进制整数1348转换成八进制，其运算过程如下：NN/8NMOD8134816841682102125202即(1348)10=(2504)8。3.1栈3.1.2栈的存储表示及操作实现例3-1

数制转换问题。设计

十进制数N和其他D进制数转换的简单算法基于原理：N=(N/D)×D+NMODD其中：MOD为求余运算（取模）。

又如：一个非负十进制整数13转换成二进制，其运算过程如下：NN/2NMOD21361630311101即(13)10=(1101)2。3.1栈3.1.2栈的存储表示及操作实现例3-1

数制转换问题。设计

十进制数N和其他D进制数转换的简单算法基于原理：N=(N/D)×D+NMODD其中：MOD为求余运算（取模）。

基于上述原理，

●计算过程是从低位到高位的顺序产生D进制数的各个数位；

●输出过程是从高位到低位进行，恰好和计算过程相反。

如果将计算中得到的D进制数各位顺序进栈保存，则按出栈序列输出的即为与输入对应的D进制数。这是利用栈的“后进先出”操作特性的最简单例子。

3.1栈3.1.2栈的存储表示及操作实现例3-1

数制转换问题。算法3-8voidConversion(){//对于输入的任意非负十进制整数，打印输出与其等值的其他进制数InitStack_Sq(S); //构造空顺序栈Scin>>N>>D;

//输入任意非负十进制数N和基数Dwhile(N){ //从低到高位产生D进制数各个数位

Push_Sq(S,N%D); //N取模D后入栈SN=N/D; //N整除D}while(!(S.top==-1)){ //从高到低位输出D进制数各个数位

Pop_Sq(S,e); //将转换后的D进制数出栈Scout<<e; //输出}}//Conversion3.1栈3.1.2栈的存储表示及操作实现例3-1

数制转换问题。分析①问题规模：待转换的非负“十进制数”N和“基”D；②基本操作：入栈、出栈操作；③时间分析：执行时间主要花费在两个while循环基本操作上，执行次数均为logDN，因此算法的时间复杂度为O(logDN)。3.1栈3.1.2栈的存储表示及操作实现例3-2

括号匹配检验。对输入表达式中任意括号串进行配对检测。

（1）基本原理：在表达式中，可包含有括号“(”和“)”，且可嵌套使用，但需要检测表达式中的括号输入是否匹配：若是“(())”序列或“(()())”序列，则为配对正确；若是“(()”序列或“())(”序列，则为配对不正确。检测表达式中的括号输入是否匹配的方法可采用“期待的急迫程度”这个概念来描述。

例如：(… (… (… (… )… )… )… )1 2 3 4 5 6 7 8当计算机接受了第1个左括号后，期待与其匹配的第8个右括号出现，可等来的是第2个左括号；

此时第1个左括号暂时放到一边，而迫切期待与第2个左括号匹配的第7个右括号出现……；第4个左括号在接受了第5个右括号之后，期待得到满足；

消解之后，第3个左括号的匹配就成为当前最急迫的任务了……；

依次类推。处理过程与栈操作相同。设计3.1栈3.1.2栈的存储表示及操作实现例3-2

括号匹配检验。对输入表达式中任意括号串进行配对检测。

（1）基本原理：在表达式中，可包含有括号“(”和“)”，且可嵌套使用，但需要检测表达式中的括号输入是否匹配：若是“(())”序列或“(()())”序列，则为配对正确；若是“(()”序列或“())(”序列，则为配对不正确。设计由此，可以自左至右扫描表达式（以回车键结束），并基于顺序栈设计一个算法来判断输入的一串括号是否配对正确。

（2）实现方法：先将读到的左括号“(”压入栈中，当读到右括号“)”时就和栈中左括号配对消解，即将栈顶的左括号弹出栈。

若栈顶弹不出左括号，则表示输入括号匹配出错；

若括号串已读完，栈中仍有左括号存在，则表示输入括号匹配出错。3.1栈3.1.2栈的存储表示及操作实现例3-2

括号匹配检验。对输入表达式中任意括号串进行配对检测。算法3-9intmatching(){//检验表达式中所含括号是否正确嵌套；若是则返回1，否则返回0InitStack_Sq(S); //构造空顺序栈SPush_Sq(S,‘#‘); //将"#"入栈表示括号串开始ch=getchar(); //读取表达式中的一个字符state=1; //state=1，正确；state=0，出错

while((ch!='\n')&&state){ //表达式未结束且检验未出错继续检验if(ch=='(')Push_Sq(S,ch); //若遇左括号则左括号入栈if(ch==')'){GetTop_Sq(S,e); //取栈顶元素if(e=='#')state=0; //若栈顶元素="#"，则无左括号配对elsePop_Sq(S,e); //若有左括号配对则消解}ch=getchar();}3.1栈3.1.2栈的存储表示及操作实现例3-2

括号匹配检验。对输入表达式中任意括号串进行配对检测。算法3-9GetTop_Sq(S,e);if(e!='#')state=0; //若栈顶元素≠"#"则左括号数多于右括号if(state)return1; //表达式中所含括号是正确嵌套，返回1elsereturn0; //表达式中所含括号非正确嵌套，返回0}//matching3.1栈3.1.2栈的存储表示及操作实现例3-2

括号匹配检验。对输入表达式中任意括号串进行配对检测。分析①问题规模：表达式串“长度”（设值为n）；②基本操作：字符比较；③时间分析：执行时间主要花费在while循环的基本操作上，执行次数为n，所以算法的时间复杂度为O(n)。3.1栈●递归算法的设计3.1.3栈与递归问题●

递归基本步骤

将规模较大的原问题分解为一个或多个规模更小、但具有类似于原问题特性的子问题，求解原问题的方法可用来解这些子问题。

●

递归终止条件

确定一个或多个无须分解、可直接求解的最小子问题。

例如，非负整数n的阶乘可递归定义为：

3.1栈3.1.3栈与递归问题●栈在递归算法内部实现中所起的作用●

调用函数前

系统需要先完成三件事情：

将所有实参、返回地址等信息传递给被调用函数保存；

为被调用函数的局部变量分配存储区；

将控制权转移到被调用函数的入口。●

调用函数后

系统也应该完成三件事情：

保存被调用函数的计算结果；

释放被调用函数的数据区；

依照被调用函数保存的返回地址将控制权转移到调用函数。

嵌套调用

当嵌套调用时，按“后调用先返回”的原则，函数之间信息传递和控制权转移通过“栈”来实现。3.1栈3.1.3栈与递归问题●栈在递归算法内部实现中所起的作用●

递归层次●

递归工作栈

运行过程

假设调用该递归函数的主函数为第0层，则从主函数调用递归函数就为第1层；从第i层递归调用本函数为进入“下一层”，即第i+1层。

为保证递归函数正确执行，系统设立一个“递归工作栈”作为整个递归期间的数据存储区。每一层递归所需信息构成一个“工作记录”。每进入一层递归，产生一个新工作记录压入栈顶；每退出一层递归，从栈顶弹出一个工作记录，则当前执行层工作记录必是递归工作栈顶工作记录。3.1栈3.1.4栈与递归问题●栈在递归算法内部实现中所起的作用

运行过程1intfact(intn){2if(n==0)return1;3else{4temp=fact(n-1);5returnn*temp;6}7}求fact(4)参数返址top40top35top25top15top05返回1返回1*1=1返回2*1=2返回3*2=6返回4*6=24toptoptoptoptop例如，非负整数n的阶乘可递归定义为：3.1栈●Hanoi问题3.1.3栈与递归问题

传说世界刚被创建时有一座钻石宝塔A，上有64个金碟。所有碟子按大到小次序从塔底堆放至塔顶。该塔边有另外两个钻石宝塔B和C。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上碟子移到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。

移动规则：

●

每次只能移动一个金碟；

●

金碟可以插在A、B和C中任一塔座上；

●

任何时刻都不能将一个较大金碟压在较小金碟之上。ABC3.1栈3.1.3栈与递归问题

●基本项：当n=1时，将编号为1的金碟从塔A移至塔C；

●

归纳项：当n>1时：设计●Hanoi问题（1）将塔A上的n-1个金碟借助塔C先移到塔B上；（2）把塔A上剩下的一个金碟移到塔C上；（3）将n-1个金碟从塔B借助塔A移到塔C上。CBA3.1栈3.1.3栈与递归问题

●基本项：当n=1时，将编号为1的金碟从塔A移至塔C；

●

归纳项：当n>1时：设计●Hanoi问题（1）将塔A上的n-1个金碟借助塔C先移到塔B上；（2）把塔A上剩下的一个金碟移到塔C上；（3）将n-1个金碟从塔B借助塔A移到塔C上。

将一个金碟从一个塔移至另一个塔的问题是一个和原问题具有相同特征属性的问题，只是问题的规模小1。3.1栈3.1.3栈与递归问题1voidhanoi(intn,charA,charB,charC){

//将A上按直径由大到小且自上而下编号为1到n的n个金碟按规则搬到C上，B作辅助2if(n==1)move(A,1,C); //将编号为1的金碟从A移到C3else{4hanoi(n-1,A,C,B); //将A上编号为n-1的金碟移到B，C作辅助5move(A,n,C); //将编号为n的金碟从A移到C6hanoi(n-1,B,A,C); //将B上编号为n-1的金碟移到C，A作辅助7}8}//hanoi求hanoi(3,A,B,C)算法3-10ABC参数返址13,A,B,C02,A,C,B51,A,B,C51,C,A,B72,B,A,C71,B,C,A51,A,B,C723工作栈●Hanoi问题3.1栈3.1.3栈与递归问题1voidhanoi(intn,charA,charB,charC){

//将A上按直径由大到小且自上而下编号为1到n的n个金碟按规则搬到C上，B作辅助2if(n==1)move(A,1,C); //将编号为1的金碟从A移到C3else{4hanoi(n-1,A,C,B); //将A上编号为n-1的金碟移到B，C作辅助5move(A,n,C); //将编号为n的金碟从A移到C6hanoi(n-1,B,A,C); //将B上编号为n-1的金碟移到C，A作辅助7}8}//hanoi算法3-10●Hanoi问题递归函数结构清晰，程序易读，不需要用户而由系统来管理递归工作栈。给用户编程和调试带来很大方便。3.2队列

队列的特点在于必须按“先进先出”规则进行操作。和线性表相比，它的插入和删除操作受到更多的约束和限定。

3.2队列3.2.1队列的类型定义●队列的定义

队列是限定只允许在表的一端进行插入，而在表另一端进行删除的线性表。允许插入的一端称队尾，随队列中元素的增加而浮动；允许删除的一端称队头，随队列中元素的减少而浮动。队列示意图a1a2a3an-2an-1an…出队列入队列队头队尾队列中没有元素时称为空队列。队列的操作规则是“先进先出”。队列又称先进先出线性表，简称FIFO表3.2队列3.2.1队列的类型定义●队列的抽象数据类型定义ADTQueue{Data：

D={ai|ai

ElemSet,i=1,2,…,n,n≥0}（具有相同类型的数据元素集合）

Relation：

R={<ai-1,ai>|ai-1,ai

D,i=2,…,n}（约定a1端为队列头，an端为队列尾）

Operation：

…… EnQueue(&Q,e)

初始条件：队列Q已经存在。 操作结果：插入元素e为Q的新队尾元素。

DeQueue(&Q,&e)

初始条件：队列Q已经存在且非空。 操作结果：删除Q的队头元素，并用e返回其值。

……}ADTQueue3.2队列3.2.2队列的存储表示及操作实现●循环队列的定义

在队列的顺序存储结构中，用一组地址连续的存储单元依次存放队头到队尾的元素，并附设两个指针front和rear分别指示队头和队尾元素位置。

循环队列及操作实现顺序存储队列中头、尾指针和队列中元素之间的关系

当入队时，尾指针增1；当出队时，头指针增1。由此约定，在非空队列中，头指针front指向队头元素，尾指针rear指向队尾元素下一个位置。

由于队列头和尾是动态的，因此需设置队头和队尾两个指针，且约定：初始化空队列时，令front=rear=0。

如果把队头元素放在数组中下标为0的一端，则出队操作的时间复杂度为O(n)。

如果只要求队列元素存储在数组中连续位置上，不要求把队头元素放在数组中下标为0的一端，则出队操作的时间复杂度为O(1)，因此采用该方法。3.2队列3.2.2队列的存储表示及操作实现●循环队列的定义front空队列43210a4a3a2a143210a1a2a3a4依次入队a1a2依次出队(移动元素)a4a343210a4a343210a1a2依次出队(不移元素)rearfrontrearfrontrearfrontrear

循环队列及操作实现

解决“假溢出”的巧妙方法是将存储队列的数组看成是头尾相接的循环结构。3.2队列3.2.2队列的存储表示及操作实现●循环队列的定义

循环队列及操作实现

当元素被插到下标最大位置上后，队列空间被耗尽，但此时低端还有空间，称“假溢出”。

a5a4a343210frontrear问题“假溢出”现象a63.2队列3.2.2队列的存储表示及操作实现●循环队列的定义

循环队列及操作实现

当元素被插到下标最大位置上后，队列空间被耗尽，但此时低端还有空间，称“假溢出”。

a5a4a343210frontrear问题“假溢出”现象解决a5a4a343210frontrear逻辑上实现循环

将队列头尾相连，即允许队列直接从下标最大位置延续到下标最小位置，逻辑上实现循环。如何实现逻辑上实现循环a6rear3.2队列3.2.2队列的存储表示及操作实现●循环队列的定义

循环队列及操作实现a5a4a343210frontrear问题“假溢出”现象解决a5a4a3a643210frontrear逻辑上实现循环

利用数学上的取模操作可以实现这种逻辑上的循环结构。队列的这种头尾相接的顺序存储结构称为循环队列。3.2队列3.2.2队列的存储表示及操作实现●循环队列的定义

设存储循环队列的数组长度为Queue_Size，则

例如：存储循环队列的数组长度为5，状态如右图：

●

循环队列长度：QueueLength=(4-2+5)%5=2

●

循环队列长度：QueueLength=(1-3+5)%5=3a443210a3frontrear

●

a5入队尾指针：rear=(4+1)%5=0a5rear

●

a6入队尾指针：rear=(0+1)%5=1a6rear

●

a3出队头指针：front=(2+1)%5=3fronta6a5●

循环队列长度：QueueLength=(rear-front+Queue_Size)%Queue_Size

●

队尾指针修改：rear=(rear+1)%Queue_Size

●

队头指针修改：front=(front+1)%Queue_Size

循环队列及操作实现循环队列满和空条件同为front==rear

应该如何区分队列空和队列满的判定条件3.2队列3.2.2队列的存储表示及操作实现●循环队列的定义

循环队列及操作实现43210a5a5a4a3frontreara6rearrear队列满时front==rear43210frontrearfronta4frontfront队列空时front==reara3a7队列满队列空a543210reara4fronta3

常用的方法是：牺牲一个数组元素的空间，并约定以“队头指针在队尾指针环状的下一个位置上”作为队列呈“满”状态的标志3.2队列3.2.2队列的存储表示及操作实现●循环队列的定义

循环队列及操作实现43210a5a4a3fronta6rear队列满时front==rear队列空时front==reara7队列满队列空

循环队列队列满的条件：(rear+1)%Queue_Size==front

循环队列队列空的条件：front==rearrear3.2队列3.2.2队列的存储表示及操作实现●循环队列的类型定义#defineQUEUE_MAX_SIZE100; //循环队列大小，可根据实际需要而定typedefstruct{ElemType *elem; //存储空间基地址int front; //头指针，队列非空指向队头元素int rear; //尾指针，队列非空指向队尾元素下一位置}SqQueue;

循环队列及操作实现3.2队列3.2.2队列的存储表示及操作实现

初始化操作●循环队列的操作实现voidInitQueue_Sq(SqQueue&Q){//构造一个空循环队列QQ.elem=newElemType[QUEUE_MAX_SIZE];if(!Q.elem)Error("Overflow!"); //存储分配失败Q.front=Q.rear=0;}//InitQueue_Sq算法3-11

循环队列及操作实现时间复杂度O(1)。

销毁操作3.2队列3.2.2队列的存储表示及操作实现●循环队列的操作实现voidDestroyQueue_Sq(SqQueue&Q){//释放循环队列Q所占用的存储空间delete[]Q.elem;Q.front=Q.rear=0;}//DestroyQueue_Sq算法3-12

循环队列及操作实现时间复杂度O(1)。

清空操作3.2队列3.2.2队列的存储表示及操作实现●循环队列的操作实现voidClearQueue_Sq(SqStack&Q){//重置循环队列Q为空队列Q.front=Q.rear=0;}//ClearQueue_Sq算法3-13

循环队列及操作实现时间复杂度O(1)。

求队列长操作3.2队列3.2.2队列的存储表示及操作实现●循环队列的操作实现intQueueLength_Sq(SqQueueQ){//返回循环队列Q的元素个数length=(Q.rear-Q.front+QUEUE_MAX_SIZE)%QUEUE_MAX_SIZE;returnlength;}//QueueLength_Sq算法3-14

循环队列及操作实现时间复杂度O(1)。

取队头元素值操作3.2队列3.2.2队列的存储表示及操作实现●循环队列的操作实现voidGetHead_Sq(SqQueueQ,ElemType&e){//若循环队列Q为空，则给出相应信息并退出运行；否则用返回队头元素值if(Q.front==Q.rear)Error("QueueEmpty!");e=Q.elem[Q.front];}//GetHead_Sq算法3-15Q.front==Q.rear表明队列已空，如果再作取队头元素值操作，则将因队列中无元素可“取”而发生溢出，称为“下溢”。

循环队列及操作实现时间复杂度O(1)。3.2队列3.2.2队列的存储表示及操作实现

入队操作●循环队列的操作实现

循环队列及操作实现voidEnQueue_Sq(SqQueue&Q,ElemTypee){//若循环队列Q已满，则给出相应信息退出运行；否则将元素e插入队尾，并修改队尾指针if(((Q.rear+1)%QUEUE_MAX_SIZE)==Q.front)Error(“QueueOverflow!”); Q.elem[Q.rear]=e;Q.rear=(Q.rear+1)%Queue_Size;}//EnQueue_Sq算法3-16时间复杂度O(1)。

出队操作3.2队列3.2.2队列的存储表示及操作实现●循环队列的操作实现

循环队列及操作实现voidDeQueue_Sq(SqQueue&Q,ElemType&e){//若循环队列Q为空，则给出相应信息并退出运行；否则用e返回队头元素，并修改队头指针if(Q.front==Q.rear)Error("QueueEmpty!");e=Q.elem[Q.front];Q.front=(Q.front+1)%QUEUE_MAX_SIZE;}//DeQueue_Sq算法3-17时间复杂度O(1)。3.2队列3.2.2队列的存储表示及操作实现

链队列及操作实现●链队列的定义用链表表示的队列称为链队列。通常用单链表表示，并设置队头指针指向其头结点，队尾指针指向其最后一个结点。

空链队列非空链队列Q.fronta1a2an∧datanextQ.rear∧Q.rearQ.front链式队列没有队列满问题

链队列的入队操作在队尾进行，出队操作在队头进行。3.2队列3.2.2队列的存储表示及操作实现

链队列及操作实现●链队列的类型定义typedefstructQNode{ //结点ElemType data; //数据域

structQNode *next; //指针域}QNode，*QueuePtr;typedefstruct{QueuePtr front; //头指针，指向链队列头结点

QueuePtr rear; //尾指针，指向链队列最后一个结点}LinkQueue;3.2队列3.2.2队列的存储表示及操作实现

链队列及操作实现

初始化操作●链队列的操作实现voidInitQueue_L(LinkQueue&Q){//构造一个空链队列QQ.front=Q.rear=newQNode;Q.front->next=NULL; }//InitQueue_L算法3-18时间复杂度O(1)。3.2队列

销毁操作3.2.2队列的存储表示及操作实现

链队列及操作实现●链队列的操作实现voidDestroyQueue_L(LinkQueue&Q){//释放链队列Q所占用的存储空间while(Q.front){Q.rear=Q.front->next;deleteQ.front;Q.front=Q.rear;}}//DestroyQueue_L算法3-193.2队列3.2.2队列的存储表示及操作实现

链队列及操作实现

销毁操作●链队列的操作实现分析

①问题规模：队列“当前长度”，即链队列结点个数（设值为n）；②基本操作：指针后移、释放结点存储空间；③时间分析：执行时间主要花费在while循环的基本操作上，执行次数为n+1，因此算法的时间复杂度为O(n)。3.2队列

清空操作3.2.2队列的存储表示及操作实现

链队列及操作实现●链队列的操作实现voidClearQueue_L(LinkQueue&Q){//清空链队列L，释放所有结点空间p=Q.front->next;while(p){q=p;p=p->next;deleteq;}Q.front->next=NULL;Q.rear=Q.front;}//ClearQueue_L算法3-203.2队列

清空操作3.2.2队列的存储表示及操作实现

链队列及操作实现●链队列的操作实现分析

①问题规模：队列“当前长度”，即链队列结点个数（设值为n）；②基本操作：指针后移、释放结点存储空间；③时间分析：执行时间主要花费在while循环的基本操作上，执行次数为n，因此算法的时间复杂度为O(n)。3.2队列

求队列长操作3.2.2队列的存储表示及操作实现

链队列及操作实现●链队列的操作实现intQueueLength_L(LinkQueueQ){//返回链队列Q的长度p=Q.front; //设置指针，初始指向链队列头结点length=0; //设置计数器length初始为0while(p->next){length++;p=p->next;}returnlength;}//QueueLength_L算法3-213.2队列

求队列长操作3.2.2队列的存储表示及操作实现

链队列及操作实现●链队列的操作实现分析

①问题规模：队列“当前长度”，即链队列结点个数（设值为n）；②基本操作：计数器加1、指针后移；③时间分析：执行时间主要花费在while循环的基本操作上，执行次数为n，因此算法的时间复杂度为O(n)。3.2队列

取队列头元素值操作3.2.2队列的存储表示及操作实现

链队列及操作实现●链队列的操作实现voidGetHead_L(LinkQueueQ,ElemType&e){//若链队列Q为空，则给出相应信息并退出运行；否则用e返回队头结点数据域的值if(Q.front->next==NULL)Error("QueueEmpty!");e=Q.front->next->data;}//GetHead_L算法3-22时间复杂度O(1)。（1）生成一个数据域值为e的新结点；（2）将新结点插入链式队列的队尾；（3）修改队列尾指针。链式队列入队操作完成Q.rear->next=p;Q.rear=p;3.2队列3.2.2队列的存储表示及操作实现

链队列及操作实现

入队操作●链队列的操作实现设计an∧Q.rearQ.fronta2a1Q.rearp∧e3.2队列

入队操作3.2.2队列的存储表示及操作实现

链队列及操作实现●链队列的操作实现voidEnQueue_L(LinkQueue&Q;ElemTypee){//插入一个数据域值为e的结点到链队列Q中，成为新的队尾结点p=newQNode;p->data=e;p->next=NULL; //生成一个数据域值为e的新结点Q.rear->next=p; //将新结点插到队尾Q.rear=p; //修改队尾指针，令其指向新结点}//EnQueue_L算法3-23时间复杂度O(1)。

（1）判断链式队列是否为空，若空则返回错误信息并退出运行；

（2）如果非空则删除链式队列队头结点，返回该结点数据域值并释放结点空间。

特殊情况–链式队列长度等于1。

解决方法–令尾指针指向头结点。3.2队列

出队操作3.2.2队列的存储表示及操作实现

链队列及操作实现●链队列的操作实现设计Q.fronta2an∧Q.reara1pQ.front∧a1p∧Q.rearQ.rearQ.front->next=p->next;e=p->data;3.2队列

出队操作3.2.2队列的存储表示及操作实现

链队列及操作实现●链队列的操作实现voidDeQueue_L(LinkQueue&Q,ElemType&e){//若链队列Q为空，则给出相应信息并退出运行；否则用e返回队头结点数据域的值if(Q.front==Q.rear)Error("QueueEmpty!");p=Q.front->next; //用指针p指向链队列Q的队头结点e=p->data;Q.front->next=p->next; //修改队头指针if(Q.rear==p)Q.rear=Q.front; //若队列长度等于1，则修改尾指针deletep; //释放队头结点所占的存储空间}//DeQueue_L算法3-24时间复杂度O(1)。3.2队列3.2.2队列的存储表示及操作实现

链队列及操作实现例3-3

模拟病人在医院等候就诊的过程。设计

患者到医院看病顺序：先排队等候，再看病治疗。在排队过程中重复做两件事情：一是当患者达到诊室时将病历交给护士，到等候队列中候诊；二是护士从等候队列中取出下一个患者病历，让该患者进入诊室就诊。

（1）病人等候就诊按照“先到先服务”原则：当“病人达到”时，入队；当“护士让下一位患者就诊”时，出队；当有“不再接收病人排队”时，队列中所有元素出队。因此，本算法采用链队列存储结构。

（2）“病人到达”用命令“A”或“a”表示，“护士让下一位患者就诊”用命令“N”或“n”表示，“不再接收病人排队”用“S”或“s”表示。3.2队列3.2.2队列的存储表示及操作实现

链队列及操作实现例3-3

模拟病人在医院等候就诊的过程。算法3-25voidSeeDoctor(){//模拟病人在医院等候就诊的过程InitQueue_L(Q); //初始化链队列Qflag=1; //flag=1：接收病人；=0：停止就诊

while(flag){cout<<"请输入命令：";cin>>ch;switch(ch){case'a':case'A':cout<<"病历号：";cin>n;cout<<endl;EnQueue_L(Q,n); //入队等候就诊break;3.2队列3.2.2队列的存储表示及操作实现

链队列及操作实现例3-3

模拟病人在医院等候就诊的过程。算法3-25case'n':case'N':if(Q.front->next){DeQueue_L(Q,n); //病人出队就诊

cout<<"病历号为"<<n<<"的病人就诊"<<endl;}elsecout<<"无病人等候就诊。"<<endl;break;3.2队列3.2.2队列的存储表示及操作实现

链队列及操作实现例3-3

模拟病人在医院等候就诊的过程。算法3-25case's':case'S':cout<<"下列排队的病人依次就诊："

while(Q.front->next){ //所有病人依次出队就诊

DeQueue_L(Q,n);cout<<n<<"";}cout<<endl<<"今天不再接收病人排队！"<<endl;flag=0;break;default:cout<<"输入命令不合法！"<<endl；

}}}//SeeDoctor3.2队列3.2.2队列的存储表示及操作实现

链队列及操作实现例3-3

模拟病人在医院等候就诊的过程。分析①问题规模：等候就诊的“病人”（设值为n）；②基本操作：入队操作、出队操作；③时间分析：算法的时间复杂度为O(n)。3.2队列3.2.2队列的存储表示及操作实现

链队列及操作实现例3-4

周末舞会上的配对舞伴。设计

假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。如果两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。先入队的男士或女士也先出队配成舞伴，因此该问题具有典型的先进先出特性，可以采用循环