3.1.1棧的定義及基本運(yùn)算

3.1棧(Stack)假設(shè)棧S=(a1，a2，a3，…an)，則a1稱為棧底元素，an為棧頂元素。棧中元素按a1，a2，a3，…an的次序進(jìn)棧，退棧的第一個(gè)元素應(yīng)為棧頂元素。換句話說(shuō)，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧又稱為后進(jìn)先出(LIFO)表。棧是限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端為棧底(Bottom)。當(dāng)棧中沒(méi)有元素時(shí)稱為空棧。3.1.1棧的定義及基本運(yùn)算3.1棧(Stac例、一疊書或一疊盤子。

anan-1a2a1棧頂棧底……例、一疊書或一疊盤子。an抽象數(shù)據(jù)類型——棧ADTStack{數(shù)據(jù)對(duì)象:

D={ai|aiElemSet,i=1,2,…,n(n>=0)

}

數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1,aiD,i=2,3,…,n

}

約定an端為棧頂，a1端為棧底?；静僮?

InitStack(&S)

操作結(jié)果:建立一個(gè)空棧S

DestroyStack(&S)

初始條件：棧S已存在操作結(jié)果:棧S被銷毀

抽象數(shù)據(jù)類型——棧ADTStack{ClearStack(&S)初始條件：棧S已存在操作結(jié)果:將S棧清空StackEmpty(S)初始條件：棧S已存在操作結(jié)果：若棧S為空棧，返回true,否則返回falseStackLength(S)初始條件：棧S已存在操作結(jié)果:返回S的元素個(gè)數(shù)GetTop(S,&e)//讀棧頂元素初始條件：棧S已存在且非空操作結(jié)果:用e返回棧頂元素ClearStack(&S)Push(&S,e)//入棧初始條件：棧S已存在操作結(jié)果:將元素e插入到棧頂Pop(&S,&e)//出棧初始條件：棧S已存在且非空操作結(jié)果:刪除S的棧頂元素，用e返回StackTraverse(S,visit())初始條件：棧S已存在且非空操作結(jié)果:從棧底到棧頂依次對(duì)S的每個(gè)元素調(diào)用visit()}ADTStackPush(&S,e)//入棧由于棧的邏輯結(jié)構(gòu)與線性表相同，因此線性表的存儲(chǔ)結(jié)構(gòu)對(duì)棧也適應(yīng)。3.1.2棧的表示和實(shí)現(xiàn)順序棧鏈棧由于棧的邏輯結(jié)構(gòu)與線性表相同，因此線性表的存儲(chǔ)結(jié)構(gòu)棧的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序棧，由于棧底位置是固定不變的，所以可以將棧底位置設(shè)置在數(shù)組兩端的任何一端；而棧頂位置是隨著入棧和出棧操作而變化的.順序棧棧的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序棧，由于棧底位置是固定不變的，所以順序棧的類型定義如下：#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{SElemType*base;

//棧底指針，base=NULL表明棧不存在SElemType*top;

//棧頂指針,top==base為棧空的標(biāo)志intstacksize;//棧當(dāng)前可以使用的最大容量}SqStack;順序棧的類型定義如下：棧頂指針top,指向棧底位置top入棧Atop出棧棧滿BCDEF設(shè)數(shù)組大小為stacksizetop==base,?？眨藭r(shí)出棧，則下溢（underflow)top==stacksize,棧滿，此時(shí)入棧，則上溢（overflow)toptoptoptoptoptoptoptoptoptoptop?？誸op123450棧空base123450ABCDEFbase123450base順序棧的入棧與出棧棧頂指針top,指向棧底top入棧Atop出棧棧滿BCDEF0M-1棧1底棧1頂棧2底棧2頂在一個(gè)程序中同時(shí)使用兩個(gè)棧0M-1棧1底棧1頂棧2底棧2頂在一個(gè)程序中同時(shí)使用兩個(gè)棧1、構(gòu)造一個(gè)空棧

StatusInitSatck(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;}//endInitSatck

基本操作的算法描述1、構(gòu)造一個(gè)空?；静僮鞯乃惴枋?、返回棧頂元素

StatusGetTop(SqStackS，SElemTtype&e){if(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}//endGetTop2、返回棧頂元素3、入棧StatusPush(SqStack&S，SElemTypee){if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+

STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;//endPush3、入棧4、出棧

StatusPop(SqStack&S，SElemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}//endPop

4、出棧棧頂…...topdatanext棧底鏈棧其操作與線性鏈表類似^棧頂…...topdatanext棧底鏈棧其操作與線性鏈表類3.2.1數(shù)制轉(zhuǎn)換3.2.2括號(hào)匹配的檢驗(yàn)3.2.3行編輯程序3.2.5表達(dá)式求值3.2棧的應(yīng)用舉例3.2.1數(shù)制轉(zhuǎn)換3.2棧的應(yīng)用舉例十進(jìn)制n和其它進(jìn)制數(shù)d的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問(wèn)題,其解決方法很多,其中一個(gè)簡(jiǎn)單算法基于下列原理:n=(ndivd)*d+nmodd(其中:div為整除運(yùn)算,mod為求余運(yùn)算)例如(1348)10=(2504)8，其運(yùn)算過(guò)程如下：3.2.1數(shù)制轉(zhuǎn)換十進(jìn)制n和其它進(jìn)制數(shù)d的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的3.2.1例如：（1348)10=(2504)8，其運(yùn)算過(guò)程如下：

計(jì)算順序輸出順序nndiv8nmod8

13481684168210

2125

202例如：（1348)10=(2504)8，

計(jì)算順序輸出算法3.1

voidconversion(){//十進(jìn)制轉(zhuǎn)換為等值的八進(jìn)制Initstack(S);scanf(“%d”,N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);printf(“%d”,e);}}//endconversion算法3.1假設(shè)表達(dá)式中充許括號(hào)嵌套,則檢驗(yàn)括號(hào)是否匹配的方法可用“期待的急迫程度”這個(gè)概念來(lái)描述。例：{[()()]}123456783.2.2括號(hào)匹配的檢驗(yàn)分析出現(xiàn)的不匹配的情況:到來(lái)的右括號(hào)不是所“期待”的;假設(shè)表達(dá)式中充許括號(hào)嵌套,則檢驗(yàn)括號(hào)是否匹配的方法3.2.21）凡出現(xiàn)左括號(hào)，則入棧；2）凡出現(xiàn)右括號(hào)，首先檢查棧是否空.若?？?，則表明該“右括號(hào)”多余,

否則和棧頂元素比較，

若相匹配，則“左括號(hào)出?！?否則表明括號(hào)不匹配.3）表達(dá)式檢驗(yàn)結(jié)束時(shí)，

若?？眨瑒t表明表達(dá)式中括號(hào)匹配,

否則表明“左括號(hào)”有余算法的設(shè)計(jì)思想：1）凡出現(xiàn)左括號(hào)，則入棧；2）凡出現(xiàn)右括號(hào)，首先檢查棧是否空Statusmatching(string&exp){intstate=1;InitStack(S);while(i<=StrLength(exp)&&state)switchofexp[i]{case“(”:{Push(S,exp[i]);i++;break;}case“)”:{if(!StackEmpty(S)&&GetTop(S)=“(”){Pop(S,e);i++;}else{state=0;}break;}if(StackEmpty(S)&&state)returnOK;}檢驗(yàn)括號(hào)匹配的算法：Statusmatching(string&exp)在用戶輸入程序或數(shù)據(jù)時(shí)，允許用戶輸入出差錯(cuò)，當(dāng)發(fā)現(xiàn)有誤時(shí)，可以及時(shí)更正。方法是：設(shè)立一個(gè)輸入緩沖區(qū)，用于接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)。假設(shè)退格符“#”表示前一個(gè)字符無(wú)效；退行符“@”表示當(dāng)前行中的字符全無(wú)效。3.2.3行編輯程序假設(shè)從終端接受了這樣兩行字符

whli##ilr#e（s#*s)outcha@putchar(*s=#++);則實(shí)際有效的是下列兩行：

while(*s)putchar(*s++);在用戶輸入程序或數(shù)據(jù)時(shí)，允許用戶輸入出差錯(cuò)，當(dāng)發(fā)現(xiàn)有誤時(shí)，可voidLineEdit(){

InitStack(S);//棧S設(shè)為輸入緩沖區(qū)

ch=getchar();

while(ch!=eof){

while(ch!=eof&&ch!=‘\n’){

switch(ch){case‘#’:Pop(S,ch);//書上為ccase‘@’:ClearStack(S);default:Push(S,ch);}//endswitchch=getchar();}//endwhile將從棧底到棧頂內(nèi)的字符傳送到用戶數(shù)據(jù)區(qū)；ClearStack(s);if(ch!=eof)ch=gethar();}//endwhileDestroyStack(s);}//endLineEdit行編輯程序算法：voidLineEdit(){行編輯程序算法：

3.2.5表達(dá)式求值例如：3*（7–2）（1）算術(shù)四則運(yùn)算的規(guī)則：a.

從左算到右b.

先乘除，后加減c.

先括號(hào)內(nèi)，后括號(hào)外由此，此表達(dá)式的計(jì)算順序?yàn)椋?*（7–2）=3*5=153.2.5表達(dá)式求值例如：3*（7–2）（2）根據(jù)上述三條運(yùn)算規(guī)則，在運(yùn)算的每一步中，對(duì)任意相繼出現(xiàn)的算符1和2，都要比較優(yōu)先權(quán)關(guān)系。算符優(yōu)先法所依據(jù)的算符間的優(yōu)先關(guān)系見(jiàn)教材P53表3.1由表可看出，右括號(hào))

和井號(hào)#

作為2時(shí)級(jí)別最低；由c規(guī)則得出：*，/，+，-為1時(shí)的優(yōu)先權(quán)低于‘（’，高于‘）’由a規(guī)則得出：‘（’==‘）’表明括號(hào)內(nèi)運(yùn)算，已算完?！?’==‘#’表明表達(dá)式求值完畢。令OP={+，-，*，/，（，），#}3.2.5表達(dá)式求值（2）根據(jù)上述三條運(yùn)算規(guī)則，在運(yùn)算的每一步中，對(duì)任意相繼出現(xiàn)（3）算法思想：設(shè)兩個(gè)棧：操作符棧OPTR，操作數(shù)棧OPND棧初始化：設(shè)操作數(shù)棧OPND為空；操作符棧OPTR的棧底元素為表達(dá)式起始符‘#’；依次讀入字符：是操作數(shù)則入OPND棧，是操作符則要判斷：

if

操作符(1)<棧頂元素(2)，則出棧、計(jì)算，結(jié)果壓入OPND棧操作符==棧頂元素且不為‘#’，脫括號(hào)（彈出左括號(hào)）；操作符>棧頂元素，壓入OPTR棧。3.2.5表達(dá)式求值（3）算法思想：3.2.5表達(dá)式求值OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,’3’)

#*(7-2)#3#Push(optr,’*’)#,*3(7-2)#Push(optr,’(’)#,*,(37-2)#Push(opnd,’7’)#,*,(3,7-2)#Push(optr,’-’)#,*,(,－3,72)#Push(opnd,’2’)#,*,(,－3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)例求表達(dá)式3*(7-2)OPTROPNDINPUTOPERATE3*(7-2)#PuStatusEvaluateExpression(OperandType&result){InitStack(OPND);InitStack(OPTR);Push(OPTR,’#’);c=getchar();while((c!=‘#’)&&(GetTop(OPTR)!=‘#’)){if(!In(c,OP){Push(OPND,c);c=getchar();}elseswitch(compare(c,GetTop(OPTR))){case‘>’:Push(OPTR,c);c=getchar();break;case‘=’:Pop(OPTR,x);c=getchar();break;case‘<’:Pop(OPTR,tem);Pop(OPND,b);a=Pop(OPND,a);

result=Operate(a,tem,b);Push(OPND,result);c=getchar();break;}//switch

}//whileresult=GetTop(OPND);}//EndEvaluateExpressionStatusEvaluateExpression(3.2.4迷宮求解

入口出口3.2.4迷宮求解出口求迷宮路徑算法的基本思想是：若當(dāng)前位置“可通”，則納入路徑，繼續(xù)前進(jìn);若當(dāng)前位置“不可通”，則后退，換方向繼續(xù)探索;若四周“均無(wú)通路”，則將當(dāng)前位置從路徑中刪除出去。求迷宮路徑算法的基本思想是：若當(dāng)前位置“可通”，則納入路徑，設(shè)當(dāng)前位置為入口位置do{if(當(dāng)前位置可通){當(dāng)前位置插入棧頂;if(該位置是出口位置)結(jié)束else切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置;}else{if(棧不空棧頂位置尚有其它方向未經(jīng)探索)設(shè)定新的當(dāng)前位置為順時(shí)針?lè)较蛐D(zhuǎn)找到的頂點(diǎn)位置的下一個(gè)鄰塊;if(棧不空且棧頂位置的四周均不通){刪去棧頂元素位置,直至找到一個(gè)可通的相鄰塊或出?；驐？?}}}while(棧不空);求迷宮中一條從入口到出口的路徑的算法思想：設(shè)當(dāng)前位置為入口位置求迷宮中一條從入口到出口的路徑的算法思想Typestruct{intord;//通道塊在路徑上的序號(hào)PosTypeseat;//通道塊在迷宮中的“坐標(biāo)位置”intdi;//從此通道塊走向下一通道塊的方向}SElemType;//棧元素類型StatusMazePath(MazeTypemaze,PosTypestart,PosTypeend){InitStack(S);curpos=start;//當(dāng)前位置為入口位置curstep=1;//探索第一步do{if(Pass(curpos)){//當(dāng)前位置可以通過(guò)footprint(curpos);//留下足印e=(curstep,curpos,1);Push(S,e);//加入路徑if(curpos==end)return(TRUE);//到達(dá)終點(diǎn)curpose=NextPos(curpos,1);

//下一個(gè)位置是當(dāng)前位置的東鄰

curstep++;Typestruct{

else{//當(dāng)前位置不通if(!StackEmpty(S)){Pop(S,e);while(e.di==4&&!StackEmpty(S)){MarkPrint(e.seat);Pop(S,e);//留下不能通過(guò)的標(biāo)記并后退}//endwhileif(e.di<4){e.di++;Push(S,e);//換下一個(gè)方向探索curpos=NextPos(e.seat,e.di);//新位置是舊位置的相鄰塊}//endif}//endif

}//endelse}while(!StackEmpty(S));return(FALSE);}//endMazePathelse{//當(dāng)前位置不通一、函數(shù)的嵌套調(diào)用r主程序srrrs子函數(shù)1rst子函數(shù)2rst子函數(shù)33.3棧與遞歸的實(shí)現(xiàn)一、函數(shù)的嵌套調(diào)用r主程序srrrs子函數(shù)1rst子函數(shù)2r二、遞歸函數(shù)及其實(shí)現(xiàn)3.3棧與遞歸的實(shí)現(xiàn)遞歸：函數(shù)直接或間接的調(diào)用自身實(shí)現(xiàn)：建立遞歸工作棧二、遞歸函數(shù)及其實(shí)現(xiàn)3.3棧與遞歸的實(shí)現(xiàn)例1遞歸的執(zhí)行情況分析--n!

intfact(intw){if(w==0)fact=1;elsefact=w*fact(w-1);}main(){intf;f=fact(3);print(f);}3.3棧與遞歸的實(shí)現(xiàn)例1遞歸的執(zhí)行情況分析--n!intfact(遞歸過(guò)程三要素:1.定義出口2.把一個(gè)大的問(wèn)題劃分成同類型的子問(wèn)題3.解的合成3.3棧與遞歸的實(shí)現(xiàn)遞歸過(guò)程三要素:3.3棧與遞歸的實(shí)現(xiàn)intfact(intw){1if(w==0)

2fact=1;

3else

4fact=w*fact(w-1);}地址wtop遞歸調(diào)用執(zhí)行情況如下：intfact(intw)地址wintfact(intw){1if(w==0)

2fact=1;

3else

4fact=w*fact(w-1);}地址w33*fact(2);4w=3topw遞歸調(diào)用執(zhí)行情況如下：intfact(intw)地址wintfact(intw){1if(w==0)

2fact=1;

3else

4fact=w*fact(w-1);}33*fact(2);w22*fact(1);4w=24w=3topw地址w遞歸調(diào)用執(zhí)行情況如下：intfact(intw)33*fact(211*fact(0);4w=14w=24w=3topwintfact(intw){1if(w==0)

2fact=1;

3else

4fact=w*fact(w-1);}33*fact(2);w22*fact(1);w地址w遞歸調(diào)用執(zhí)行情況如下：11*fact(0);4w=14w=2411*fact(0);4w=14w=24w=3topwintfact(intw){1if(w==0)

2fact=1;

3else

4fact=w*fact(w-1);}33*fact(2);w22*fact(1);w0w地址wfact(0)=1遞歸調(diào)用執(zhí)行情況如下：11*fact(0);4w=14w=24intfact(intw){1if(w==0)

2fact=1;

3else

4fact=w*fact(w-1);}33*fact(2);w22*fact(1);w0wfact(0)=111*fact(0);w4w=24w=3topfact(1)=1地址w遞歸調(diào)用執(zhí)行情況如下：intfact(intw)33*fact(2intfact(intw){1if(w==0)

2fact=1;

3else

4fact=w*fact(w-1);}33*fact(2);w22*fact(1);w0wfact(0)=111*fact(0);wfact(1)=14w=3topfact(2)=2地址w遞歸調(diào)用執(zhí)行情況如下：intfact(intw)33*fact(2intfact(intw){1if(w==0)

2fact=1;

3else

4fact=w*fact(w-1);}33*fact(2);w22*fact(1);w0wfact(0)=111*fact(0);wfact(1)=1fact(2)=2topfact(3)=6地址w遞歸調(diào)用執(zhí)行情況如下：intfact(intw)33*fact(2例2：TowerofHanoi問(wèn)題問(wèn)題描述：有A,B,C三個(gè)塔座，A上套有n個(gè)直徑不同的圓盤，按直徑從小到大疊放，形如寶塔,編號(hào)1,2,3……n。要求將n個(gè)圓盤從A移到C，疊放順序不變，移動(dòng)過(guò)程中遵循下列原則：每次只能移一個(gè)圓盤圓盤可在三個(gè)塔座上任意移動(dòng)任何時(shí)刻，每個(gè)塔座上不能將大盤壓到小盤上例2：TowerofHanoi問(wèn)題問(wèn)題描述：有A,B,C解決方法n=1時(shí)，直接把圓盤從A移到Cn>1時(shí)，先把上面n-1個(gè)圓盤從A移到B,然后將n號(hào)盤從A移到C,再將n-1個(gè)盤從B移到C。即把求解n個(gè)圓盤的Hanoi問(wèn)題轉(zhuǎn)化為求解n-1個(gè)圓盤的Hanoi問(wèn)題，依次類推，直至轉(zhuǎn)化成只有一個(gè)圓盤的Hanoi問(wèn)題執(zhí)行情況遞歸工作棧保存內(nèi)容：形參n,x,y,z和返回地址返回地址用行編號(hào)表示nxyz返回地址解決方法執(zhí)行情況nxyzmain(){intm;printf("Inputnumberofdisks");scanf("%d",&n);printf("Steps:%3ddisks",n);hanoi(n,‘A',‘B',‘C');(0)}voidhanoi(intn,charX,charY,charZ)(1){(2)if(n==1)(3)move(1,X,Z);(4)else{(5)hanoi(n-1,X,Z,Y);(6)move(n,X,Z);(7)hanoi(n-1,Y,X,Z);(8)}(9)}ABC1233ABC03ABC02ACB63ABC02ACB61ABC6ABC3ABC02ACB6main()ABC1233ABCmain(){intn;printf("Inputthenumberofdisksscanf("%d",&n);printf("Thestepstomoving%3dhanoi(n,'X','Y',‘Z');(0)}voidhanoi(intn,charX,charY,charZ)(1){(2)if(n==1)(3)move(1,X,Z);(4)else{(5)hanoi(n-1,X,Z,Y);(6)move(n,X,Z);(7)hanoi(n-1,Y,X,Z);(8)}(9)}ABC3ABC02ACB61CAB8ABC3ABC02ACB63ABC03ABC02ACB6main()ABC3ABCmain(){intn;printf("Inputthenumberofdisksscanf("%d",&n);printf("Thestepstomoving%3dhanoi(n,'X','Y','Z');(0)}voidhanoi(intn,charX,charY,charZ)(1){(2)if(n==1)(3)move(1,X,Z);(4)else{(5)hanoi(n-1,X,Z,Y);(6)move(n,X,Z);(7)hanoi(n-1,Y,X,Z);(8)}(9)}ABC3ABC02BAC83ABC02BAC81BCA6ABC3ABC02BAC83ABC0main()ABC3ABCmain(){intn;printf("Inputthenumberofdisksscanf("%d",&n);printf("Thestepstomoving%3dhanoi(n,'X','Y','Z');(0)}voidhanoi(intn,charX,charY,charZ)(1){(2)if(n==1)(3)move(1,X,Z);(4)else{(5)hanoi(n-1,X,Z,Y);(6)move(n,X,Z);(7)hanoi(n-1,Y,X,Z);(8)}(9)}ABC3ABC02BAC81ABC8ABC3ABC02BAC83ABC0?？?ABC02BAC8main()ABC3ABC3.4隊(duì)列3.4.1抽象數(shù)據(jù)類型隊(duì)列的定義隊(duì)列的定義及特點(diǎn)定義：隊(duì)列是限定只能在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除的線性表。隊(duì)尾(rear)——允許插入的一端隊(duì)頭(front)——允許刪除的一端隊(duì)列特點(diǎn)：先進(jìn)先出(FIFO)

3.4隊(duì)列

ADTQueue{數(shù)據(jù)對(duì)象：

D={ai|aiQElemSet,i=1,2,…,n,n>=0

}

數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1,aiD,i=2,…,n}

基本操作:

InitQueue(&Q)

操作結(jié)果:構(gòu)造一個(gè)空隊(duì)列Q

DestroyQueue(&Q)

初始條件:隊(duì)列已存在

操作結(jié)果:隊(duì)列Q被銷毀，不再存在

抽象數(shù)據(jù)類型隊(duì)列的定義ADTQueue{抽象數(shù)據(jù)類型隊(duì)列的定義ClearQueue(&Q)

初始條件:隊(duì)列已存在

操作結(jié)果:將Q清為空隊(duì)列QueueEmpty(Q)初始條件:隊(duì)列已存在

操作結(jié)果:若Q為空隊(duì)列，返回true,否則返回falseQueueLength(Q)初始條件:隊(duì)列已存在

操作結(jié)果:返回Q的元素個(gè)數(shù)GetHead(Q,&e)

初始條件:隊(duì)列Q非空

操作結(jié)果:用e返回隊(duì)頭元素ClearQueue(&Q)EnQueue(&Q,e)//入隊(duì)初始條件:隊(duì)列已存在

操作結(jié)果:插入元素e為Q的新隊(duì)尾元素DeQueue(&Q,&e)//出隊(duì)初始條件:隊(duì)列Q非空

操作結(jié)果:刪除Q的隊(duì)頭元素，用e返回QueueTraverse(Q,visit())初始條件:隊(duì)列Q非空

操作結(jié)果:從隊(duì)頭到隊(duì)尾，依次對(duì)Q的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit().一旦visit()失敗，則操作失敗}ADTQueueEnQueue(&Q,e)//入隊(duì)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈隊(duì)列，它是限制僅在表頭刪除和表尾插入的單鏈表。顯然僅有單鏈表的頭指針不便于在表尾做插入操作，為此再增加一個(gè)尾指針，指向鏈表的最后一個(gè)結(jié)點(diǎn)。于是，將鏈隊(duì)列的類型LinkQueue定義為一個(gè)結(jié)構(gòu)類型：3.4.2鏈隊(duì)列typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈隊(duì)列，它是限制僅在表頭刪除和表尾插頭5836^frontrearQ.頭^frontrearQ.LinkQueueQ;隊(duì)列：出隊(duì)端入隊(duì)端空隊(duì)列：頭5836^frontQ.頭^frontQ.LinkQue1.構(gòu)造一個(gè)空隊(duì)列voidInitQueue(LinkQueue&Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

//if(!Q.front)exit(OVERFLOW);Q.front->next=NULL;}//endInitQueue

鏈隊(duì)列上實(shí)現(xiàn)的基本運(yùn)算：1.構(gòu)造一個(gè)空隊(duì)列鏈隊(duì)列上實(shí)現(xiàn)的基本運(yùn)算：2.銷毀隊(duì)列voidDestoryQueue(LinkQueue&Q){while(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}//endwhile}//endDestoryQueue2.銷毀隊(duì)列3.入隊(duì)voidEnQueue(LinkQueue&Q,QElemTypee){p=(QueuePtr)malloc(sizeof(QNode));p–>data=e;p–>next=null;Q.rear->next=p;Q.rear=p;}//endEnQueue

隊(duì)首隊(duì)尾frontrear……^隊(duì)首隊(duì)尾frontrear……^3.入隊(duì)隊(duì)首隊(duì)尾frontrear……^隊(duì)首隊(duì)尾frontr4.出隊(duì)StatusDeQueue(LinkQueue&Q,QElemType&e){if(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);}//endDeQueue注意：在出隊(duì)算法中，一般只需修改隊(duì)頭指針。但當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí)，該結(jié)點(diǎn)既是隊(duì)頭也是隊(duì)尾，故刪去此結(jié)點(diǎn)時(shí)亦需修改尾指針，且刪去此結(jié)點(diǎn)后隊(duì)列變空。隊(duì)首隊(duì)尾frontrear……^隊(duì)首front……隊(duì)尾^rear4.出隊(duì)注意：在出隊(duì)算法中，一般只需修改隊(duì)頭指針。但當(dāng)原隊(duì)123450frontJ1,J2,J3入隊(duì)rearJ1,J2,J3出隊(duì)J1J2J3rear123450front3.4.3循環(huán)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)（用一維數(shù)組實(shí)現(xiàn)sq[M]）J1J2J3rearJ4,J5,J6入隊(duì)rear123450J4J5J6front設(shè)兩個(gè)指針front,rear,約定：front指示隊(duì)頭元素；rear指示隊(duì)尾元素的下一個(gè)位置；初值front=rear=0入隊(duì)列：sq[rear++]=x;rearrearfrontfront空隊(duì)列條件：front==rearfront=0rear=0123450隊(duì)空出隊(duì)列：x=sq[front++];front123450frontJ1,J2,J3入隊(duì)rea存在問(wèn)題設(shè)數(shù)組維數(shù)為M，則：當(dāng)front=0,rear=M時(shí)，再有元素入隊(duì)發(fā)生溢出——真溢出當(dāng)front0,rear=M時(shí)，再有元素入隊(duì)發(fā)生溢出——假溢出解決方案隊(duì)首固定，每次出隊(duì)后剩余元素向下移動(dòng)——浪費(fèi)時(shí)間循環(huán)隊(duì)列基本思想：把隊(duì)列設(shè)想成環(huán)形，讓sq[0]接在sq[M-1]之后，若rear+1==M,則令rear=0;0M-11frontrear…...…...實(shí)現(xiàn)：利用“模”運(yùn)算入隊(duì)：rear=(rear+1)%M;sq[rear]=x;出隊(duì)：front=(front+1)%M;x=sq[front];存在問(wèn)題0M-11frontrear…...…...實(shí)現(xiàn)：利012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始狀態(tài)J4,J5,J6出隊(duì)J7,J8,J9入隊(duì)隊(duì)空：front==rear解決方案：1.另外設(shè)一個(gè)標(biāo)志以區(qū)別隊(duì)空、隊(duì)滿2.少用一個(gè)元素空間隊(duì)空：front==rear隊(duì)滿：(rear+1)%M==front隊(duì)尾指針加1追上隊(duì)頭，隊(duì)列中有一個(gè)空額，但避免判斷標(biāo)志的時(shí)間上的損失隊(duì)滿：front==rear012345rearfrontJ4J5J6012345rea循環(huán)隊(duì)列類型說(shuō)明：#defineQueueSize100typedefStruct{intfront;intrear;QElemType*base;或QElemTypedata[QueueSize];}SqQueue;循環(huán)隊(duì)列類型說(shuō)明：基本操作的算法描述1.構(gòu)造空隊(duì)列voidInitQueue(SqQueue&Q){

Q.base=(QElemType*)malloc(QueueSize*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;}基本操作的算法描述1.構(gòu)造空隊(duì)列2.返回隊(duì)列長(zhǎng)度intQueueLength(SqQueueQ){Return(Q.rear-Q.front+QueueSize)%QueueSize;}2.返回隊(duì)列長(zhǎng)度基本操作的算法描述3.入隊(duì)StatusEnQueue(SqQueue&Q,QElemTypee){if((Q.rear+1)%QueueSiz