第3章棧和隊(duì)列學(xué)習(xí)要點(diǎn)掌握棧和隊(duì)列這兩種抽象數(shù)據(jù)類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問題中正確選用它們。熟練掌握棧類型的兩種實(shí)現(xiàn)方法。熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法。第3章棧和隊(duì)列

棧和隊(duì)列是在程序設(shè)計中被廣泛使用的兩種線性數(shù)據(jù)結(jié)構(gòu)，它們的特點(diǎn)在于基本操作的特殊性，棧必須按"后進(jìn)先出"的規(guī)則進(jìn)行操作，而隊(duì)列必須按"先進(jìn)先出"的規(guī)則進(jìn)行操作。和線性表相比，它們的插入和刪除操作受更多的約束和限定，故又稱為限定性的線性表結(jié)構(gòu)。3.1棧3.2隊(duì)列3.1棧3.1.1棧的定義棧是一種特殊的線性表。其特殊性在于限定插入和刪除數(shù)據(jù)元素的操作只能在線性表的一端進(jìn)行。進(jìn)行插入和刪除的一端被稱為棧頂(top)，并用一個“棧頂指針”指示；不允許插入和刪除的另一端稱作棧底(bottom)。我們經(jīng)常將棧用下圖3-1的形式描述：圖3-1例：對于一個棧，給出輸入項(xiàng)A、B、C，如果輸入項(xiàng)序列由ABC組成，試給出所有可能的輸出序列。A進(jìn)A出B進(jìn)B出C進(jìn)C出ABCA進(jìn)A出B進(jìn)C進(jìn)C出B出ACBA進(jìn)B進(jìn)B出A出C進(jìn)C出BACA進(jìn)B進(jìn)B出C進(jìn)C出A出BCAA進(jìn)B進(jìn)C進(jìn)C出B出A出CBA不可能產(chǎn)生輸出序列CAB判定規(guī)則：如果輸入序列為……ai……aj……ak，則不可能的輸出序列為……ak……ai……aj例子：輸入序列為123456，則能否得到435612和135426

結(jié)論：棧的修改是按后進(jìn)先出（LastInFirstOut）的原則進(jìn)行的，因此棧又稱為后進(jìn)先出線性表（簡稱LIFO結(jié)構(gòu)）。

棧的抽象數(shù)據(jù)類型的定義，請參考教材的第45頁。3.1.2棧的順序存儲(順序棧）棧的順序存儲結(jié)構(gòu)是用一組連續(xù)的存儲單元依次存放棧中的每個數(shù)據(jù)元素，并用起始端作為棧底。其結(jié)構(gòu)定義：

typedefstruct{

ElemType*base;//存儲空間基址

inttop;

//棧頂指針

intstacksize;

//允許的最大存儲空間以元素為單位

}Stack;

基本操作接口(函數(shù)聲明)：voidInitStack(Stack&S，intmaxsize);//構(gòu)造一個最大存儲容量為maxsize的空棧S。voidDestroyStack(Stack&S);//銷毀棧S，S不再存在。voidClearStack(Stack&S);//將S置為空棧。boolStackEmpty(StackS);//若棧S為空棧，則返回TRUE，否則返回FALSE。

intStackLength(StackS);//返回S的元素個數(shù)，即棧的長度。boolGetTop(StackS,ElemType&e);//若棧不空，則用e返回S的棧頂元素，并返回TRUE；否則返回FALSE。boolPush(Stack&S,ElemTypee);//若棧的存儲空間不滿，則插入元素e為新的棧頂元素，并返回TRUE；//否則返回FALSE。

boolPop(Stack&S,ElemType&e);//若棧不空，則刪除S的棧頂元素，用e返回其值，并返回TRUE；否則返回FALSE。

voidStackTraverse(StackS,void(*visit(ElemType))//依次對S的每個元素調(diào)用函數(shù)visit()，一旦visit()失敗，則操作失敗?；静僮魉惴ǎ?.初始化棧SvoidInitStack(Stack&S，intmaxsize)

{

//構(gòu)造一個最大存儲容量為maxsize的空棧S

if(maxsize==0)

maxsize=MAXLISTSIZE;

S.base=newElemType[maxsize];

if(!S.base)exit(1);

//存儲分配失敗

S.stacksize=maxsize;

S.top=0;

//空棧中元素個數(shù)為0

}2.讀取棧頂元素boolGetTop(StackS,ElemType&e)

{

//若棧不空，則用e返回S的棧頂元素，并返回TRUE；否則返回FALSE

if(S.top==0)returnFALSE;

e=*(S.base+S.top-1);//返回非空棧中棧頂元素

returnTRUE;

}3.入棧boolPush(Stack&S,ElemTypee)

{

//若棧的存儲空間不滿，則插入元素e為新的棧頂元素，并返回TRUE；否則返回FALSE

if(S.top==S.stacksize)

//棧已滿，無法進(jìn)行插入

returnFALSE;*(S.base+S.top)=e;

//插入新的元素

++S.top;

//棧頂指針后移

returnTRUE;

}5.出棧

boolPop(Stack&S,ElemType&e)

{

//若棧不空，則刪除S的棧頂元素，用e返回其值，并返回TRUE；否則返回FALSE

if(S.top==0)returnFALSE;

e=*(S.base+S.top-1);//返回非空棧中棧頂元素

--S.top;

//棧頂指針前移

returnTRUE;

}

結(jié)論：由于棧的插入和刪除操作具有它的特殊性，所以用順序存儲結(jié)構(gòu)表示的棧并不存在插入刪除數(shù)據(jù)元素時需要移動的問題，但棧容量難以擴(kuò)充的弱點(diǎn)仍就沒有擺脫。3.1.3棧的鏈?zhǔn)酱鎯θ羰菞Ｖ性氐臄?shù)目變化范圍較大或不清楚棧元素的數(shù)目，就應(yīng)該考慮使用鏈?zhǔn)酱鎯Y(jié)構(gòu)。人們將用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示的棧稱作“鏈?！?。鏈棧通常用一個無頭結(jié)點(diǎn)的單鏈表表示。如圖3-3所示。由于棧的插入刪除操作只能在一端進(jìn)行，而對于單鏈表來說，在首端插入刪除結(jié)點(diǎn)要比尾端相對地容易一些，所以，我們將單鏈表的首端作為棧頂端，即將單鏈表的頭指針作為棧頂指針。^top圖3-3datanext

棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)（鏈棧）在C語言中可用下列類型定義實(shí)現(xiàn)：鏈棧的定義更簡單，結(jié)點(diǎn)結(jié)構(gòu)和單鏈表中的結(jié)點(diǎn)結(jié)構(gòu)相同，無須重復(fù)定義。由于棧只在棧頂作插入和刪除操作，因此鏈棧中不需要頭結(jié)點(diǎn)。

typedefstruct{SLinktop;//棧頂指針intlength;//棧中元素個數(shù)}Stack;下面我們將給出鏈棧各項(xiàng)基本操作的算法。1.初始化棧SvoidInitStack(Stack&S)

{

//構(gòu)造一個空棧S

S.top=NULL;//設(shè)棧頂指針的初值為"空"

S.length=0;

//空棧中元素個數(shù)為0

}//InitStack2.入棧voidPush(Stack&S,ElemTypee)

{

//在棧頂之上插入元素e為新的棧頂元素

p=newLNode;

//建新的結(jié)點(diǎn)

if(!p)exit(1);

//存儲分配失敗

p->data=e;

p->next=S.top;

//鏈接到原來的棧頂

S.top=p;

//移動棧頂指針

++S.length;

//棧的長度增1

}//Push3.出棧boolPop(Stack&S,SElemType&e)

{

//若棧不空，則刪除S的棧頂元素，用e返回其值，

//并返回TRUE；否則返回FALSE

if(!S.top)

returnFALSE;

else

{e=S.top->data;

//返回棧頂元素

q=S.top;

S.top=S.top->next;

//修改棧頂指針

--S.length;

//棧的長度減1

deleteq;

//釋放被刪除的結(jié)點(diǎn)空間

returnTRUE;

}

}//Pop3.1.4棧的應(yīng)用舉例

【舉例1】將從鍵盤輸入的字符序列逆置輸出比如，從鍵盤上輸入：tsetasisihT；算法將輸出：Thisisatest

下面我們給出解決這個問題的完整算法。

typedefcharElemType;voidReverseRead(){STACKS;//定義一個棧結(jié)構(gòu)Scharch;InitStack(S);//初始化棧while((ch=getchar())!=’\n’)//從鍵盤輸入字符，直到輸入換行符為止

Push(S,ch);//將輸入的每個字符入棧while(!StackEmpty(S)){//依次退棧并輸出退出的字符

Pop(S,ch);putchar(ch);}putchar(‘\n’);}【舉例2】十進(jìn)制數(shù)值轉(zhuǎn)換成二進(jìn)制使用展轉(zhuǎn)相除法將一個十進(jìn)制數(shù)值轉(zhuǎn)換成二進(jìn)制數(shù)值。即用該十進(jìn)制數(shù)值除以2，并保留其余數(shù)；重復(fù)此操作，直到該十進(jìn)制數(shù)值為0為止。最后將所有的余數(shù)反向輸出就是所對應(yīng)的二進(jìn)制數(shù)值。比如：(692)10=(1010110100)2，其展轉(zhuǎn)相除的過程如圖3-4所示：圖3-4下面給出解決這個問題的完整算法。voidconversion(){STACKS;//定義棧結(jié)構(gòu)SInitStack(S);//初始化棧Sscanf(“%d”,data);//輸入十進(jìn)制正整數(shù)while(data){Push(S,data%2);//余數(shù)入棧

data=data/2;//被除數(shù)data整除以2，得到新的被除數(shù)}while(!StackEmpty(S)){//依次從棧中彈出每一個余數(shù)，并輸出之

Pop(S,data);printf(“%d”,data);}}【舉例3】檢驗(yàn)表達(dá)式中的括號匹配情況假設(shè)在一個算術(shù)表達(dá)式中，可以包含三種括號：圓括號“（”和“）”，方括號“[”和“]”和花括號“{”和“}”，并且這三種括號可以按任意的次序嵌套使用。比如，...[...{...}...[...]...]...[...]...(...)..。現(xiàn)在需要設(shè)計一個算法，用來檢驗(yàn)在輸入的算術(shù)表達(dá)式中所使用括號的合法性。算術(shù)表達(dá)式中各種括號的使用規(guī)則為：出現(xiàn)左括號，必有相應(yīng)的右括號與之匹配，并且每對括號之間可以嵌套，但不能出現(xiàn)交叉情況。我們可以利用一個棧結(jié)構(gòu)保存每個出現(xiàn)的左括號，當(dāng)遇到右括號時，從棧中彈出左括號，檢驗(yàn)匹配情況。在檢驗(yàn)過程中，若遇到以下幾種情況之一，就可以得出括號不匹配的結(jié)論。

（1）當(dāng)遇到某一個右括號時，棧已空，說明到目前為止，右括號多于左括號；（2）從棧中彈出的左括號與當(dāng)前檢驗(yàn)的右括號類型不同，說明出現(xiàn)了括號交叉情況；（3）算術(shù)表達(dá)式輸入完畢，但棧中還有沒有匹配的左括號，說明左括號多于右括號。下面是解決這個問題的完整算法。

typedefcharElemType;boolCheckBracket(){STACKS;//定義棧結(jié)構(gòu)Scharch,e;InitStack(S);//初始化棧Swhile((ch=getchar())!=’\n’){//以字符序列的形式輸入表達(dá)式

switch(ch){case(ch==‘(’||ch==‘[’||ch==‘{’):Push(S,ch);break;//遇左括號入棧

//在遇到右括號時，分別檢測匹配情況case(ch==‘)’):if(StackEmpty(S))retrunFALSE;else{Pop(S,e);if(e!=‘(’)returnFALSE;}break;case(ch==‘]’):if(StackEmpty(S))retrunFALSE;else{Pop(S,e);if(e!=‘[’)returnFALSE;}break;case(ch==‘}’):if(StackEmpty(S))retrunFALSE;else{Pop(S,e);if(e!=‘{’)returnFALSE;}break;default:break;}}if(StackEmpty(S))returnTRUE;elsereturnFALSE;}【舉例4】表達(dá)式求值問題任何一個表達(dá)式都是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成，其中，操作數(shù)可以是常數(shù)也可以是被說明為變量或常量的標(biāo)識符；運(yùn)算符可以分為算術(shù)運(yùn)算符、關(guān)系運(yùn)算符和邏輯運(yùn)算符等三類；基本界限符有左右括弧和表達(dá)式結(jié)束符等。為了敘述簡潔，在此僅限于討論只含二元運(yùn)算符的算術(shù)表達(dá)式。由于算術(shù)運(yùn)算的規(guī)則是：先乘除后加減、先左后右和先括弧內(nèi)后括弧外，則對表達(dá)式進(jìn)行運(yùn)算不能按其中運(yùn)算符出現(xiàn)的先后次序進(jìn)行?！九e例4】表達(dá)式求值問題在計算機(jī)中，對這種二元表達(dá)式可以有三種不同的標(biāo)識方法。假設(shè)Exp=S1+OP+S2則稱OP+S1+S2為表達(dá)式的前綴表示法（簡稱前綴式）稱S1+OP+S2為表達(dá)式的中綴表示法（簡稱中綴式）稱S1+S2+OP為表達(dá)式的后綴表示法（簡稱后綴式）

可見，它以運(yùn)算符所在不同位置命名的。

【舉例4】表達(dá)式求值問題在計算機(jī)中，對這種二元表達(dá)式可以有三種不同的標(biāo)識方法。假設(shè)Exp=S1+OP+S2則稱OP+S1+S2為表達(dá)式的前綴表示法（簡稱前綴式）稱S1+OP+S2為表達(dá)式的中綴表示法（簡稱中綴式）稱S1+S2+OP為表達(dá)式的后綴表示法（簡稱后綴式）

可見，它以運(yùn)算符所在不同位置命名的。

【舉例4】表達(dá)式求值問題例如：若Exp=a×b＋（c－d/e）×f

則它的

前綴式為：＋×ab×－c/def

中綴式為：a×b＋c－d/e×f

后綴式為：ab×cde/－f×＋【舉例4】表達(dá)式求值問題綜合比較它們之間的關(guān)系可得下列結(jié)論：

1．三式中的“操作數(shù)之間的相對次序相同”；

2．三式中的“運(yùn)算符之間的的相對次序不同”；

3．中綴式丟失了括弧信息，致使運(yùn)算的次序不確定；

4．前綴式的運(yùn)算規(guī)則為：連續(xù)出現(xiàn)的兩個操作數(shù)和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一個最小表達(dá)式；

5．后綴式的運(yùn)算規(guī)則為：·運(yùn)算符在式中出現(xiàn)的順序恰為表達(dá)式的運(yùn)算順序；·每個運(yùn)算符和在它之前出現(xiàn)且緊靠它的兩個操作數(shù)構(gòu)成一個最小表達(dá)式；【舉例4】表達(dá)式求值問題以下就分“如何按后綴式進(jìn)行運(yùn)算”和“如何將原表達(dá)式轉(zhuǎn)換成后綴式”兩個問題進(jìn)行討論。如何按后綴式進(jìn)行運(yùn)算？

可以用兩句話來歸納它的求值規(guī)則：

"先找運(yùn)算符，后找操作數(shù)。"

演示運(yùn)算過程為：對后綴式從左向右"掃描"，遇見操作數(shù)則暫時保存，遇見運(yùn)算符即可進(jìn)行運(yùn)算；此時參加運(yùn)算的兩個操作數(shù)應(yīng)該是在它之前剛剛碰到的兩個操作數(shù)，并且先出現(xiàn)的是第一操作數(shù)，后出現(xiàn)的是第二操作數(shù)。由此可見，在運(yùn)算過程中保存操作數(shù)的結(jié)構(gòu)應(yīng)該是個棧?！九e例4】表達(dá)式求值問題如何由原表達(dá)式轉(zhuǎn)換成后綴式？我們先引進(jìn)一個運(yùn)算符的“優(yōu)先數(shù)”的概念。給每個運(yùn)算符賦以一個優(yōu)先數(shù)的值，如下所列：

運(yùn)算符#(+-×/

優(yōu)先數(shù)-101122“#”為結(jié)束符。容易看出，優(yōu)先數(shù)反映了算術(shù)運(yùn)算中的優(yōu)先關(guān)系，即優(yōu)先數(shù)“高”的運(yùn)算符應(yīng)優(yōu)先于優(yōu)先數(shù)低的運(yùn)算符進(jìn)行運(yùn)算。也就是說，對原表達(dá)式中出現(xiàn)的每一個運(yùn)算符是否即刻進(jìn)行運(yùn)算取決于在它后面出現(xiàn)的運(yùn)算符，如果它的優(yōu)先數(shù)"高或等于"后面的運(yùn)算，則它的運(yùn)算先進(jìn)行，否則就得等待在它之后出現(xiàn)的所有優(yōu)先數(shù)高于它的"運(yùn)算"都完成之后再進(jìn)行。【舉例4】表達(dá)式求值問題如何由原表達(dá)式轉(zhuǎn)換成后綴式？顯然，保存運(yùn)算符的結(jié)構(gòu)應(yīng)該是個棧，從棧底到棧頂?shù)倪\(yùn)算符的優(yōu)先數(shù)是從低到高的，因此它們運(yùn)算的先后應(yīng)是從棧頂?shù)綏５椎??！九e例4】表達(dá)式求值問題如何由原表達(dá)式轉(zhuǎn)換成后綴式？演示因此，從原表達(dá)式求得后綴式的規(guī)則為：設(shè)立運(yùn)算符棧；設(shè)表達(dá)式的結(jié)束符為“#”，預(yù)設(shè)運(yùn)算符棧的棧底為“#”；若當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴式；若當(dāng)前字符為運(yùn)算符且優(yōu)先數(shù)大于棧頂運(yùn)算符，則進(jìn)棧，否則退出棧頂運(yùn)算符發(fā)送給后綴式；若當(dāng)前字符是結(jié)束符，則自棧頂至棧底依次將棧中所有運(yùn)算符發(fā)送給后綴式；【舉例4】表達(dá)式求值問題如何由原表達(dá)式轉(zhuǎn)換成后綴式？因此，從原表達(dá)式求得后綴式的規(guī)則為：6)“(”對它之前后的運(yùn)算符起隔離作用，則若當(dāng)前運(yùn)算符為“(”時進(jìn)棧；7)")"可視為自相應(yīng)左括弧開始的表達(dá)式的結(jié)束符，則從棧頂起，依次退出棧頂運(yùn)算符發(fā)送給后綴式直至棧頂字符為"("止。3.2隊(duì)列3.2.1隊(duì)列的定義隊(duì)列特殊性在于限定插入在線性表的一端進(jìn)行，刪除在線性表的另外一端進(jìn)行。如圖3-5所示：圖3-5

插入端和刪除端都是浮動的。通常我們將插入端稱為隊(duì)尾，用一個“隊(duì)尾指針”指示；而刪除端被稱為隊(duì)頭，用一個“隊(duì)頭指針”指示。結(jié)論：先進(jìn)先出（FirstInFirstOut），簡稱為FIFO線性表。舉例1：到醫(yī)院看病，首先需要到掛號處掛號，然后，按號碼順序救診。舉例2：乘坐公共汽車，應(yīng)該在車站排隊(duì)，車來后，按順序上車。舉例3：在Windows這類多任務(wù)的操作系統(tǒng)環(huán)境中，每個應(yīng)用程序響應(yīng)一系列的“消息”，像用戶點(diǎn)擊鼠標(biāo)；拖動窗口這些操作都會導(dǎo)致向應(yīng)用程序發(fā)送消息。為此，系統(tǒng)將為每個應(yīng)用程序創(chuàng)建一個隊(duì)列，用來存放發(fā)送給該應(yīng)用程序的所有消息，應(yīng)用程序的處理過程就是不斷地從隊(duì)列中讀取消息，并依次給予響應(yīng)。下面我們給出隊(duì)列結(jié)構(gòu)的九個基本操作：

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

2.DestroyQueue(&Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：隊(duì)列Q被銷毀，不再存在。

3.ClearQueue(&Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：將Q清為空隊(duì)列。

4.QueueEmpty(Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：若Q為空隊(duì)列，則返回TRUE，否則返回FALSE5.QueueLength(Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：返回Q的元素個數(shù)，即隊(duì)列的長度。

6.GetHead(Q,&e)初始條件：Q為非空隊(duì)列。操作結(jié)果：用e返回Q的隊(duì)頭元素。

7.EnQueue(&Q,e)

初始條件：隊(duì)列Q已存在。操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。8.DeQueue(&Q,&e)初始條件：Q為非空隊(duì)列。操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。9.QueueTraverse(Q,visit())初始條件：隊(duì)列Q已存在且非空，visit()為元素的訪問函數(shù)。操作結(jié)果：依次對Q的每個元素調(diào)用函數(shù)visit()，一旦visit()失敗則操作失敗。

3.2.2隊(duì)列的鏈?zhǔn)酱鎯υ谟面準(zhǔn)酱鎯Y(jié)構(gòu)表示隊(duì)列時，需要設(shè)置隊(duì)頭指針和隊(duì)尾指針，以便指示隊(duì)頭結(jié)點(diǎn)和隊(duì)尾結(jié)點(diǎn)。^frontrear圖3-14頭結(jié)點(diǎn)下面是在C語言中，實(shí)現(xiàn)隊(duì)列鏈?zhǔn)酱鎯Y(jié)構(gòu)的類型定義：typedefSLinkQueuePtr;//鏈隊(duì)列的結(jié)點(diǎn)結(jié)構(gòu)和單鏈表相同

typedefstruct{QueuePtrfront;//隊(duì)列的頭指針QueuePtrrear;//隊(duì)列的尾指針intlength;//隊(duì)列元素個數(shù)}Queue;//鏈隊(duì)列下面我們給出鏈?zhǔn)疥?duì)列的基本操作算法。（1）初始化隊(duì)列QvoidInitQueue(Queue&Q)

{

//構(gòu)造一個空隊(duì)列Q

Q.front=Q.rear=newLNode;

if(!Q.front)exit(1);

//存儲分配失敗

Q.front->next=NULL;

Q.length=0;

}（2）入隊(duì)voidEnQueue(Queue&Q,ElemTypee)

{

//在當(dāng)前隊(duì)列的尾元素之后，插入元素e為新的隊(duì)列尾元素

s=newLNode;

if(!s)exit(1);

//存儲分配失敗

s->data=e;

s->next=NULL;

Q.rear->next=s;

//修改尾結(jié)點(diǎn)的指針

Q.rear=s;

//移動隊(duì)尾指針

++Q.length;

//隊(duì)列長度增1

}（3）出隊(duì)boolDeQueue(Queue&Q,ElemType&e)

{

//若隊(duì)列不空，則刪除當(dāng)前隊(duì)列Q中的頭元素，用e返回其值，并返回TRUE；否則返回FALSE

if(Q.front==Q.rear)//鏈隊(duì)列中只有一個頭結(jié)點(diǎn)

returnFALSE;

p=Q.front->next;

e=p->data;

//返回被刪元素

Q.front->next=p->next;

//修改頭結(jié)點(diǎn)指針

if(Q.rear==p)Q.rear=Q.front;

deletep;

//釋放被刪結(jié)點(diǎn)

returnTRUE;

}//DeQueue

3.2.3隊(duì)列的順序存儲（循環(huán)隊(duì)列）

和順序棧相類似，在利用順序分配存儲結(jié)構(gòu)實(shí)現(xiàn)隊(duì)列時，除了用一維數(shù)組描述隊(duì)列中數(shù)據(jù)元素的存儲區(qū)域之外，尚需設(shè)立兩個指針front和rear分別指示“隊(duì)頭”和“隊(duì)尾”的位置。為了敘述方便，在此約定：初始化建空隊(duì)列時，令front=rear=0，每當(dāng)插入一個新的隊(duì)尾元素后，尾指針rear增1；每當(dāng)刪除一個隊(duì)頭元素之后，頭指針front增1。因此，在非空隊(duì)列中，頭指針始終指向隊(duì)頭元素，而尾指針指向隊(duì)尾元素的"下一個"位置。如下圖所示。3.2.3隊(duì)列的順序存儲（循環(huán)隊(duì)列）

假設(shè)在這之后又有兩個元素f和g相繼入隊(duì)列，而隊(duì)列中的元素b和c又相繼出隊(duì)列。則隊(duì)頭指針指向元素d，隊(duì)尾指針則指到數(shù)組“之外”的位置上去了，致使下一個入隊(duì)操作無法進(jìn)行(請注意此時隊(duì)列空間并未滿)。為此，設(shè)想這個數(shù)組的存儲空間是個“環(huán)”，認(rèn)定“7”的下一個位置是“0”。如下圖所示。我們將這種形式表示的隊(duì)列稱之為循環(huán)隊(duì)列。gfed76543210rearfront圖3-11

假設(shè)為隊(duì)列開辟的數(shù)組單元數(shù)目為MAX_QUEUE，在C語言中，它的下標(biāo)在0~MAX_QUEUE-1之間，若增加隊(duì)頭或隊(duì)尾指針，可以利用取模運(yùn)算（一個整數(shù)數(shù)值整除以另一個整數(shù)數(shù)值的余數(shù)）實(shí)現(xiàn)。如下所示：

front=(front+1)%MAX_QUEUE；

rear=(rear+1)%MAX_QUEUE；當(dāng)front或rear為MAXQUEUE-1時，上述兩個公式計算的結(jié)果就為0。這樣，就使得指針自動由后面轉(zhuǎn)到前面，形成循環(huán)的效果。隊(duì)空和隊(duì)滿的標(biāo)志問題：隊(duì)列變?yōu)榭?，?duì)頭和隊(duì)尾指針相等。reara7a876543210front76543210rearfront(a)(b)圖3-12隊(duì)列變?yōu)闈M，隊(duì)頭和隊(duì)尾指針也相等。frontreara6a5a4a3a1a2765432104reara6a5a4a3a1a2a8a77653210front(a)(b)圖3-13

解決方法：一是為隊(duì)列另設(shè)一個標(biāo)志，用來區(qū)分隊(duì)列是“空”還是“滿”；二是當(dāng)數(shù)組只剩下一個單元時就認(rèn)為隊(duì)滿，此時，隊(duì)尾指針只差一步追上隊(duì)頭指針，即：(rear+1)%MAX_QUEUE==front。循環(huán)隊(duì)列的結(jié)構(gòu)定義如下：

#defineMAXLISTSIZE100//循環(huán)隊(duì)列的最大容量typedefstruct{

ElemType*elem;

//存儲空間基址

intrear;

//隊(duì)尾指針

intfront;

//隊(duì)頭指針

intqueuesize;

//允許的最大存儲空間，以元素為單位

}Queue;

類似于順序棧和鏈棧，除了循環(huán)隊(duì)列的初始化需要添加一個"最大容量"的參數(shù)之外，循環(huán)隊(duì)列和鏈隊(duì)列的基本操作接口基本相同。各項(xiàng)基本操作算法。（1）初始化隊(duì)列QvoidInitQueue(Queue&Q，intmaxsize)

{

//構(gòu)造一個最大存儲空間為maxsize的空隊(duì)列Q

if(maxsize==0)

maxsize=MAXLISTSIZE;

Q.elem=newElemType[maxsize];//為循環(huán)隊(duì)列分配存儲空間

if(!Q.elem)exit(1);

//存儲分配失敗

Q.queuesize=maxsize;

Q.front=Q.rear=0;

}//InitQueue（2）入隊(duì)boolEnQueue(Queue&Q,ElemTypee)

{

//若當(dāng)前隊(duì)列不滿，這在當(dāng)前隊(duì)列的尾元素之后，插入元素e為新的隊(duì)列尾元素,并返回TRUE,否則返回FALSE

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

returnFALSE;

Q.elem[Q.rear]=e;

Q.rear=(Q.rear+1)%Q.queuesize;

returnTRUE;

}（3）出隊(duì)boolDeQueue(Queue&Q,ElemType&e)

{

//若隊(duì)列不空，則刪除當(dāng)前隊(duì)列Q中的頭元素，用e返回其值

//并返回TRUE；否則返回FALSE

if(Q.front==Q.rear)

returnFALSE;

e=Q.elem[Q.front];

Q.front=(Q.front+1)%Q.queuesize;

returnTRUE;

}（4）隊(duì)列的長度intQueueLength(QueueQ)

{

//返回隊(duì)列Q中元素個數(shù)，即隊(duì)列的長度

return((Q.rear-Q.front+Q.queuesize)%Q.queuesize);

}4．隊(duì)列的應(yīng)用舉例【舉例1】汽車加油站。隨著城市里汽車數(shù)量的急速增長，汽車加油站也漸漸多了起來。通常汽車加油站的結(jié)構(gòu)基本上是：入口和出口為單行道，加油車道可能有若干條。每輛車加油都要經(jīng)過三段路程，第一段是在入口處排隊(duì)等候進(jìn)入加油車道；第二段是在加油車道排隊(duì)等候加油；第三段是進(jìn)入出口處排隊(duì)等候離開。實(shí)際上，這三段都是隊(duì)列結(jié)構(gòu)。若用算法模擬這個過程，就需要設(shè)置加油車道數(shù)加2個隊(duì)列。【舉例2】模擬打印機(jī)緩沖區(qū)。在主機(jī)將數(shù)據(jù)輸出到打印機(jī)時，會出現(xiàn)主機(jī)速度與打印機(jī)的打印速度不匹配的問題。這時主機(jī)就要停下來等待打印機(jī)。顯然，這樣會降低主機(jī)的使用效率。為此人們設(shè)想了一種辦法：為打印機(jī)設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，當(dāng)主機(jī)需要打印數(shù)據(jù)時，先將數(shù)據(jù)依次寫入這個緩沖區(qū)，寫滿后主機(jī)轉(zhuǎn)去做其他的事情，而打印機(jī)就從緩沖區(qū)中按照先進(jìn)先出的原則依次讀取數(shù)據(jù)并打印，這樣做即保證了打印數(shù)據(jù)的正確性，又提高了主機(jī)的使用效率。由此可見，打印機(jī)緩沖區(qū)實(shí)際上就是一個隊(duì)列結(jié)構(gòu)?！九e例3】CPU分時系統(tǒng)在一個帶有多個終端的計算機(jī)系統(tǒng)中，同時有多個用戶需要使用CPU運(yùn)行各自的應(yīng)用程序，它們分別通過各自的終端向操作系統(tǒng)提出使用CPU的請求，操作系統(tǒng)通常按照每個請求在時間上的先后順序，將它們排成一個隊(duì)列，每次把CPU分配給當(dāng)前隊(duì)首的請求用戶，即將該用戶的應(yīng)用程序投入運(yùn)行，當(dāng)該程序運(yùn)行完畢或用完規(guī)定的時間片后，操作系統(tǒng)再將CPU分配給新的隊(duì)首請求用戶，這樣即可以滿足每個用戶的請求，又可以使CPU正常工作?！九e例4】編寫一個打印二項(xiàng)式系數(shù)表（即楊輝三角）的算法。系數(shù)表中的第k行有k+1個數(shù)，除了第一個和最后一個數(shù)為1之外，其余的數(shù)則為上一行中位其左、右的兩數(shù)之和。

這個問題的程序可以有很多種寫法，一種最直接的想法是利用兩個數(shù)組，其中一個存放已經(jīng)計算得到的第k行的值，然后輸出第k行的值同