第三章 棧和隊(duì)列

第三章棧和隊(duì)列1棧和隊(duì)列是重要的數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列是線性表的子集（是插入和刪除受限的線性表）前言2【學(xué)習(xí)目標(biāo)】

1.掌握棧和隊(duì)列這兩種抽象數(shù)據(jù)類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問題中正確選用它們。

2.熟練掌握棧類型的兩種實(shí)現(xiàn)方法。

3.熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法。

4.理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程。

【重點(diǎn)和難點(diǎn)】

棧和隊(duì)列是在程序設(shè)計(jì)中被廣泛使用的兩種線性數(shù)據(jù)結(jié)構(gòu)，因此本章的學(xué)習(xí)重點(diǎn)在于掌握這兩種結(jié)構(gòu)的特點(diǎn)，以便能在應(yīng)用問題中正確使用。

3【學(xué)習(xí)指南】

在這一章中，主要是學(xué)習(xí)如何在求解應(yīng)用問題中適當(dāng)?shù)貞?yīng)用棧和隊(duì)列，棧和隊(duì)列在兩種存儲(chǔ)結(jié)構(gòu)中的實(shí)現(xiàn)都不難，但應(yīng)該對(duì)它們了如指掌，特別要注意它們的基本操作實(shí)現(xiàn)時(shí)的一些特殊情況，如棧滿和?？铡㈥?duì)滿和隊(duì)空的條件以及它們的描述方法。4【課前思考】

1.什么是線性結(jié)構(gòu)？簡(jiǎn)單地說，線性結(jié)構(gòu)是一個(gè)數(shù)據(jù)元素的序列。

2.你見過餐館中一疊一疊的盤子嗎？如果它們是按1,2,…,n的次序往上疊的,那么使用時(shí)候的次序應(yīng)是什么樣的？必然是依從上往下的次序，即n,…,2,1。它們遵循的是"后進(jìn)先出"的規(guī)律，這正是本章要討論的"棧"的結(jié)構(gòu)特點(diǎn)。

3.在日常生活中，為了維持正常的社會(huì)秩序而出現(xiàn)的常見現(xiàn)象是什么？是"排隊(duì)"。在計(jì)算機(jī)程序中，模擬排隊(duì)的數(shù)據(jù)結(jié)構(gòu)是"隊(duì)列"。5棧必須按“后進(jìn)先出”的規(guī)則進(jìn)行操作隊(duì)列必須按“先進(jìn)先出”的規(guī)則進(jìn)行操作和線性表相比，它們的插入和刪除操作受更多的約束和限定，故又稱為限定性的線性表結(jié)構(gòu)從“數(shù)據(jù)結(jié)構(gòu)”的角度看:

它們都是線性結(jié)構(gòu)，即數(shù)據(jù)元素之間的關(guān)系相同。

但它們是完全不同的數(shù)據(jù)類型。除了它們各自的基本操作集不同外，主要區(qū)別是對(duì)插入和刪除操作的"限定"。6通常稱，棧和隊(duì)列是限定插入和刪除只能在表的“端點(diǎn)”進(jìn)行的線性表。

線性表?xiàng)ｊ?duì)列Insert(L,

i,x)Insert(S,n+1,x)Insert(Q,n+1,x)

1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)

1≤i≤n棧和隊(duì)列是兩種常用的數(shù)據(jù)類型7

3.1

棧8

3.1.1棧的類型定義

棧（Stack）是限定只能在表的一端進(jìn)行插入和刪除操作的線性表。在表中，允許插入和刪除的一端稱作“棧頂(top)”，不允許插入和刪除的一端稱作“棧底(bottom)"。9通常稱往棧頂插入元素的操作為"入棧"，稱刪除棧頂元素的操作為"出棧"。因?yàn)楹笕霔５脑叵扔谙热霔５脑爻鰲＃时环Q為是一種"后進(jìn)先出"的結(jié)構(gòu)，因此又稱LIFO（LastInFirstOut的縮寫）表。很多書上都以如下圖所示的鐵路調(diào)度站形象地表示棧的這個(gè)特點(diǎn)。

10棧的類型定義

ADTStack{

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

D＝{ai|ai

∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關(guān)系：

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

約定an

端為棧頂，a1端為棧底?；静僮鳎?/p>

}ADTStack11InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(S)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())12

InitStack(&S)

操作結(jié)果：構(gòu)造一個(gè)空棧S。

DestroyStack(&S)

初始條件：棧S已存在。

操作結(jié)果：棧S被銷毀。13StackEmpty(S)

初始條件：棧S已存在。

操作結(jié)果：若棧S為空棧，則返回

TRUE，否則FALSE。

判定棧是否為空棧是棧在應(yīng)用程序

中經(jīng)常使用的操作，通常以它作為循環(huán)結(jié)束的條件。14

StackLength(S)

初始條件：棧S已存在。

操作結(jié)果：返回S的元素個(gè)數(shù)，

即棧的長(zhǎng)度。15GetTop(S,&e)

初始條件：棧S已存在且非空。

操作結(jié)果：用e返回S的棧頂元素,并

不將它從棧中刪除。

a1a2an……e16ClearStack(&S)

初始條件：棧S已存在。

操作結(jié)果：將

S清為空棧。

17Push(&S,e)

初始條件：棧S已存在。

操作結(jié)果：插入元素e為新的棧

頂元素。

a1a2ane……18Pop(&S,&e)

初始條件：棧S已存在且非空。

操作結(jié)果：刪除S的棧頂元素，

并用e返回其值。a1a2anan-1

……e19StackTraverse(S,visit())初始條件：棧S已存在且非空，visit()為元素的訪問函數(shù)。

操作結(jié)果：從棧底到棧頂依次對(duì)S的每個(gè)元素調(diào)用函數(shù)visit()，一旦

visit()失敗，則操作失敗。

這是對(duì)棧進(jìn)行從棧底到棧頂?shù)摹氨闅v”操作，應(yīng)用較多的場(chǎng)合是，輸出棧中所有數(shù)據(jù)元素。

20順序棧3.1.2棧的表示和實(shí)現(xiàn)類似于線性表的順序映象實(shí)現(xiàn)，指向表尾的指針可以作為棧頂指針。//-----棧的順序存儲(chǔ)表示

-----#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;

typedef

struct{

SElemType*base;

SElemType*top;

int

stacksize;}SqStack;21實(shí)現(xiàn)：一維數(shù)組s[M]top123450進(jìn)棧A棧滿BCDEF設(shè)數(shù)組維數(shù)為Mtop=base,?？?此時(shí)出棧,則下溢（underflow)top=M,棧滿,此時(shí)入棧,則上溢（overflow)toptoptoptoptop123450空棧topbasebasetop出棧toptop棧空base棧底指針base,始終指向棧底位置；棧頂指針top,其初值指向棧底，始終在棧頂元素的下一個(gè)位置123450ABtop22

StatusInitStack(SqStack&S){//構(gòu)造一個(gè)空棧SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存儲(chǔ)分配失敗

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;returnOK;}23

StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){//棧滿，追加存儲(chǔ)空間

S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*

sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存儲(chǔ)分配失敗

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}24StatusPop(SqStack&S,SElemType&e){//若棧不空，則刪除S的棧頂元素，

//用e返回其值，并返回OK；

//否則返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK;}25在一個(gè)程序中同時(shí)使用兩個(gè)棧：0M-1棧1底棧1頂棧2底棧2頂263.2棧的應(yīng)用舉例由于棧的操作具有后進(jìn)先出的固有特性，致使棧成為程序設(shè)計(jì)中的有用工具。凡應(yīng)用問題求解的過程具有"后進(jìn)先出"的天然特性的話，則求解的算法中也必然需要利用"棧"。27棧的應(yīng)用舉例例一、數(shù)制轉(zhuǎn)換例二、括號(hào)匹配的檢驗(yàn)例三、行編輯程序問題例四、迷宮求解例五、表達(dá)式求值例六、實(shí)現(xiàn)遞歸28例一、數(shù)制轉(zhuǎn)換

十進(jìn)制數(shù)N和其他d進(jìn)制數(shù)的轉(zhuǎn)換是

計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問題，其解決方

法很多，其中一個(gè)簡(jiǎn)單算法基于下列原

理：

N=(Ndivd)×d+Nmodd

(其中：div為整除運(yùn)算，mod為求余運(yùn)算)29

NNdiv8Nmod8

13481684

168210

2125

202計(jì)算順序輸出順序例如：（1348)10=(2504)8，

其運(yùn)算過程如下：30voidconversion(){

InitStack(S);//構(gòu)造空棧

scanf("%d",&N);//輸入一個(gè)十進(jìn)制數(shù)

while(N){Push(S,N%8);//"余數(shù)"入棧

N=N/8;

//非零"商"繼續(xù)運(yùn)算

}while(!StackEmpty(S)){

//和"求余"所得相逆的順序輸出八進(jìn)制的各位數(shù)

Pop(S,&e);

printf("%d",e);}}//conversion31例二、括號(hào)匹配的檢驗(yàn)假設(shè)在表達(dá)式中［］（））或［（［］［］）］等為正確的格式，［（］）或（［]（）或（（）））均為不正確的格式。則檢驗(yàn)括號(hào)是否匹配的方法可用“期待的急迫程度”這個(gè)概念來描述。32

即后出現(xiàn)的"左括弧"，它等待與其匹配的"右括弧"出現(xiàn)的"急迫"心情要比先出現(xiàn)的左括弧高。換句話說，對(duì)"左括弧"來說，后出現(xiàn)的比先出現(xiàn)的"優(yōu)先"等待檢驗(yàn)，對(duì)"右括弧"來說，每個(gè)出現(xiàn)的右括弧要去找在它之前"最后"出現(xiàn)的那個(gè)左括弧去匹配。顯然，必須將先后出現(xiàn)的左括弧依次保存，為了反映這個(gè)優(yōu)先程度，保存左括弧的結(jié)構(gòu)用棧最合適。這樣對(duì)出現(xiàn)的右括弧來說，只要"棧頂元素"相匹配即可。如果在棧頂?shù)哪莻€(gè)左括弧正好和它匹配，就可將它從棧頂刪除。

33分析可能出現(xiàn)的不匹配的情況:到來的右括弧并非是所“期待”的；例如：考慮下列括號(hào)序列：

[([][])]12345678到來的是“不速之客”；直到結(jié)束，也沒有到來所“期待”的括弧。34這三種情況對(duì)應(yīng)到棧的操作即為：

1．和棧頂?shù)淖罄ɑ〔幌嗥ヅ洌?/p>

2．棧中并沒有左括弧等在哪里；

3．棧中還有左括弧沒有等到和它 相匹配的右括弧。35算法的設(shè)計(jì)思想：1）凡出現(xiàn)左括弧，則進(jìn)棧；2）凡出現(xiàn)右括弧，首先檢查棧是否空

若?？?，則表明該“右括弧”多余，

否則和棧頂元素比較，

若相匹配，則“左括弧出棧”，

否則表明不匹配。3）表達(dá)式檢驗(yàn)結(jié)束時(shí)，

若?？?，則表明表達(dá)式中匹配正確，

否則表明“左括弧”有余。36Statusmatching(charexp[]){

intstate=1;while(i<=Length(exp)&&state){switchexp[i]{case'('||'['

:{Push(S,exp[i]);i++;break;}case')'

:{if(！StackEmpty(S)&&GetTop(S)=‘(’

){Pop(S,e);i++;}else{state=0;}break;}case‘]'

:{if(！StackEmpty(S)&&GetTop(S)=‘['）

{Pop(S,e);i++;}else{state=0;}break;}}if(StackEmpty(S)&&state)returnOK;…...37例三、行編輯程序問題如何實(shí)現(xiàn)？“每接受一個(gè)字符即存入存儲(chǔ)器”?并不恰當(dāng)！38設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū),并假設(shè)“#”為退格符，“@”為退行符。在用戶輸入一行的過程中，允許用戶輸入出差錯(cuò)，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。合理的作法是：39假設(shè)從終端接受了這樣兩行字符：

whli##ilr#e（s#*s)

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

while(*s)

putchar(*s++);40可設(shè)這個(gè)輸入緩沖區(qū)為一個(gè)棧結(jié)構(gòu)，每當(dāng)從終端接受了一個(gè)字符之后先作如下判斷：

1、既不是退格也不是退行符，則將該字符壓入棧頂；

2、如果是一個(gè)退格符，則從棧頂刪去一個(gè)字符；

3、如果是一個(gè)退行符，則將字符棧清為空棧。41

while(ch!=EOF&&ch!='\n'){ switch(ch){case‘#’:Pop(S,c);break;//棧非空，退棧

case'@':ClearStack(S);break;//重置S為空棧

default:Push(S,ch);break;//未考慮棧滿

}

ch=getchar();//從終端接收下一個(gè)字符

}ClearStack(S);//重置S為空棧if(ch!=EOF)ch=getchar();}

ch=getchar();

ClearStack(S);//重置S為空棧

while(ch!=EOF){//EOF為全文結(jié)束符將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)；42例四、迷宮求解通常用的是“窮舉求解”的方法43

為了保證在任何位置上都能沿原路退回,需要用一個(gè)“后進(jìn)先出”的結(jié)構(gòu)即棧來保存從入口到當(dāng)前位置的路徑。并且在走出出口之后,棧中保存的正是一條從入口到出口的路徑所謂“下一位置”指的是“當(dāng)前位置”四周四個(gè)方向（東、南、西、北）上相鄰的方塊。假設(shè)以棧S記錄“當(dāng)前路徑”，則棧頂中存放的是“當(dāng)前路徑上最后一個(gè)通道塊”。

“納入路徑”的操作即為“當(dāng)前位置入棧；

“從當(dāng)前路徑上刪除前一通道塊”的操作即為"出棧"。44迷宮路徑算法的基本思想：若當(dāng)前位置“可通”,則納入路徑，繼續(xù)前進(jìn);若當(dāng)前位置“不可通”,則后退,換方向繼續(xù)探索;若四周“均無(wú)通路”,則將當(dāng)前位置從路徑中刪除出去。45設(shè)定當(dāng)前位置的初值為入口位置；

do｛

若當(dāng)前位置可通，則｛將當(dāng)前位置插入棧頂；

若該位置是出口位置，則算法結(jié)束；

否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；

}

否則

{

若棧不空且棧頂位置尚有其他方向未被探索，求迷宮中一條從入口到出口的路徑的算法：46

則設(shè)定新的當(dāng)前位置為:沿順時(shí)針方向轉(zhuǎn)找到的棧頂位置的下一相鄰塊；

若棧不空但棧頂位置的四周均不可通，則{刪去棧頂位置；//從路徑中刪去該通道塊

若棧不空，則重新測(cè)試新的棧頂位置，直至找到一個(gè)可通的相鄰塊或出棧至棧空；

}

}

}while(棧不空)；若?？?，則表明迷宮沒有通路。47例五、表達(dá)式求值任何一個(gè)表達(dá)式都是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成。

操作數(shù)可以是常數(shù)也可以是被說明為變量或常量的標(biāo)識(shí)符；

運(yùn)算符可以分為算術(shù)運(yùn)算符、關(guān)系運(yùn)算符和邏輯運(yùn)算符等三類；

基本界限符有左右括弧和表達(dá)式結(jié)束符等。48

限于二元運(yùn)算符的表達(dá)式定義:

Exp=S1OPS2

操作數(shù):變量、常量、表達(dá)式運(yùn)算符:算術(shù)運(yùn)算符、關(guān)系運(yùn)算符、邏輯運(yùn)算符界限符：括號(hào)、結(jié)束符表達(dá)式求值49

表達(dá)式的三種標(biāo)識(shí)方法：設(shè)Exp=S1+OP+S2則稱OP+S1+S2為前綴表示法

S1+OP+S2為中綴表示法

S1+S2+OP為后綴表示法50算術(shù)四則運(yùn)算的規(guī)則：先乘除，后加減從左算到右先括號(hào)內(nèi)，后括號(hào)外運(yùn)算符和界限符通稱為算符。兩個(gè)算符和之間的優(yōu)先關(guān)系：，的優(yōu)先權(quán)低于；，的優(yōu)先權(quán)等于；，的優(yōu)先權(quán)高于。51規(guī)則注意：＋、-、×、/為時(shí)，優(yōu)先權(quán)均低于“（”，但均高于“）”；時(shí)，令，“#”是表達(dá)式的結(jié)束符；表中的“（”與“）”相遇時(shí)，括號(hào)內(nèi)的運(yùn)算完成；當(dāng)“#”遇到“#”時(shí)，表達(dá)式求值完成當(dāng)輸入的運(yùn)算符優(yōu)先權(quán)高于棧頂運(yùn)算符時(shí)，運(yùn)算符入棧52中綴表達(dá)式求值基本算法思想：置操作數(shù)棧為空棧，表達(dá)式起始符“#”為運(yùn)算符棧底元素；依次讀入表達(dá)式中每個(gè)字符，若是操作數(shù)則進(jìn)OPND棧，若是運(yùn)算符棧則和OPTR棧的棧頂運(yùn)算符比較優(yōu)先權(quán)后作相應(yīng)操作，直至整個(gè)表達(dá)式求值完畢（即OPTR棧的的棧頂元素和當(dāng)前讀入的字符均為“#”）。定義兩個(gè)工作棧：一個(gè)為OPTR，寄存運(yùn)算符；一個(gè)為OPND，寄存操作數(shù)或運(yùn)算結(jié)果。53例：3*(7–2)

OPTR棧OPND棧輸入操作1# 3*(7–2)# PUSH(OPND,‘3’)2#3*(7–2)#PUSH(OPTR,‘*’)3#*3(7–2)#PUSH(OPTR,‘(’)4#*(37–2)#PUSH(OPND,‘7’)5#*(37–2)#PUSH(OPTR,‘–’)6#*(–372)#PHSH(OPND,‘2’)7#*(–372)#operate(‘7’,’-’,’2’)8#*(35)#POP(OPTR)9#*35#operate(‘3’,‘*’,‘5’)10#15#returnGetTop(OPND)54OperandType

EvaluateExpression(){//設(shè)OPTR和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧//OP為運(yùn)算符集合。

InitStack(OPTR);Push(OPTR,'#');

initStack(OPND);c=getchar();

while(c!='#'||GetTop(OPTR)!='#'){if(!In(c,OP))//不是運(yùn)算符則進(jìn)棧

{Push((OPND,c);c=getchar();}else

}//whilereturnGetTop(OPND);}//EvaluateExpression……55switch(precede(GetTop(OPTR),c){case'<'://棧頂元素優(yōu)先權(quán)低

Push(OPTR,c);c=getchar();break;case'='://脫括號(hào)并接收下一字符

Pop(OPTR,x);c=getchar();break;case'>'://退棧并將運(yùn)算結(jié)果入棧

Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch56

OPTR為運(yùn)算符的集合，若ch是運(yùn)算符，則函數(shù)IN(ch,OP)的值為“TRUE”。若c(棧頂運(yùn)算符)的優(yōu)先性高于棧頂運(yùn)算符，則函數(shù)precede(GetTop（OPTR),c)值為“>"。……

算法的時(shí)間復(fù)雜度為O(n)，其中n為表達(dá)式字符串的長(zhǎng)度。57

ADTQueue{

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

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

數(shù)據(jù)關(guān)系：

R1＝{<ai-1,ai>|ai-1,ai

∈D,i=2,...,n}

約定其中a1

端為隊(duì)列頭，an

端為隊(duì)列尾基本操作：3.4隊(duì)列的類型定義}

ADTQueue58隊(duì)列的基本操作：

InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)QueueTravers(Q,visit())59InitQueue(&Q)

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

DestroyQueue(&Q)

初始條件：隊(duì)列Q已存在。

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

60QueueEmpty(Q)

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

操作結(jié)果:若Q為空隊(duì)列,則返回TRUE，

否則返回FALSE。QueueLength(Q)

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

操作結(jié)果:返回Q的元素個(gè)數(shù)，即隊(duì)列

的長(zhǎng)度。61

GetHead(Q,&e)

初始條件：Q為非空隊(duì)列。

操作結(jié)果：用e返回Q的隊(duì)頭元素。a1a2an……62

ClearQueue(&Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：將Q清為空隊(duì)列。63EnQueue(&Q,e)

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

操作結(jié)果:插入元素e為Q的新的隊(duì)尾元素。a1a2ane……64

DeQueue(&Q,&e)

初始條件：Q為非空隊(duì)列。

操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返

回其值。a1a2an……653.5隊(duì)列類型的實(shí)現(xiàn)鏈隊(duì)列——鏈?zhǔn)接诚笱h(huán)隊(duì)列——順序映象66

typedef

struct

QNode{//結(jié)點(diǎn)類型

QElemTypedata;

struct

QNode*next;}QNode,*QueuePtr;鏈隊(duì)列——鏈?zhǔn)接诚?7typedef

struct{//鏈隊(duì)列類型

QueuePtrfront;//隊(duì)頭指針

QueuePtrrear;//隊(duì)尾指針}LinkQueue;a1∧anQ.frontQ.rearQ.frontQ.rear∧空隊(duì)列68

StatusInitQueue(LinkQueue&Q){//構(gòu)造一個(gè)空隊(duì)列Q

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);//存儲(chǔ)分配失敗

Q.front->next=NULL;returnOK;}69

StatusEnQueue(LinkQueue&Q,

QElemTypee){//插入元素e為Q的新的隊(duì)尾元素

p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);//存儲(chǔ)分配失敗

p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}70

StatusDeQueue(LinkQueue&Q,

QElemType&e){//若隊(duì)列不空，則刪除Q的隊(duì)頭元素，//用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;}71循環(huán)隊(duì)列——順序映象初始化建空隊(duì)列時(shí)，令front=rear=0，每當(dāng)插入一個(gè)新的隊(duì)尾元素后，尾指針增1；每當(dāng)刪除一個(gè)隊(duì)頭元素之后，頭指針front增1。因此，在非空隊(duì)列中，頭指針始終指向隊(duì)頭元素，而尾指針指向隊(duì)尾元素的"下一個(gè)"位置。如下圖所示。72實(shí)現(xiàn)：用一維數(shù)組實(shí)現(xiàn)sq[M]123450空隊(duì)列rear=0front=0J1J2J3rearrear123450J4,J5,J6入隊(duì)J4J5J6frontrearrear123450frontJ1,J1,J3入隊(duì)rear123450J1,J2,J3出隊(duì)J1J2J3frontfrontfront存在問題：當(dāng)front=0,rear=M時(shí)再有元素入隊(duì)發(fā)生溢出——真溢出當(dāng)front≠0,rear=M時(shí)再有元素入隊(duì)發(fā)生溢出——假溢出rear73解決方案隊(duì)首固定，每次出隊(duì)剩余元素向下移動(dòng)——浪費(fèi)時(shí)間循環(huán)隊(duì)列基本思想：把隊(duì)列設(shè)想成環(huán)形，讓sq[0]接在sq[M-1]之后，若rear+1==M,則令rear=0;實(shí)現(xiàn)：利用“模”運(yùn)算入隊(duì)：base[rear]=x;rear=(rear+1)%M;出隊(duì)：x=base[front];front=(front+1)%M;隊(duì)滿、隊(duì)空判定條件74012345rearfrontJ5J6J7012345rearfrontJ4J9J8J4,J5,J6出隊(duì)J7,J8,J9入隊(duì)隊(duì)空：front==rear隊(duì)滿：front==rear解決方案：1.另外設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)空、隊(duì)滿2.少用一個(gè)元素空間：隊(duì)空：front==rear隊(duì)滿：(rear+1)%M==front3.使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)J5J6012345rearfront初始狀態(tài)J475循環(huán)隊(duì)列－隊(duì)列的順序表示和實(shí)現(xiàn)

#defineMAXQSIZE100//最大隊(duì)列長(zhǎng)度

typedef

struct{

QElemType*base;//動(dòng)態(tài)分配存儲(chǔ)空間

intfront;//頭指針，若隊(duì)列不空，

//指向隊(duì)列頭元素

intrear;//尾指針，若隊(duì)列不空，指向

//隊(duì)列尾元素的下一個(gè)位置}SqQueue;76

StatusInitQueue(SqQueue&Q){//構(gòu)造一個(gè)空隊(duì)列QQ.base=(QElemType*)malloc

(MAXQSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);//存儲(chǔ)分配失敗

Q.front=Q.rear=0;returnOK;}第二種解決方案，占用一個(gè)元素空間77StatusEnQueue(SqQueue&Q,QElemTypee){//插入元素e為Q的新的隊(duì)尾元素

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

returnERROR;//隊(duì)列滿

Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}第二種解決方案，占用一個(gè)元素空間78

StatusDeQueue(SqQueue&Q,QElemType&e){//若隊(duì)列不空，則刪除Q的隊(duì)頭元素，

//用e返回其值，并返回OK;否則返回//ERRORif(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}第二種解決方案，占用一個(gè)元素空間79

#defineMAXQSIZE100//最大隊(duì)列長(zhǎng)度

typedef

struct{

QElemType*base;//動(dòng)態(tài)分配存儲(chǔ)空間

intfront;//頭指針，若隊(duì)列不空，

//指向隊(duì)列頭元素

intrear;//尾指針，若隊(duì)列不空，指向

//隊(duì)列尾元素的下一個(gè)位置}SqQueue;循環(huán)隊(duì)列——順序映象第一種解決方案：設(shè)標(biāo)志

int

emptyflag;//隊(duì)列空的標(biāo)志，空為180

StatusInitQueue(SqQueue&Q){//構(gòu)造一個(gè)空