堆栈与队列ppt课件.ppt-.docx

堆栈与队列ppt课件.ppt
1、第三章栈和队列四类基本结构：1.线性结构2.树形结构3.图状结构4.集合1〕线性表2〕栈和队列3〕串4〕数组与广义表栈与队列的规律特征：从数据结构角度讲，栈与队列也是线性表，不同之处在于其操作的特殊性〔栈为LIFO，队列为FIFO〕，为操作受限的线性表。从数据类型角度讲，栈与队列是与线性表不同的重要抽象数据类型，广泛的应用于各类软件系统中。3.1栈3.1.1栈的抽象类型定义3.1.2栈实现——挨次栈与链栈3.1.3栈的应用举例3.1.4栈与递归过程3.2队列3.2.1队列的类型定义3.2.2队列类型的实现3.2.3队列的应用举例3.1.1栈的抽象类型定义栈顶(
2、Top):允许进行插入、删除操作的一端栈底(Bottom):另一端，不允许插入、删除的一端空栈(StackEmpty):表中没有元素1.基本概念定义:作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行。an...a2a1栈顶Top栈底Bottom栈s=(a1,a2,……,an)进栈:栈的插入操作,或称为入栈出栈:栈的删除操作,或称为退栈特点：后进先出(LIFO)LastInFirstOut1.基本概念an...a2a1栈顶Top栈底Bottom进栈出栈栈s=(a1,a2,……,an)元素入栈的挨次与出栈的挨次相反栈的抽象数据类型定义ADTS
3、tack{数据对象：数据关系：基本操作：1.InitStack(S)2.StackEmpty(S)3.Push(S,x)4.Pop(S,x)5.GetTop(S,x)}ADTStackR={|ai-1,ai∈D,i=2,3,...,n}商定an端为栈顶，a1端为栈底。D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}…………了解各种操作的功能即可3.1.2栈的实现——挨次栈——链栈1.挨次栈#defineStack_Size初始支配量typedefstruct{StackElementTypee
4、lem[Stack_Size]；inttop；}SeqStack;(最简洁、最常用)为栈支配一个足够大的容量。挨次栈toptoptoptoptoptopDABCE①挨次栈的初始化②挨次栈的推断栈是否为空③挨次栈的推断栈是否为满④挨次栈的入栈⑤挨次栈的出栈⑥挨次栈的取栈顶元素2.挨次栈的基本操作：voidInitStack(SeqStack*S){S-top=-1;}3.挨次栈的基本操作——初始化函数空栈top#defineStack_Size50typedefstruct{StackElementTypeelem[Stack_Size];inttop；
5、}SeqStack;intIsEmpty(SeqStackS){if(S.top==-1)returnTRUE;elsereturnFALSE;}3.挨次栈的基本操作——推断栈是否为空栈空top#defineStack_Size50typedefstruct{StackElementTypeelem[Stack_Size];inttop；}SeqStack;intIsFull(SeqStackS){if(S.top==StackSize-1)returnTRUE;elsereturnFALSE;}3.挨次栈的基本操作——推断栈是否为满栈满topDABCE#de
6、fineStack_Size50typedefstruct{StackElementTypeelem[Stack_Size];inttop；}SeqStack;intPush(SeqStack*S,ElemTypex){if(S-top==Stack_Size-1)returnFALSE;S-top++;S-elem[S-top]=x;returnTRUE;}3.挨次栈的基本操作——入栈入栈toptoptoptoptoptopDABCE#defineStack_Size50typedefstruct{StackElementTy
7、peelem[Stack_Size];inttop；}SeqStack;intPop(SeqStack*S,ElemType*x){if(S-top==-1)returnFALSE;*x=S-elem[S-top];S-top--;returnTRUE;}3.挨次栈的基本操作——出栈问题：栈顶top要修改吗？要修改，栈发生转变！！出栈toptoptoptoptoptopDABCE#defineStack_Size50typedefstruct{StackElementTypeelem[Stack_Size];inttop；}Se
8、qStack;3.挨次栈的基本操作——取栈顶元素问题：栈顶top要修改吗？不要修改，栈没有转变！！取元素DABCEtopintPop(SeqStack*S,ElemType*x){if(S-top==-1)returnFALSE;*x=S-elem[S-top];S-top--;returnTRUE;}GetTop(SeqStack*S,ElemType*x)#defineStack_Size50typedefstruct{StackElementTypeelem[Stack_Size];inttop；}SeqStack;4.顺
9、序栈的基本操作特点下溢：栈空时再做退栈运算将产生溢出。1〕栈底位置固定在向量的低端，即S.elem[0]----表示栈底元素2〕入栈：S.top++，保存元素；3〕出栈：取元素，S.top--；4〕空栈：S.top=-1；5〕栈满：S.top=StackSize-1；上溢：栈满时再做进栈运算〔一种出错状态，应设法避开〕。例:现有一空栈，输入序列为12345，进行PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH操作后,输出序列为_____例:现有一n个单元的挨次栈，top作为栈顶指针,假定以地址高端作为栈底(即初始化时top=n)。则向栈中压入一
10、个元素时，top的转变是______top不变top=ntop=top-1top=top+1例:若一个栈的输入序列是1，2，…，n，输出序列的第一个元素是n，则第i个输出元素是_____n-in-i+1in-i-12,3例：设有一个输入序列123，请问经过栈后可以得到多少种输出序列？分析：元素可以入栈，然后又出栈，还可以入栈后停留，然后到达输出序列以1为开头以2为开头以3为开头123213321,132,231Cn2n1n+1=5,当n=3时14,当n=4时5.挨次栈的描述方式2#defineSTACK_SIZE初始支配量#defineSTACKINCREME
11、NT增加支配量typedefstruct{ElemType*elem；inttop；intstacksize;}SqStack;先为栈支配一个基本容量，在应用过程中，当栈的空间不过使用时再渐渐扩大。5.挨次栈的描述方式3#defineSTACK_SIZE初始支配量#defineSTACKINCREMENT增加支配量typedefstruct{ElemType*base；//栈低指针ElemType*top；//栈顶指针intstacksize;}SqStack;方法一：将栈的容量加到足够大，但这种方法由于事先难以估量容量，有可能铺张空间问题：当程序中同时使用几
12、个栈时，如何防止栈的上溢？6.挨次栈上溢的解决方法方法二：使用两个〔或多个〕栈共享存储空间方法。两栈的栈底分别设在给定存储空间的两端，然后各自向中间伸延，当两栈的栈顶相遇时才可能发生溢出。两栈共享技术——双端栈利用了栈“栈底位置不变，而栈顶位置动态转变”的特性。首先为两个栈申请一个共享的一维数组空间S[M]，将两个栈的栈底分别放在一维数组的两端,分别是0，M-1。0M-1top[0]top[1]7.双端栈#defineM初始支配量typedefstruct{ElemTypeStack[M];inttop[2];}DqStack;b1b2b3b4a3a2a10M
13、-1top[0]top[1]7.双端栈留意：1.操作需要说明是具体栈〔top[0]还是top[1]〕2.栈空推断：3.栈满推断：当两个栈迎面相遇时才会溢出,即top[0]+1=top[1]b1b2b3b4a3a2a10M-1top[0]top[1]栈s1栈s2栈s1:top[0]=-1;栈s2:top[1]=M;①双端栈的初始化②双端栈的入栈③双端栈的出栈7.双端栈的基本操作：voidInitStack(DqStack*S){S-top[0]=-1;S-top[1]=M;}7.双端栈的基本操作——初始化函数0M-1top[0]top[1]#de
14、fineM100typedefstruct{ElemTypeStack[M];inttop[2];}DqStack;7.双端栈的基本操作——入栈函数intPush(DqStack*S,ElemTypex,inti){returnFALSE;switch(i){case0:S-top[0]++;S-Stack[S-top[0]]=x;break;case1:S-top[1]--;S-Stack[S-top[1]]=x;break;default:returnFALSE;}returnTRUE;}推断栈是否满向栈0压
15、入元素向栈1压入元素参数错误#defineM100typedefstruct{ElemTypeStack[M];inttop[2];}DqStack;if(S-top[0]+1==S-top[1])7.双端栈的基本操作——出栈函数intPop(DqStack*S,ElemType*x,inti){{case0:if(S-top[0]==-1)return(FALSE);*x=S-Stack[S-top[0]];S-top[0]--;break;case1:if(S-top[1]==M)return(FAL
16、SE);*x=S-Stack[S-top[1]];S-top[1]++;break;default:return(FALSE);}return(TRUE);}switch(i)从栈0弹出元素从栈1弹出元素参数错误#defineM100typedefstruct{ElemTypeStack[M];inttop[2];}DqStack;要避开栈上溢出更好的方法是使用链式存储结构,让多个栈共享全部可用存储空间。多个栈共享空间…………栈1底栈1顶栈2底栈2顶…栈底栈顶nn留意:链栈中指针的方向入栈、出栈都在这里进行8.链栈的基本概念anan-1
17、^a1····栈顶指针top接受链表作为存储结构实现的栈。接受带头结点的单链表实现栈。由于栈的插入和删除操作仅限制在表头位置进行，所以链表的表头指针就作为栈顶指针。为便于操作,留意:链栈在使用完毕时，应当释放其空间8.链栈的特点anan-1^a1····栈顶指针top进栈和退栈〔插入和删除〕仅能在表头位置上〔栈顶〕进行。链栈中的结点是动态产生的，可不考虑上溢问题。空栈推断：top-next=NULL9.链栈的描述：typedefstructnode{ElemTypedata;structnode*next;}LinkStackNode,*LinkSta
18、ck;①链栈的初始化②链栈栈的入栈③链栈栈的出栈同单链表的初始化temptop^^×①temp-next=top-next;②top-next=temp;a1a2temp①②10.链栈的基本操作——入栈10.链栈的基本操作——入栈intPush(LinkStacktop,ElemTypex){LinkStackNode*temp;temp=(LinkStackNode*)malloc(sizeof(LinkStackNode));if(temp==NULL)return(FALSE);temp-data=x;temp-n
19、ext=top-next;top-next=temp;return(TRUE);}typedefstructnode{ElemTypedata;structnode*next;}LinkStackNode,*LinkStack;10.链栈的基本操作——出栈intPop(LinkStacktop,ElemType*x){LinkStackNode*temp;temp=top-next;if(temp==NULL)return(FALSE);top-next=temp-next;*x=temp-data;free(t
20、emp);return(TRUE);}typedefstructnode{ElemTypedata;structnode*next;}LinkStackNode,*LinkStack;11.链栈的基本操作特点栈底位置固定链表的末尾p-next=NULL----表示栈底元素入栈：用入栈元素建立新结点，并将其插入到链表的首元结点之前(头插法)出栈：取出链表首元结点的元素，并将其从链表中删除；空栈：top-next=NULL；12.多栈的描述：#defineM10typedefstructnode{ElemTypedata;structnode*ne
21、xt;}LinkStackNode,*LinkStack;LinkStacktop[M];top[0],top[1],……top[m-1],分别是m个链栈的栈顶指针,分别指向m个不同的链栈topM-1top4top3top2top1top012.多链栈：将多个链栈的栈顶指针存放在一个一维指针数组中统一管理M-143210C2^C1^D1^E3E2^E1G2^G1^F1top12.多栈的基本操作——初始化voidinit_linklist(LinkStacktop[M]){LinkStackNode*temp;inti;for(i=0;inext=NULL;to
22、p[i]=temp;}}temp=(LinkStack)malloc(sizeof(LinkStackNode));12.多栈的基本操作——入栈/*将元素x进入第i号链栈*/intpushi(LinkStacktop[M],inti,ElemTypex){LinkStackNode*temp;temp=(LinkStackNode*)malloc(sizeof(LinkStackNode));if(temp==NULL)return(FALSE);temp-data=x;temp-next=top[i]-next;top[i]-
23、next=temp;return(TRUE);}12.多栈的基本操作——出栈/*将第i号栈栈顶元素弹出，放到x中*/intPopi(LinkStacktop[M],inti,ElemType*x){LinkStackNode*temp;temp=top[i]-next;if(temp==NULL)return(FALSE);top[i]-next=temp-next;*x=temp-data;free(temp);return(TRUE);}3.1.3栈应用举例例1.数制转换例如:〔1348)10=(2504)8，计算挨次输出顺
24、序1682102125202NiNi+1＝Ni/8Nimod813481684进栈进栈推断条件voidconversion(intn){inte;SqStackS;/*使用挨次栈*/InitStack(S);while(n){Push(S,n%8);n=n/8;}while(!IsEmpty(S))/*输出计算结果*/{Pop(S,e);printf(%d,e);}}假设在表达式中〔［］〔〕〕或［〔［］［］〕］均为正确的格式，［〔］〕或〔［〔〕〕或〔〔〕］)均为不正确的格式。则检验括号是否匹配的方法可用“期盼的急迫程度”这个概念来描述。
25、例2.括号匹配的检验括号栈匹配{出栈匹配[出栈匹配[出栈匹配(出栈匹配[出栈[(])]}{[][([{[[算法的设计思想:凡消灭左括号，凡消灭右括号，若栈空，则说明该“右括号”多余否则和栈顶元素比较；若相匹配，则“左括号出栈”，否则说明左右括号不匹配表达式检验结束时，若栈空，则说明左右括号匹配，否则说明“左括号”有余。则进栈；首先检查栈是否空括号匹配算法intMatch(charch,charstr){if(ch==(str==))returnTRUE;elseif(ch==[str==])returnTRUE;elseif(ch=={str==})returnTRUE;elsereturnFALSE;}例3.表达式求值限于二元运算符的表达式定义:表达式：(操作数)+(运算符)+(操作数)操作数：简洁变量|表达式运算符：双目运算符〔算术运算符、关系运算符、规律运算符)问题分析：Exp=a´b+(c-d/e)´f确定计算规章，即明确运算符的优先级。确定当前处理字符是运算符还是操作数；每个运算符的运算次序要由它之后的一
27、个运算符来定。设立操作数栈与操作符栈；设表达式的结束符为“#”，预设运算符栈的栈底为“#”；若当前字符是操作数，则直接压入操作数栈。若当前字符是操作符，则与操作符栈的栈顶运算符进行优先级比较若优先级高于栈顶运算符则进栈；若优先级低于栈顶运算符则从操作数栈中弹出两个操作数a,b,从操作符栈中弹出一个运算符θ，经计算后将结果T压入操作数栈5.“(”对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开头的表达式的结束符。算法思路：Exp=F´E/D-C+B´A##操作数栈T(1)+CT(2)=A´BT(1)=D/ET(3)=T(3)´FT(4)=T(2)–T(4
28、)T(5)=ABT(1)CT(2)DET(3)FT(5)T(4)操作符栈#´/+´-①③②④⑤#Exp=F´E/D-C+B´A3.1.4栈与递归过程1.递归的基本概念在函数的执行过程中又直接或间接调用该函数本身直接递归调用在函数中直接调用函数本身间接递归调用在函数中调用其它函数,其它函数又调用原函数intf1(intx){inty,z;……z=f2(y);…….return(2*z);}intf2(intt){inta,c;……c=f1(a);…….return(3+c);}intf(intx){inty,z;……z=f(y);…….return(2*z);}
29、函数的递归调用C编译系统对递归函数的自调用次数没有限制f()调f调f2调f1f1()f2()2.递归应用示例：1)阶乘函数2)斐波纳契数列(Fibonacci函数)例用递归方法求n的阶乘递归算法的两要素：问题分解：将问题分解为相同性质且规模更小的问题。递归结束条件：必需给出递归的结束条件，否则递归会无限循环下去。例用递归方法求n的阶乘递推归纳：递归终止：n=0时，0！=1n!→(n-1)!→。省略部分。);elsereturnBSearch(a,x,low,mid-1);}设计递归算法的方法前提：原问题可以层层分解为类似的子问题，且子问题比原问题规模更小规模最
30、小的问题具有直接解方法：查找分解方法:将原问题转化为子问题求解例：n!=n*(n-1)!设计递归出口:依据规模最小的子问题确定递归终止条件，例:求解n!，当n＝0时，n!＝1；递归应用示例——汉诺(hanoi)问题例:汉诺塔问题。设有三座塔座〔A、B、C〕,在一个塔座〔设为A〕上有64个盘片，盘片不等，按大盘在下，小盘在上的挨次依次叠放。现要将A塔上的盘片借助于B塔，移到C塔上并保持同样挨次叠排，移动盘片时必需遵守以下规章：〔1〕每次只能移动一个圆盘；〔2〕圆盘可以插在A、B、C任意一个塔座上〔3〕任何时候都不能将一个较大的圆盘放到较小的圆盘之上。将A塔上的红
31、、黄两盘移动到B上蓝盘放到C上将红、黄两盘从B移动到C盘上。〔完成〕ABC问题分析：n=1时，直接将其从A－C；n1时，只要先将前n-1个借助C从A－B,那么可以把第n个直接从A－C;将剩下的n-1个圆盘遵守规章借助A从B－C，问题性质相同,因此适合接受递归过程！递归结束条件问题分解若将n个盘片按规定从A塔移至C塔：把A塔上的n-1个盘片借助C塔移至B塔把第n个盘片从A塔移至C塔把B塔上的n-1个盘片借助A塔移至C塔算法用函数hanoi(n,x,y,z)以递归算法实现盘片数源塔借用塔目标塔递归终止：当递归调用到盘片数为1
32、时算法描述：递归调用hanoi(n-1,x,z,y);将n号盘片从x塔移动到z塔；递归调用hanoi(n-1,y,x,z)。voidhanoi(intn,charx,chary,charz){move(x,1,z);else{hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);}}main(){intn;printf(“Inputthenumberofdisks:”);scanf(“%d”,printf(“Thestepstomoving%3ddisks:n”,n);hanoi(n,’A’,’B’,’C’);}prin
33、tf(“%c—%d—%cn”,x,n,z);printf(“%c—%d—%cn”,x,1,z);if(n==1)将全部的实在参数、返回地址等信息传递给被调用函数保存；为被调用函数的局部变量支配存储区；将把握转移到被调用函数的入口。当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：函数调用实现内幕保存被调函数的计算结果；释放被调函数的数据区；依据被调函数保存的返回地址将把握转移到调用函数。从被调用函数返回调用函数之前，应当完成以下三项任务：多个函数嵌套调用的规章是：此时的内存管理实行“栈式管理”后调用先返回！例
34、如：voidmain(){…a();…}//mainmain的数据区函数a的数据区函数b的数据区voida(){…b();…}//avoidb(){…}//b递归工作栈：递归过程执行过程中占用的数据区。递归工作记录：每一层的递归参数合成一个记录。当前活动记录：栈顶记录指示当前层的执行状况。当前环境指针：递归工作栈的栈顶指针。递归函数执行的过程可视为同一函数进行嵌套调用，例如：voidhanoi(intn,charx,chary,charz){if(n==1)move(x,1,z);else{hanoi(n-1,x,z,y);move(x,n,z);hanoi(
35、n-1,y,x,z);}}61abc03abc返址nxyz62acb81cab82bac123456789intcount=0;voidmove(charx,intn,charz){count++;printf(no.%dmovedisk%dfrom%cto%cn,count,n,x,z);}voidhanio(intn,charx,chary,charz){if(n==1)move(x,1,z);else{hanio(n-1,x,z,y);move(x,n,z);hanio(n-1,y,x,z);}}…...hanoi(n-1,x,
36、z,y);move(x,n,z);hanoi(n-1,y,x,z);…...3ABCn,x,y,z…...hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);…...2BACABC…...hanoi(n,A,B,C);…...1A-C2A-B1C-B3A-C1B-A2B-C1A-C…...hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);……2ACBmo
37、ve(x,n,z);move(x,n,z);…...move(x,1,z);1BCA…...move(x,1,z);1ABC…...move(x,1,z);1CAB…...move(x,1,z);1ABCmove(x,n,z);栈小结栈是一种操作受限制的特殊线性表，特殊性在于插入(入栈)和删除(出栈)操作只能在线性表的一端进行(栈顶)，线性表的另外一端固定不变(栈底)。操作的特殊性造就了元素入栈的挨次与出栈的挨次相反，即后进先出(LIFO)。同线性表一样，栈也有两种存储方式：挨次栈与链栈。挨次栈有发生上溢的可能，而链栈通常不会发生栈满〔除非整个空间均被占满〕只
38、要满足LIFO原则，均可接受栈结构。3.2.1队列的类型定义队尾(rear):允许进行插入操作的一端队头(front):允许进行删除操作的一端空队(QueueEmpty):表中没有元素1.基本概念定义:限定全部的插入操作在表的一端〔表尾〕进行，而删除操作在表的另一端进行〔表头〕的线性表。队尾rear队头front队列q=(a1,a2,……,an)an...a2a1入队:队列的表尾插入操作出队:队列的表头删除操作特点：先进先出(FIFO)FirstInFirstOut1.基本概念入队队列q=(a1,a2,……,an)队尾rear队头frontan...a2a1出
39、队元素入队列的挨次与出队列的挨次相同队列的抽象数据类型定义ADTQueue{数据对象：数据关系：基本操作：1.InitQueue(Q)2.QueueEmpty(Q)3.EnQueue(Q,x)4.DeQueue(Q,x)5.QueueLength(Q)}ADTQueueR={|ai-1,ai∈D,i=2,3,...,n}商定an端为队尾，a1端为队头。D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}…………了解各种操作的功能即可3.2.2队列的实现链队列循环队列——链式映象——挨次映象1.链队列接受链表
40、作为存储结构实现的队列。接受带头结点的单链表实现队列。由于队列的插入在队尾进行，而删除操作队头进行，链表分别设有队头指针和队尾指针。a1a2^an····rear^空链队frontrearfront非空链队2.链队列的描述：typedefstructNode{}QNode;typedefstruct{}LinkQueue;LinkQueueQ;^Q.rearQ.frontQNode*front;QNode*rear;ElemTypedata;structNode*next;rear^front空链队2.链队列的描述：Q.rearQ.fronta1^an····
41、frontrear非空链队a1^an····3.链队列的基本操作——初始化intInitQueue(LinkQueue*Q){Q-front=(QNode*)malloc(sizeof(QNode));if(Q-front==NULL)exit(OVERFLOW);Q-front-next=NULL;Q-rear=Q-front;returnOK;}^Q.rearQ.front3.链队列的基本操作入队申请结点空间将新结点插入到队尾，即插到Q.rear之后出队推断链队是否为空若不为空，删去队头元素并返回该元素,即删
42、除首元结点；若为空，返回失败3.链队列的基本操作——入队intEnQueue(LinkQueue*Q,ElemTypex){QNode*s;s=(QNode*)malloc(sizeof(QNode));if(s==NULL)returnFALSE;s-data=x;s-next=NULL;Q-rear-next=s;Q-rear=s;returnTRUE;}3.链队列的基本操作——出队intDeQueue(LinkQueue*Q,ElemType*x){QNode*p;if(Q-front==Q-rea
43、r)returnFALSE;p=Q-front-next;Q-front-next=p-next;*x=p-data;free(p);}Q.rearQ.fronta1^p^if(Q-rear==p)Q-rear=Q-front;若队中只有一个元素4.循环队列——挨次映射#defineMAXSIZE初始支配量typedefstruct{ElemTypeelem[MAXSIZE];intfront;intrear;}Seueue;(最简洁、最常用)//头指针，指向队头元素//尾指针，指向队
44、尾元素的下一个位置队列rearrearrearABCrearfront4.循环队列——挨次映射frontfrontfrontrear出队ABC#defineMAXSIZE初始支配量typedefstruct{ElemTypeelem[MAXSIZE];intfront;intrear;}Seueue;(最简洁、最常用)SeueueQ;入队操作为：Q.elem[Q.rear]=x;Q.rear=Q.rear+1;出队操作为：x=Q.elem[Q.front]；Q.front=Q.front+1；//头指针，指向队头元素//尾指针，指向队尾元素的下一个位置
45、frontrear入队rearrearrearABCrearfrontfrontfrontfrontfrontrear出队ABCrearrearfrontrear入队DEFrearrearrearG空队34012入队序列：出队序列：ABCABC4.循环队列——挨次映射SeueueQ;入队操作为：Q.elem[Q.rear]=x;Q.rear=Q.rear+1;出队操作为：x=Q.elem[Q.front]；Q.front=Q.front+1；下标计算修改;入队操作为：Q.elem[Q.rear]=x;Q.rear=(Q.rear+1)%MAXSIZE;出队
46、操作为：x=Q.elem[Q.front]；Q.front=(Q.front+1)%MAXSIZE；frontrear入队rearrearrearABCrearfrontfrontfrontfrontfrontrear出队ABCrearrearfrontrear入队DEFrearrearrearGHrear空队34012队空条件:队满:队满:rear-frontfront=0;Q-rear=0;}5.循环队列的基本操作——初始化rearfront0401234intIsEmpty(Sueue*Q){if(Q-front==Q-rea
47、r)returnTRUE;returnFALSE;}5.循环队列的基本操作——判空intIsFull(Sueue*Q){if((Q-rear+1)%MAXSIZE==Q-front)returnTRUE;returnFALSE;}5.循环队列的基本操作——判满rear5.循环队列的基本操作——入队列rearfrontrearrear0401234rearABCDintEnQueue(Sueue*Q,ElemTypex){if((Q-rear+1)%MAXSIZE==Q-front)returnFALSE;Q-el
48、em[Q-rear]=e;Q-rear=(Q-rear+1)%MAXSIZE;returnTRUE;}front5.循环队列的基本操作——出队列frontfront0401234ABCDfrontfrontrearintDeQueue(Sueue*Q,ElemType*e){if(Q-front==Q-rear)returnERROR;*e=Q-elem[Q-front];Q-front=(Q-front+1)%MAXSIZE;returnOK;}5.循环队列的基本操作——取队头元素f
49、ront0401234ABCrearintGetFront(Sueue*Q,ElemType*e){if(Q-front==Q-rear)returnERROR;*e=Q-elem[Q-front];returnOK;}5.循环队列的基本操作——求长度01234rearfrontCD01234frontABCrearintQueueLength(SueueQ){return(Q.rear-Q.front+MAXSIZE)%MAXSIZE;}1〕只能在队尾删除元素，即出队在队尾只能在队头插入元素，即入队在对头2〕入队：推断
50、队满，Q.elem[Q.rear]=e(Q.rear+1)%MAXSIZE；3〕出队：推断队空，e=Q.elem[Q.front](Q.front+1)%MAXSIZE；4〕空队：Q.rear==Q.front；5〕队满：(Q.rear+1)%MAXSIZE==Q.front5.循环队列的基本操作特点循环队列的队空和队满推断问题解决方案二2.设置一个标志队空条件:队满条件:rear=fronttag=0rear=fronttag=1假设标志位tag，初值=0当入队列操作成功，tag=1;当出队列操作成功，tag=0;循环
51、队列的队空和队满推断问题解决方案三3.设置一个计数器队空条件:队满条件:count=0count=MAXSIZE假设计数器count，初值=0当入队列操作成功，count+1;当出队列操作成功，count-1;这样，count不仅具有计数功能，而且可以起到标识作用队空条件:队满条件:rear=front(rear+1)%maxsize=front循环队列的队空和队满推断问题解决方案1.少用一个存储单元2.设置一个标志3.设置一个计数器队空条件:队满条件:rear=fronttag=0rear=fronttag=1队空条件
52、:队满条件:count=0count=maxsize3.2.3队列应用举例第1行1第2行11第3行121第4行1331第5行14641杨辉三角〔二项式系数值〕：设第i行的值：(a[0]=0)a[1]..a[i](a[i+1]=0)则第i+1行的值:b[j]=a[j-1]+a[j],j=1,2,…,i+1例打印杨辉三角01011012队头队尾1013310121111000voidYangHuiTriAngle(inth){inti;ElemTypex,e;SeueueQ;InitQueue(EnterQueue(EnterQueue(EnterQueue(
53、for(i=1;ih;i++){do{DeleteQueue(if(x!=0)printf(%d,x);elseprintf(n);GetFront(EnterQueue(}while(e!=0);EnterQueue(}while(!IsEmpty(Q)){DeleteQueue(printf(%d,x);}}患者看病的过程:先排队等候，再看病治疗患者到达诊室，查看前面还有多少人等待患者将病例交给护士,排到等候队列中候诊护士从等候队列中取出下一个患者的病例,该患者进入
54、诊室看病。护士停止挂号，依次将剩余患者看完为止护士退出系统。例模拟患者医院看病过程求队列长度，即:QueueLength(Q)元素入队列，即:EnQueue(Q,n);元素出队列，即:DeQueue(Q,n);若队列不空，则将所以元素依次出队患者将病例交给护士,排到等候队列中候诊printf(npleaseinputnubmer:);scanf(%d,EnQueue(Q,n);length=QueueLength(Q)printf(%dpersonwaiti