第4章 棧和隊列

1數據結構及應用算法教程(修訂版)配套課件2第4章棧和隊列

棧和隊列是對線性表的某些操作加以限定而派生出的結構。它們的操作本身并不難掌握，難點是理解棧和隊列的應用思想、掌握其算法的設計技巧。講授本章課程大約需6課時。

3

通常稱，棧和隊列是限定插入和刪除只能在表的“端點”進行的線性表。

線性表棧隊列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棧和隊列是兩種常用的數據類型43.1棧3.2棧的應用舉例3.3隊列3.4隊列應用舉例53.1棧一、棧的結構特點和操作二、棧的表示和操作的實現6一、棧的結構特點和操作7棧(Stack)的定義a2a1a4a3棧底棧頂

棧(stack)是限定只能在表的一端進行插入和刪除的線性表。在棧中,

允許插入和刪除的一端稱為“棧頂”(top),不允許插入和刪除的一端稱為“棧底”(bottom)。8InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S)棧的基本操作:(9個基本操作）

比一般線性表少了三種操作求前驅，求后繼，定位(LocateElem)9

InitStack(&S)(初始化)

操作結果：構造一個空棧S。

DestroyStack(&S)

初始條件：棧S已存在。

操作結果：棧S被銷毀。10

StackEmpty(S)（判空）

初始條件：棧S已存在

操作結果：若棧S為空棧，

則返回TRUE，

否則FALSE。11

StackLength(S)（棧長）

初始條件：棧S已存在。

操作結果：返回S的元素個數，

即棧的長度。12

GetTop(S,&e)（取棧頂元素）

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

操作結果：用e返回S的棧頂元素。a1a2an……13

ClearStack(&S)（清空）

初始條件：棧S已存在。

操作結果：將S清為空棧。

14

Push(&S,e)（入棧-插入）

初始條件：棧S已存在。

操作結果：插入元素e為

新的棧頂元素。

a1a2ane……15

Pop(&S,&e)（出棧-刪除）

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

操作結果：刪除S的棧頂元素，

并用e返回其值。a1a2anan-1

……16

順序棧

鏈棧二、棧的表示和操作的實現17

順序棧

類似于線性表的順序表示法，指向表尾的指針可以作為棧頂指針。棧頂指針top---不是地址，而是數組的下標，其值是棧頂元素的下標。18//-----棧的順序存儲表示

-----

#defineSTACK_INIT_SIZE100;

#defineSTACKINCREMENT10;

typedefstruct{

SElemType

*elem;

inttop;----棧頂下標,順序表是length

intstacksize;

intincrement;

}

SqStack;補充：length=top+1；19

void

InitStack_Sq(SqStack&S){

//構造一個空棧S

S.elem=newSElemType[maxsize];//表示棧已經存在

S.top=-1;//棧為空

S.stacksize=maxsize;S.incrementsize=incresize;

//對棧的其他成員附初值}20void

Push_Sq(SqStack&S,SElemTypee){

if

(S.top==S.stacksize-1)

incrementStacksize(S);//如果順序棧的空間已滿，應為棧擴容

S.elem[++S.top]=e;//在棧頂插入數據元素}S.elem[++S.top]=e;可以改為如下兩句：S.top++;S.elem[S.top]=e;總結：先改變top（top+1），再賦值。21bool

Pop_Sq(SqStack&S,SElemType&e){//若棧不空，則刪除S的棧頂元素，

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

//否則返回FALSE。

if

(S.top

==

-1)return

FALSE;e=S.elem[S.top-

-];

return

TRUE;}e=S.elem[S.top-

-];此語句可以改為：e=S.elem[S.top];S.top-

-；總結：先賦值再改變top（top-1）22棧頂指針∧a1an注意:鏈棧中指針的方向an-1

鏈棧top233.2棧的應用舉例

棧在算法設計中占有重要的地位，運用的技巧也性也較高，本節(jié)安排五個例子來討論棧的使用。24例一數制轉換例二括號匹配的檢驗例三背包求解例四表達式求值例五遞歸函數的實現25

例一、數制轉換

算法基于數制轉換公式：

N=(Ndivd)×d+Nmodd

26

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

其運算過程如下：

NNdiv8Nmod8

13481684

168210

2125

202計算順序輸出順序27void

conversion()

{InitStack(S);

cin>>N;

while

(N)

{

Push(S,N%8);N=N/8;

}

while

(!StackEmpty(S)){

Pop(S,e);

cout<<e;

}}

//conversion28例二、括號匹配的檢驗假設在表達式中（［］（））或［（［］［］）］等為正確的格式，［（］）或（［（））或（（）］)均為不正確的格式。

則檢驗括號是否匹配的方法可用“期待的急迫程度”這個概念來描述。29分析可能出現的不匹配的情況:到來的右括弧并非是所“期待”的；例如：考慮下列括號序列：

[([][])]12345678到來的是“不速之客”；直到結束，也沒有到來所“期待”的括弧。30算法的設計思想：1）凡出現左括弧，則進棧；2）凡出現右括弧，首先檢查棧是否空若?？?，則表明該“右括弧”多余，否則和棧頂元素比較，若相匹配，則“左括弧出棧”

，否則表明不匹配。3）表達式檢驗結束時，若棧空，則表明表達式中匹配正確，否則表明“左括弧”有余。31boolmatching(charexp[]){

intstate=1;ch=*exp++;

while(ch!=‘#’&&state){

switchofch{

case

左括弧:{Push(S,ch);i++;break;}//左括弧進棧

case”)”:{//

匹配‘）’

if(!StackEmpty(S)&&GetTop(S)=‘(‘)Pop(S,e);

else

state=0;

break;}

case”]”:{……}//

匹配‘]’

}

ch=*exp++;

}

if(StackEmpty(S)&&state)

return

TRUE;

elsereturn

FALSE;

}32例三.背包問題:

假設有n件體積分別為w1,w2,…wn的物品和一個能裝載體積為T的背包.能否從n件物品中選擇若干件恰好裝滿背包,

即

wi1+wi2+…+wik=

T,則背包問題有解；否則無解.

以W(1,8,4,3,5,2),

T=10為例

(1,4,3,2

),

(1,4,5

),(8,2)和(3,5,2)是其解。3354381435822WT=101+4+3+2=10

利用回溯的算法思想求解背包問題

從背包中取出物品再繼續(xù)搜索的策略稱之為回溯，其規(guī)則是“后進先出”，即背包以棧的操作完成求解。34voidknapsack(intw[],intT,int

n){//T在算法中是剩余的容積，初值為背包的體積

InitStack(S);k=0;

do{

while(T>0&&k<n){

if

(T-w[k]>=0){

//第k件物品可以進棧

Push(S,k);T─

=w[k];

}k++;

}

if(T==0)StackTraverse(S);//輸出一個解

Pop(S,k);

T+=w[k];//退出棧頂物品

k++;

}while

(!StackEmpty(S)||k<n);}35

限于二元運算符的表達式定義:

表達式::=

操作數運算符操作數操作數::=

簡單變量|

表達式簡單變量::=

標識符|

無符號整數例四、表達式求值例如:exp=ab

+

(7d/e)f36

表達式的三種標識方法：設

Exp=S1OP

S2則稱OP

S1S2

為前綴表示法

S1

OP

S2

為中綴表示法

S1

S2

OP

為后綴表示法

37例如:Exp=ab

+

(cd/e)f前綴式:+

ab

c/def中綴式:ab

+

cd/ef后綴式:ab

cde/f

+結論:1）操作數之間的相對次序不變;2）運算符的相對次序不同;3）中綴式丟失了括弧信息，致使運算的次序不確定;4)前綴式的運算規(guī)則為:連續(xù)出現的兩個操作數和在它們之前且緊靠它們的運算符構成一個最小表達式;5)后綴式的運算規(guī)則為:運算符在式中出現的順序恰為表達式的運算順序;

每個運算符和在它之前出現且緊靠它的兩個操作數構成一個最小表達式。38如何從后綴式求值？例如：

abcde/f+abd/ec-d/e(c-d/e)f先找運算符，再找操作數:Exp=ab

+

(cd/e)f39后綴表達式：算法思想abcde/f+#1、遇到操作數入棧，2、遇到操作符就出棧（連續(xù)出兩個棧頂元素），進行計算，將結果壓棧3、直到表達式掃描完畢。難點：如何將中綴表達式轉換為后綴表達式（樹的知識。）40Computy(suffix[]){Stacks;i=0;InitStack(&x);while(suffix[i++]!=‘#’){ifsuffix

[i]是操作數嗎？

push(&s,suffix[i]);else{x=pop(&s,&e);y=pop(&s,&e);N=operate(x,y,suffix[i]);push(&s,N);}//else//i++;}//whileret=pop(&s,&e);return(ret);}suffix[]=abcde/f+#41ifsuffix

[i]是操作數嗎?if（‘0’<=suffix

[i]

<=‘9”）;擴展思考：如果是多位數的數字如何判斷？42N=operate(x,y,suffix[i]);//是操作符進行運算=========================operate(x,y,suffix[i]){switch(suffix[i]){case’+’:N=y+x;returnN;break;case’-’:N=y-x;returnN;break;case’*’:N=y*x;returnN;break;case’\’:N=y\x;returnN;break;default:returnERROR;}//switch}43

如何從原表達式求得后綴式？

每個運算符的運算次序要由它之后的一個運算符來定，在后綴式中，優(yōu)先數高的運算符領先于優(yōu)先數低的運算符。分析“原表達式”和“后綴式”中的運算符:原表達式:a+b

cd/e

f

后綴式:abc+de/f

44運算符優(yōu)先數表

運算符#（+–）/^優(yōu)先數-1011222345從原表達式求得后綴式的規(guī)律為：1)

設立操作符棧；2)設表達式的結束符為“#”，

予設運算符棧的棧底為“#”；3)

若當前字符是操作數，則直接發(fā)送給后綴。4)

若當前運算符的優(yōu)先數大于棧頂運算符,則進棧；5)

否則（小于等于），退出棧頂運算符發(fā)送給后綴式；6)“(”對它之前后的運算符起隔離作用，

“)”可視為自相應左括弧開始的表達式的結束符。46從原表達式求得后綴式的規(guī)律為：設立一數組放原表達式：exp[]=原表達式設立操作符棧；S

設立一個數組放后綴表達式suffix[]

2)設表達式的結束符為“#”，

予設運算符棧的棧底為“#”；//push（&s,“#”)準備工作：47從原表達式求得后綴式的規(guī)律為：3)

若當前字符是操作數，則直接發(fā)送給后綴式。if(ch)為操作數，suffix[k++]=ch;逐個讀取原表達式的字符，進行對應處理：分別考慮操作數，操作符（考慮優(yōu)先級），左括號（，右括號）的處理方法。若為操作符：48從原表達式求得后綴式的規(guī)律為：若為操作符：4)

若當前運算符的優(yōu)先數高于棧頂運算符,則進棧；5)

否則，退出棧頂運算符發(fā)送給后綴式；幾種情況：情況1：符號為+-*/:比較優(yōu)先級，確定是進棧還是給后

綴表達式情況2：(-----進棧情況3：）---）不進棧，

自棧頂至（之前的運算符出棧并發(fā)給后綴式，

）出棧6)“(”對它之前后的運算符起隔離作用，

“)”可視為自相應左括弧開始的表達式的結束符。49從原表達式求得后綴式的規(guī)律為：1)

設立操作符棧；2)設表達式的結束符為“#”，

予設運算符棧的棧底為“#”；3)

若當前字符是操作數，則直接發(fā)送給后綴式。4)

若當前運算符的優(yōu)先數高于棧頂運算符,則進棧；5)

否則，退出棧頂運算符發(fā)送給后綴式；6)“(”對它之前后的運算符起隔離作用，

“)”可視為自相應左括弧開始的表達式的結束符。50voidtransform(charsuffix[],charexp[]){InitStack(S);Push(S,#);p=exp;ch=*p;k=0；

while(!StackEmpty(S)){

if(!opmenber(ch))suffix[k++]=ch;

else

{

}

if(ch!=#){p++;ch=*p;}}//whilesuffix[k]=\0;}//transform……//如果為操作符看后面swich部分}51switch(ch)

{

case

(

:Push(S,ch);break;//左括號入棧

case

)

:

Pop(S,c);自頂到（全部出棧給后綴數組

while(c!=

()

{suffix[k++]=c;Pop(S,c)}

break;

defult:{//其他情況比較優(yōu)先級

while(Gettop(S,c)&&

(precede(c,ch)))

{suffix[k++]=c;Pop(S,c);}

if(ch!=

#)Push(S,ch);

break;

}

}//switchC為棧頂操作符，ch為當前操作符precede（c,ch）return1為ch<=cintopermanber(ch){if(‘0’<=ch<=‘9’;}return0;elsereturn1;說明：為操作數，則返回0intprecede(c,ch)c為棧頂的運算符；ch為當前的運算符當ch<=c,則返回1，反之(ch>c)返回0{Switch(ch)case+:case–:{if（

棧頂c是#或者（），return0;//ch>celse返回1;//其他情況ch<=c;}case*:case/:{if（

棧頂c是*或者/）retrun1;//ch<=celseretrun0;//ch>c}}//switch如果表達式是：234+56/2*11-8怎么處理多位數？55例五、實現遞歸

將所有的實在參數、返回地址等信息傳遞給被調用函數保存；--保護現場為被調用函數的局部變量分配存儲區(qū)；將控制轉移到被調用函數的入口。

當在一個函數的運行期間調用另一個函數時，在運行該被調用函數之前，需先完成三項任務：56保存被調函數的計算結果；釋放被調函數的數據區(qū)；（局部變量）依照被調函數保存的返回地址將控制轉移到調用函數。

從被調用函數返回調用函數之前，應該完成下列三項任務：57多個函數嵌套調用的規(guī)則是：此時的內存管理實行“棧式管理”后調用先返回！例如：voidmain(){voida(){voidb(){………

a();

b();

……}//main}//a}//bMain的數據區(qū)函數a的數據區(qū)函數b的數據區(qū)遞歸的定義：一個函數自己直接或間接調用自己。對計算機而言，某函數調用別的函數與調用自己本身，沒有不同，至于難以理解，那是人的思維而已。59

遞歸函數執(zhí)行的過程可視為同一函數進行嵌套調用，在執(zhí)行遞歸函數的過程中也需要一個“遞歸工作?！?。作用：（1）將遞歸調用的實際參數、返回地址傳遞給下一層執(zhí)行的遞歸函數；（2）保存本層的參數和局部變量，以便從下一層返回時重新使用它們。60A(n,x,y)=x+1,n=0x,n=1,y=00,n=2,y=01,n=3,y=02,n≥4,y=0A(n-1,A(n,x,y-1),x)，n≠0,y≠0Ackerman函數定義：用實例模仿編譯程序解決遞歸問題的過程（無需掌握）61A(3,2,1)=A(2,A(3,2,0),2)=A(2,1,2)A(3,2,0)=1=A(1,A(2,1,1),1)=A(1,A(1,A(2,1,0),1),1)=A(1,A(1,0,1),1)A(2,1,0)=0=A(1,A(0,A(1,0,0),0),1)=A(1,A(0,0,0),1)A(1,0,0)=x=0=A(1,1,1)A(0,0,0)=x+1=1=A(0,A(1,1,0),1)=A(0,1,1)A(1,1,0)=x=1=2A(0,1,1)=x+1=2

Ackerman函數A(3,2,1)的遞歸運行模擬321320212211210101100000111110011

遞歸過程的實現遞歸進層（i→i+1層）系統(tǒng)需要做三件事：

(1)保留本層參數與返回地址（將所有的實在參數、返回地址等信息傳遞給被調用函數保存）；

(2)給下層參數賦值（為被調用函數的局部變量分配存儲區(qū)）；

(3)將程序轉移到被調函數的入口。

而從被調用函數返回調用函數之前，遞歸退層（i←i+1層）系統(tǒng)也應完成三件工作：

(1)保存被調函數的計算結果；

(2)恢復上層參數（釋放被調函數的數據區(qū)）；(3)依照被調函數保存的返回地址，將控制轉移回調用函數。設計遞歸的條件及方法：一、將問題化為原問題的子問題的求解（砍頭去尾，中間切）假設n個規(guī)模問題，判斷：1、砍頭：取第一個元素，n-1個元素與原問題是否相似2、去尾：剩n-1個問題與原問題是否相似3、中間切：將原問題一分為2，Q1，Q2與原問題是否相似（排序大多用此）二、終止條件：設計遞歸出口，確定終止條件(能在最小值上有直接解，并作為終止條件條件，告知何時停止遞歸)例：1+2+3+…..+n條件滿足否？(1)去尾1+2+…+(n-1)(2)終止條件：n==0，return0;

或n==1，retrun1;

或n==2，retrun3;intSum（n）{if(n==1)，total=1；

elsetotal=sum（n-1）+n

returntotal；}求階乘：

n！=1*2*3*……*(n-1)*n去尾，與原問題相似終止條件：n=1時，result=1

intfunction（intn）{if（n==1）result=1；

elseresult=function（n-1）*n}Hanoi塔問題Hannoi的傳說

相傳在印度的貝納雷斯有座大寺廟，寺廟內有一塊紅木板，上面插著三根鉆石棒，在盤古開天地，世界剛創(chuàng)造不久之時，神便在其中的一根鉆石棒上放了６４枚純金的圓盤。

有一個叫婆羅門的門徒，不分日夜地向這座寺廟趕路，抵達后，就盡力將６４枚純金的圓盤移到另一根鉆石棒上。等到婆羅門完成這項工作，寺廟和婆羅門本身都崩潰了，世界在一聲霹靂中也毀滅了。不管這個傳說的可信度有多大，如果考慮一下把64片金片，由一根針上移到另一根針上，并且始終保持上小下大的順序。這需要多少次移動呢?這里需要遞歸的方法。假設有n片，移動次數是f(n).顯然f⑴=1,f⑵=3,f⑶=7，且f(k+1）=2*f(k)+1。此后不難證明f(n)=2^n-1。n=64時，

f（64）=2^64-1=18446744073709551615

假如每秒鐘一次，共需多長時間呢？一個平年365天有31536000秒，閏年366天有31622400秒，平均每年31556952秒，計算一下，18446744073709551615/31556952=584554049253.855年

這表明移完這些金片需要5845億年以上，而地球存在至今不過45億年，太陽系的預期壽命據說也就是數百億年。真的過了5845億年，不說太陽系和銀河系，至少地球上的一切生命，連同梵塔、廟宇等，都早已經灰飛煙滅。漢諾塔問題：有三根桿子A，B，C。A桿上有N個(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規(guī)則將所有圓盤移至C桿：每次只能移動一個圓盤；大盤不能疊在小盤上面。

提示：可將圓盤臨時置于B桿，也可將從A桿移出的圓盤重新移回A桿，但都必須遵循上述兩條規(guī)則。

問：如何移？最少要移動多少次？n個盤子,A->C去尾，前面n-1個盤子作為小問題，將n-1個盤子黏起來，就成了兩個盤子，如何移呢？(D1是上面的小盤（假想成n-1個黏起來的盤），D2是下面的大盤)1、D1AB2.D2A->C3D1B->Chanoi(n,A,B,C)//A-C借助B{If（n=1）{

printf（“n從A移動C”）；return1；}else{hanoi（n-1，A,C,B）

printf（n,A-C）hanoi(n-1，B,A,C)}}723.3隊列一、隊列的結構特點和操作二、隊列的表示和操作的實現73一、隊列的結構特點和操作使用場合：用于仿真，服務窗口的設置是否合理74隊列(Queue)的定義

隊列(queue)是限定只能在表的一端進行刪除，而在另一端插入的線性表。在隊列中，允許刪除的一端稱為“隊頭”(front)，允許插入的一端稱為“隊尾”(rear)。

a1a2a3a4a5隊頭隊尾75

InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)QueueTravers(Q)隊列的基本操作：76InitQueue(&Q)

操作結果：構造一個空隊列Q。

DestroyQueue(&Q)

初始條件：隊列Q已存在。

操作結果：隊列Q被銷毀，

不再存在。

77QueueEmpty(Q)

初始條件：隊列Q已存在。

操作結果：若Q為空隊列，

則返回TRUE，

否則返回FALSE。78

QueueLength(Q)

初始條件：隊列Q已存在。

操作結果：返回Q的元素個數，

即隊列的長度。79

GetHead(Q,&e)

初始條件：Q為非空隊列。

操作結果：用e返回Q的隊頭元素。a1a2an……80

ClearQueue(&Q)

初始條件：隊列Q已存在。

操作結果：將Q清為空隊列。81

EnQueue(&Q,e)

初始條件：隊列Q已存在。

操作結果：插入元素e為Q的

新的隊尾元素。a1a2ane……82

DeQueue(&Q,&e)

初始條件：Q為非空隊列。

操作結果：刪除Q的隊頭元素，

并用e返回其值。a1a2an……83

鏈隊列

循環(huán)隊列二、隊列的表示和操作的實現84

typedefstruct

QNode{//結點類型

QElemTypedata;

struct

QNode*next;

}QNode,*QueuePtr;

鏈隊列85Q.frontQ.reartypedefstruct{//鏈隊列類型

QueuePtrfront;//隊頭指針（指向頭結點）

QueuePtrrear;//隊尾指針（指向尾元素）}

LinkQueue;a1∧an…Q.frontQ.rear∧空隊列86

void

InitQueue_L(LinkQueue&Q){//構造一個空隊列Q

Q.front=Q.rear=newQNode;

Q.front->next=

NULL;}產生一個空結點，并讓front與rear都指向它。87

void

EnQueue_L(LinkQueue&Q,QElemTypee)

{//插入元素e為Q的新的隊尾元素

p=

new

QNode;p->data=e;p->next=NULL;Q.rear->next=p;

Q.rear=p;}注意：鏈的變化；rear指向尾函數。88

bool

DeQueue_L(LinkQueue&Q,QElemType&e){//若隊列不空，則刪除Q的隊頭元素，

//用e返回其值,并返回TRUE；否則返回FALSE

if(Q.front==Q.rear)returnFALSE;p=Q.front->next;e=p->data;

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

if(Q.rear==p)Q.rear=Q.front;//當原隊列只有一個元素時，

要特殊處理

。

delete

p;

returnTRUE;}注意：釋放刪除的結點；只有一元素時的特殊處理；fornt始終指向頭結點（不變）89#define

MAXQSIZE100//最大隊列長度typedefstruct{

QElemType*elem;//動態(tài)分配存儲空間

intfront;//頭指針，若隊列不空，

//指向隊列頭元素

intrear;//尾指針，若隊列不空，指向

//隊列尾元素的下一個位置

int

queuesize;

int

incrementsize;}

SqQueue;

循環(huán)隊列（順序隊列）少了隊列長度queuelength，因為通過front與rear運算可得90由于插入刪除分別在隊尾和隊頭進行。思考：能否做到，用數組表示隊列時，做到不頻繁移動元素，并保持線性的特點？解決方法：移動front或者rear就可。問題：產生假溢（假滿）解決方法：頭尾相連，讓數組形成一個環(huán)—循環(huán)數組（循環(huán)隊列）。如何實現(取模實現)：rear=(rear+1)%queuesize(queuesize是隊列/數組的最大容量)91循環(huán)隊列：保留了數組存儲的簡單，且插入刪除無須元素的移動。還有一個問題有待解決：隊列滿：front==rear;隊列空：front==rear;按照算法的特性：算法要有確定性，不能出現歧義。92如何解決：1、設置標志當入隊，使front==rear，則為滿，當出隊，使front==rear，則為空。2、犧牲一個內存單元，讓空和滿的判斷條件都唯一?？眨?/p>

front==rear滿：（rear+1）%queuesize==front;93循環(huán)隊列非循環(huán)隊列入隊rear=(rear+1)%queuesize;Rear=rear+1出隊front==(front+1)%queuesize;Front=front+1隊空rear==front；rear==front；隊滿(rear+1)%queuesize==front；rear==front；Rear+1=queuesize(rear-front+queuesize)%queuesize94abcdQ.elemQ.fronteQ.rearQ.front:

指向隊頭元素Q.rear:

指向隊尾下一元素隊列的入隊和出隊操作：95e01234567Q.frontQ.rear初態(tài)（空隊）:Q.frontQ.rear隊空:當頭尾指針重合時:隊為空9601234567acbQ.frontQ.rear隊滿狀態(tài)的約定:acbQ.rear01234567Q.rearQ.frontabcdefg假滿真滿Q.rearQ.rear隊滿時還富裕一個單元的空間以區(qū)別“隊空”和“隊滿”的條件9701234567abcQ.rearQ.frontQ.reard循環(huán)隊列（按循環(huán)機制使用順序空間）

front和rear都按逆時針操作98Q.rear=(Q.rear+1)Q.front=(Q.front+1)

通過頭尾指針的循環(huán)使用,順序空間即可當循環(huán)空間來使用，稱循環(huán)隊。循環(huán)使用指針在技術上是由取模實現的：%

MAXQSIZE;%

MAXQSIZE;99

void

InitQueue_Sq(SqQueue&Q){//構造一個空隊列Q

Q.elem=

new

QElemType

[MAXQSIZE+1];

Q.queuesize=MAXQSIZE；

Q.front=Q.rear=0;

}100void

EnQueue_Sq(SqQueue&Q,ElemTypee){

//插入元素e為Q的新的隊尾元素

if

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

incrementQueuesize(Q);

//隊列已滿需擴容

Q.elem[Q.rear]=e;

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

MAXQSIZE;}101void

DeQueue_Sq(SqQueue&Q,ElemType&e)

{

//若隊列不空，則刪除Q的隊頭元素，

//用e返回其值，并返回TRUE;否則返回FALSE

if(Q.front==Q.rear)

returnFALSE;e=Q.elem[Q.front];Q.front=(Q.front+1)%MAXQSIZE;

return

TRUE;}1023.4隊列的應用舉例利用循環(huán)隊列求二項式系數（楊輝三角）楊輝三角形特點：1、頭尾均為12、其他元素是上層相鄰元素之和。問題描述：n為第n層，輸出具有n層楊輝三角形。給第n-1層，如何產生第n層。假如知道第三層，1,3,3,1（已全部入隊），如何產生第四層的數？1、每次出隊一個元素x（三層的）2、讀取一元素y=Gethead()3、x+y入隊（第四層的元素），3、循環(huán)1-3。出隊1；Gethead（）3；1+3=4，入隊；出隊3；Gethead（）3；1+3=6，入隊；出隊3；Gethead（）1；3+1=4，入隊；在兩行之間加上輔助變量0，作為行界值（為了便于編程）013310|0146410楊三角算法：1、根據楊三角第n-1層數產生編程，m=1（當前層數）2、每次從隊列里面出隊一個元素x，讀取頭元素y3、將x+y入隊4、不斷重復2,3，直到y(tǒng)=0；（小循環(huán)）5、不斷重復1,2,3,直到m=n；（大循環(huán)）存在小問題：1、頭尾問題；2、何時小循環(huán)結束106第1行11