數(shù)據(jù)結構第3章棧和隊列課件

第3章限定性線性表—棧和隊列3.1棧3.2棧的應用舉例3.3棧與遞歸的實現(xiàn)3.4隊列第3章限定性線性表—棧和隊列3.1棧13.1棧3.1.1棧的定義棧作為一種限定性線性表，是將線性表的插入和刪除運算限制為僅在表尾進行，通常將表中允許進行插入、刪除操作的一端稱為棧頂(Top)，因此棧頂?shù)漠斍拔恢檬莿討B(tài)變化的，它由一個稱為棧頂指針的位置指示器指示。同時表的另一端被稱為棧底(Bottom)。當棧中沒有元素時稱為空棧。棧的插入操作被形象地稱為進?；蛉霔＃瑒h除操作稱為出?；蛲藯?。

3.1棧3.1.1棧的定義2設S=(a1,a2,…,an)表示棧，則a1為棧底元素，an

為棧頂元素。棧是一種后進先出（LastInFirstOut）的線性表（簡稱LIFO結構）。圖3.1棧設S=(a1,a2,…,an)表示棧，則a1為棧底元素，an3棧只能對棧頂元素進行插入和刪除操作。例：若輸入A，B，C，D，同時在插入的時候也可能進行刪除操作?？赡艿妮敵鲂蛄袨椋築，A，C，D;

C、D、A、B；D，A，C，B；C、A、D、B；D，C，A，B；C、B、D、A；B，C，A，D；A，C，B，D；棧只能對棧頂元素進行插入和刪除操作。4ADTStack{

數(shù)據(jù)元素：可以是任意類型的數(shù)據(jù)，但必須屬于同一個數(shù)據(jù)對象。數(shù)據(jù)關系：棧中數(shù)據(jù)元素之間是線性關系。基本操作：（1）InitStack(&S)

初始條件：S為未初始化的棧。操作結果：將S初始化為空棧。（2）ClearStack(&S)

初始條件：棧S已經存在。操作結果：將棧S置成空棧。ADTStack{5

（3）StackEmpty(S)

初始條件：棧S已經存在。操作結果：若S為空棧，則函數(shù)值為TRUE，否則FALSE

（4）Push(&S,e)

初始條件：棧S已經存在。操作結果：在S的頂部插入(亦稱壓入)元素e；（3）StackEmpty(S)6

（5）Pop(&S,&e)

初始條件：棧S已經存在。操作結果：刪除(亦稱彈出)棧S的頂部元素，并用e帶回該值。（6）GetTop(S,&e)

初始條件：棧S已經存在。操作結果：取棧S的頂部元素。與Pop(&S,e)不同之處在于GetTop(S,&e)不改變棧頂?shù)奈恢?。?）Pop(&S,&e)73.1.2棧的表示和實現(xiàn)1.順序棧順序棧是用順序存儲結構實現(xiàn)的棧，即利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時由于棧的操作的特殊性，還必須附設一個位置指針top（棧頂指針）來動態(tài)地指示棧頂元素在順序棧中的位置。通常以top=0表示空棧。順序棧的存儲結構可以用C語言中的一維數(shù)組來表示。棧的順序存儲結構定義如下：3.1.2棧的表示和實現(xiàn)1.順序棧8＃defineTRUE1＃defineFALSE0typedefstruct{SElemType*base;SElemType*top;intstacksize;//?？墒褂玫淖畲笕萘縸SqStack;

按初始分配量進行第一次存儲分配，base為棧底指針，始終指向棧底。top為棧頂指針，初值指向棧底，每插入一個元素，top增1；每刪除一個元素，top減1，top始終在棧頂元素的下一個位置上。

＃defineTRUE19圖3.2順序棧中的進棧和出棧43210432104321043210圖3.2順序棧中的進棧和出棧444410順序?；静僮鞯膶崿F(xiàn)如下:(1)初始化。StatusInitStack(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;returnOK;}順序?；静僮鞯膶崿F(xiàn)如下:StatusInitStac11(2)取棧頂元素StatusGetTop(SqStackS,SElemType&e){if(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}(2)取棧頂元素12(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;returnOK;}(3)入棧。13(4)出棧StatusPop(SqStack&S,SelemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}(4)出棧142.鏈棧圖3.4鏈棧示意圖鏈式棧無棧滿問題，空間可擴充插入與刪除僅在棧頂處執(zhí)行鏈式棧的棧頂在鏈頭適合于多棧操作2.鏈棧圖3.4鏈棧示意圖鏈式棧無棧滿問題，空間可152.鏈棧

圖3.4鏈棧示意圖棧的鏈式存儲結構實際上就是一個單鏈表，叫做鏈棧。插入和刪除操作只能在鏈棧的棧頂進行。

棧頂指針Top應該在鏈表的哪一頭？

鏈式棧的棧頂在鏈頭插入與刪除僅在棧頂處執(zhí)行鏈式棧無棧滿問題，空間可擴充適合于多棧操作2.鏈棧圖3.4鏈棧示意圖棧的鏈式存儲結構162.鏈棧/*

鏈棧結構

*/

typedef

struct

StackNode

{

SElemType

data;

//節(jié)點數(shù)據(jù)域

struct

StackNode

*next;//節(jié)點指針域

}StackNode,*LinkStackPtr;

//節(jié)點指針

typedef

struct

LinkStack

{

LinkStackPtr

top;

//棧頂指針

int

count;

//棧中元素個數(shù)}LinkStack;

2.鏈棧/*

鏈棧結構

*/

172.鏈棧//棧的初始化操作Status

InitStack(LinkStack

*S)

{

S->top

=

(LinkStackPtr)malloc(sizeof(StackNode));

if(!S->top)

return

ERROR;

S->top

=

NULL;

S->count

=

0;

return

OK;

}

2.鏈棧//棧的初始化操作182.鏈棧/*

把S置為空棧

*/

Status

ClearStack(LinkStack

*S)

{

LinkStackPtr

p,q;

p

=

S->top;

while(p)

{

q

=

p;

p

=

p->next;

free(q);

}

S->count=0;

return

OK;

}

2.鏈棧/*

把S置為空棧

*/

192.鏈棧/*

若棧S為空棧，則返回TRUE，否則返回FALSE

*/

Status

IsEmptyStack(LinkStack

S)

{

if

(S.count

==

0)

{

return

TRUE;

}

else

{

return

FALSE;

}

}

2.鏈棧/*

若棧S為空棧，則返回TRUE，否則返回FA202.鏈棧/*

若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR

*/

Status

GetTopElem(LinkStack

S,SElemType

*e)

{

if

(S.top

==

NULL)

{

return

ERROR;

}

else

{

*e

=

S.top->data;

}

return

OK;

}

2.鏈棧/*

若棧不空，則用e返回S的棧頂元素，并返回O212.鏈棧Status

Push(LinkStack

*S,SElemType

e)

{

LinkStackPtr

s=(LinkStackPtr)malloc(sizeof(StackNode));

if

(!s)

{

return

ERROR;

}

s->data

=

e;

s->next

=

S->top

S->top

=

s;

S->count++;

return

OK;

}

2.鏈棧Status

Push(LinkStack

*S222.鏈棧/*

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

*/

Status

Pop(LinkStack

*S,SElemType

*e)

{

LinkStackPtr

p;

if(IsEmptyStack(*S))

{

return

ERROR;

}

*e

=

S->top->data;

p

=

S->top;

S->top

=

S->top->next

free(p);

S->count--;

return

OK;

}

2.鏈棧/*

若棧不空，則刪除S的棧頂元素，用e返回其值233.2棧的應用舉例1.數(shù)制轉換假設要將十進制數(shù)N轉換為d進制數(shù)，一個簡單的轉換算法是重復下述兩步，直到N等于零：X=Nmodd(其中mod為求余運算)N=Ndivd(其中div為整除運算)3.2棧的應用舉例1.數(shù)制轉換24如(1348)10=(2504)8

NN/8N%8134816841682102125202如(1348)10=(2504)8NN/8N%8125voidconversion(){ InitStack(S); scanf(“%d”,&N); while(N) { Push(s,N%8); N=N/8; } while(!StackEmpty(s)){ Pop(S,e); printf(“%d”,e); }}voidconversion()262.括號匹配問題假設表達式中包含三種括號：圓括號、方括號和花括號，它們可互相嵌套，如([{}]([]))或({([][()])})等均為正確的格式，而{[]})}或{[()]或([]}均為不正確的格式。在檢驗算法中可設置一個空棧。讀入字符直到文件尾。如果字符是一個左括號，則直接入棧。如果字符是一個右括號，那么若棧為空，則報錯；若棧不為空，則將棧頂元素出棧。如果出棧的符號不是對應的左括號，則報錯。在文件尾，如果棧非空則報錯。2.括號匹配問題273.表達式求值

表達式求值是高級語言編譯中的一個基本問題，是棧的典型應用實例。任何一個表達式都是由操作數(shù)(operand)、運算符(operator)和界限符(delimiter)組成的。操作數(shù)既可以是常數(shù)，也可以是被說明為變量或常量的標識符；運算符可以分為算術運算符、關系運算符和邏輯運算符三類；基本界限符有左右括號和表達式結束符等。3.表達式求值表達式求值是高級語言編譯中的28[例]算術表達式5+6/2-3*4。正確理解：

5+6/2-3*4=5+3-3*4=8-3*4=8-12=-4由兩類對象構成的：（1）操作數(shù)，如2、3、4（2）運算符號，如+、-、*、/不同運算符號優(yōu)先級不一樣[例]算術表達式5+6/2-3*4。正確理解：29后綴表達式

中綴表達式：運算符號位于兩個運算數(shù)之間。如a+b*

c-

d/

e后綴表達式：運算符號位于兩個運算數(shù)之后。如abc*+

de/-〖例〗62/

3-

42*+

=?

后綴表達式求值策略：從左向右“掃描”，逐個處理運算數(shù)和運算符號。1.遇到運算數(shù)怎么辦？如何“記住”目前還不未參與運算的數(shù)？2.遇到運算符號怎么辦？對應的運算數(shù)是什么？啟示：需要有種存儲方法，能順序存儲運算數(shù)，并在需要時“倒序”輸出！后綴表達式中綴表達式：運算符號位于兩個運算數(shù)之間。如a30對象:6(運算數(shù))〖例〗62/

3-

42*+

=?

對象:2(運算數(shù))對象:/

(運算符)對象:3(運算數(shù))

對象:-

(運算符)

對象:4(運算數(shù))

對象:2(運算數(shù))

對象:*

(運算符)對象:+

(運算符)

Pop:8top62toptop2

6

/=33333-=0042top24*=8880+=88T(N)=O(N)8對象:6(運算數(shù))〖例〗62/3-4231中綴表達式求值

基本策略：將中綴表達式轉換為后綴表達式，然后求值

如何將中綴表達式轉換為后綴？觀察一個簡單例子：3+4*5-6345*+6–1.運算數(shù)相對順序不變2.運算符號順序發(fā)生改變需要存儲“等待中”的運算符號要將當前運算符號與“等待中”的最后一個運算符號比較有括號怎么辦？棧中綴表達式求值有括號怎么辦？棧32〖例〗3*

(4+5

)/

6

=?345+*6/top輸出:3輸入對象:3(操作數(shù))

輸入對象:*

(乘法)輸入對象:((左括號)輸入對象:4(操作數(shù))輸入對象:+

(加法)輸入對象:5(操作數(shù))輸入對象:)(右括號)輸入對象:/

(除法)輸入對象:6(操作數(shù))(4+5T(N)=O(N)*+*/6/〖例〗3*(4+5)/6=?34533中綴表達式如何轉換為后綴表達式從頭到尾讀取中綴表達式的每個對象，對不同對象按不同的情況處理。①運算數(shù)：直接輸出；②左括號：壓入棧；③右括號：將棧頂?shù)倪\算符彈出并輸出，直到遇到左括號（出棧，不輸出）；④運算符：?若優(yōu)先級大于棧頂運算符時，則把它壓棧；?若優(yōu)先級小于等于棧頂運算符時，將棧頂運算符彈出并輸出；再比較新的棧頂運算符，直到該運算符大于棧頂運算符優(yōu)先級為止，然后將該運算符壓棧；⑤若各對象處理完畢，則把棧中存留的運算符一并輸出。中綴表達式如何轉換為后綴表達式從頭到尾讀取中綴表達式的341）無括號算術表達式求值

表達式計算程序設計語言中都有計算表達式的問題，這是語言編譯中的典型問題。

(1)表達式形式：由運算對象、運算符及必要的表達式括號組成；

(2)表達式運算：運算時要有一個正確的運算形式順序。由于某些運算符可能具有比別的運算符更高的優(yōu)先級，因此表達式不可能嚴格的從左到右進行運算，見圖3.5。1）無括號算術表達式求值表達式計算35圖3.5表達式運算及運算符優(yōu)先級圖3.5表達式運算及運算符優(yōu)先級36圖3.6無括號算術表達式的處理過程圖3.6無括號算術表達式的處理過程372）算術表達式處理規(guī)則

(1)規(guī)定優(yōu)先級表。

(2)設置兩個棧：OVS(運算數(shù)棧)和OPTR(運算符棧)。

(3)自左向右掃描，遇操作數(shù)進OVS，遇操作符則與OPTR棧頂優(yōu)先數(shù)比較：當前操作符>OPTR棧頂,當前操作符進OPTR棧；當前操作符≤OPTR棧頂，OVS棧頂、次頂和OPTR棧頂，退棧形成運算T(i)，T(i)進OVS棧。例：實現(xiàn)A/B*C+D*E＃的運算過程時棧區(qū)變化情況。2）算術表達式處理規(guī)則38棧的其他應用：

函數(shù)調用及遞歸實現(xiàn)深度優(yōu)先搜索回溯算法……棧的其他應用：393.3棧與遞歸的實現(xiàn)

棧非常重要的一個應用是在程序設計語言中用來實現(xiàn)遞歸。遞歸是指在定義自身的同時又出現(xiàn)了對自身的調用。如果一個函數(shù)在其定義體內直接調用自己，則稱其為直接遞歸函數(shù)；如果一個函數(shù)經過一系列的中間調用語句，通過其它函數(shù)間接調用自己，則稱其為間接遞歸函數(shù)。3.3棧與遞歸的實現(xiàn)棧非常重要的一個40遞歸過程的實現(xiàn)一個函數(shù)調用另一個函數(shù)時，在運行被調用函數(shù)之前，系統(tǒng)做的工作有：

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

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

(3)將程序轉移到被調函數(shù)的入口。遞歸過程的實現(xiàn)41

而從被調用函數(shù)返回調用函數(shù)之前，系統(tǒng)也應完成三件工作：

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

(2)恢復上層參數(shù)（釋放被調函數(shù)的數(shù)據(jù)區(qū)）；

(3)依照被調函數(shù)保存的返回地址，將控制轉移回調用函數(shù)。當多個函數(shù)調用時按后調用先返回的原則。

而從被調用函數(shù)返回調用函數(shù)之前，系統(tǒng)也應完成三42

系統(tǒng)將整個程序運行時所需的數(shù)據(jù)空間安排在一個棧中，每次調用一個函數(shù)時就為它在棧頂分配一個存儲區(qū)，當一個函數(shù)返回時就釋放它的存儲區(qū)，當前正在運行的函數(shù)所有數(shù)據(jù)必在棧頂。voidfirst(int,int);voidfirst(ints,intt)voidsecond(int); {voidmain() inti;{ ……intm,n; sencond(i);

…… 2:first(m,n); ……1: }

…… voidsecond(intd) {} intx,y;

…… }

系統(tǒng)將整個程序運行時所需的數(shù)據(jù)空間安排在一個棧中，432)遞歸結構

例：n階Hanoi塔問題：假設有三個分別命名為X、Y和Z的塔座，在塔座X上插有n個直徑大小各不相同、依小到大編號為1，2,…，n的圓盤。現(xiàn)要求將X軸上的n個圓盤移至塔座Z上并仍按同樣順序疊排，圓盤移動時必須遵循下列原則：

(1)每次只能移動一個圓盤；

(2)圓盤可以插在X、Y和Z中的任何一個塔座上；

(3)任何時刻都不能將一個較大的圓盤壓在較小的圓盤之上。2)遞歸結構例：n階Hanoi塔問題：假44

如何實現(xiàn)移動圓盤的操作呢？當n=1時，問題比較簡單，只要將編號為1的圓盤從塔座X直接移動到塔座Z上即可；當n>1時，需利用塔座Y作輔助塔座，若能設法將壓在編號為n的圓盤上的n-1個圓盤從塔座X(依照上述原則)移至塔座Y上，則可先將編號為n的圓盤從塔座X移至塔座Z上，然后再將塔座Y上的n-1個圓盤(依照上述原則)移至塔座Z上。而如何將n-1個圓盤從一個塔座移至另一個塔座問題是一個和原問題具有相同特征屬性的問題，只是問題的規(guī)模小個1，因此可以用同樣方法求解。由此可得如下算法所示的求解n階Hanoi塔問題的函數(shù)。如何實現(xiàn)移動圓盤的操作呢？當n=1時，問題比較45voidhanoi(intn,charx,chary,charz)/*將塔座X上按直徑由小到大且至上而下編號為1至n的n個圓盤按規(guī)則搬到塔座Z上，Y可用作輔助塔座*/1{2if(n==1)3move(x,1,z);/*將編號為1的圓盤從X移動Z*/4else{5hanoi(n-1,x,z,y);/*將X上編號為1至n-1的圓盤移到Y,Z作輔助塔*/6move(x,n,z);/*將編號為n的圓盤從X移到Z*/7hanoi(n-1,y,x,z);/*將Y上編號為1至n-1的圓盤移動到Z，X作輔助塔*/8}9}voidhanoi(intn,charx,chary46

下面給出三個盤子搬動時hanoi(3,A,B,C)遞歸調用過程，如圖3.8所示。hanoi(2,A,C,B):hanoi(1,A,B,C)move(A->C)1號搬到Cmove(A->B) 2號搬到Bhanoi(1,C,A,B)move(C->B)1號搬到Bmove(A->C) 3號搬到Chanoi(2,B,A,C):hanoi(1,B,C,A)move(B->A) 1號搬到Amove(B->C)2號搬到Chanoi(1,A,B,C)move(A->C) 1號搬到C下面給出三個盤子搬動時hanoi(3,A,47圖3.8Hanoi塔的遞歸函數(shù)運行示意圖圖3.8Hanoi塔的遞歸函數(shù)運行示意圖483)遞歸問題的優(yōu)點通過上面的例子可看出，遞歸既是強有力的數(shù)學方法，也是程序設計中一個很有用的工具。其特點是對遞歸問題描述簡捷，結構清晰，程序的正確性容易證明。

4)遞歸算法求解問題的要素遞歸算法就是算法中有直接或間接調用算法本身的算法。遞歸算法的要點如下：

(1)問題具有類同自身的子問題的性質，被定義項在定義中的應用具有更小的尺度。

(2)被定義項在最小尺度上有直接解。3)遞歸問題的優(yōu)點49

設計遞歸算法的方法是：

(1)尋找方法，將問題化為原問題的子問題求解（例n!=n*(n-1)!）。

(2)設計遞歸出口，確定遞歸終止條件(例求解n!時，當n=1時，n!=1)。設計遞歸算法的方法是：50

2.遞歸算法到非遞歸算法轉換遞歸算法具有兩個特性：

(1)遞歸算法是一種分而治之、把復雜問題分解為簡單問題的求解問題方法，對求解某些復雜問題，遞歸算法的分析方法是有效的。（2）遞歸算法的時間效率低。2.遞歸算法到非遞歸算法轉換511)消除遞歸的原因其一：有利于提高算法時空性能，因為遞歸執(zhí)行時需要系統(tǒng)提供隱式棧實現(xiàn)遞歸，效率低且費時。其二：無應用遞歸語句的語言設施環(huán)境條件，有些計算機語言不支持遞歸功能，如FORTRAN語言中無遞歸機制。其三：遞歸算法是一次執(zhí)行完，這在處理有些問題時不合適，也存在一個把遞歸算法轉化為非遞歸算法的需求。1)消除遞歸的原因522)簡單遞歸（尾遞歸和單向遞歸）消除在簡單情況下，將遞歸算法可簡化為線性序列執(zhí)行，可直接轉換為循環(huán)實現(xiàn)。遞歸進層三件事：保存本層參數(shù)、返回地址;

傳遞參數(shù)，分配局部數(shù)據(jù)空間;

控制轉移。遞歸退層三件事：恢復上層； 傳遞結果； 轉斷點執(zhí)行。2)簡單遞歸（尾遞歸和單向遞歸）消除遞53

尾遞歸是指遞歸調用語句只有一個，而且是處于算法的最后。我們以階乘問題的遞歸算法Fact(n)為例討論尾遞歸算法的運行過程。為討論方便，我們列出階乘問題的遞歸算法Fact(n)，并簡化掉參數(shù)n的出錯檢查語句，改寫遞歸調用語句的位置在最后，算法如下：longFact(intn){if(n==0)return1;returnn*Fact(n-1);}尾遞歸是指遞歸調用語句只有一個，而且是處于54圖3.9遞歸調用變化情況示意圖3.9遞歸調用變化情況示意55圖3.10f(3)遞歸調用流程變化示意圖3.10f(3)遞歸調用流程變化示意56

由圖3.10可看出，整個計算包括自上而下遞歸調用進層和自下而上遞歸返回退層兩個階段，所有遞歸調用直接或間接依賴f(0)，所以整個階段分兩步，計算順序在第二階段，先計算f(0)→f(1)→…→f(n)，工作變量y記錄中間結果。由圖3.10可看出，整個計算包括自上而下遞歸57循環(huán)結構的階乘問題算法Fact(n)如下：longFact(intn){intfac=1;for(inti=1;i<=n;i++)/*依次計算f(1)，…，f(n)*/fac=fac*i;/*f(i)=f(i)*i*/returnfac;}循環(huán)結構的階乘問題算法Fact(n)如下：longFac58

單向遞歸的一個典型例子是我們討論過的計算斐波那契數(shù)列的算法Fib(n)。其中，遞歸調用語句Fib(n-1)和Fib(n-2)只與主調用函數(shù)Fib(n)有關，相互之間參數(shù)無關，并且這些遞歸調用語句也和尾遞歸一樣處于算法的最后。例：斐波那契數(shù)列單向遞歸的一個典型例子是我們討論過的計算斐波那59斐波那契數(shù)列的遞歸算法Fib(n)如下，F(xiàn)ib(intn){if（n==0||n==1）returnn;/*遞歸出口*/elsereturnFib(n-1)+Fib(n-2);/*遞歸調用*/}斐波那契數(shù)列的遞歸算法Fib(n)如下，F(xiàn)ib(int60圖3.11Fib(5)遞歸調用過程示意圖3.11Fib(5)遞歸調用過程示意61圖3.12Fib(5)循環(huán)調用過程示意圖圖3.12Fib(5)循環(huán)調用過程示意圖62intFib(intn){intx,y,z;if（n==0||n==1）returnn;/*計算Fib(0),Fib(1)*/else{intx=0,y=1,z;/*x=Fib(0),y=Fib(1)*/for(i=2;i<=n;i++){z=y;/*z=Fib(i-1)*/y=x+y;/*y=Fib(i-1)+Fib(i-2)，求Fib(i)，形成第i項*/x=z;/*x=Fib(i-1)*/}}returny;}intFib(intn)633.4隊列3.4.1隊列的定義隊列

(Queue)是另一種限定性的線性表，它只允許在表的一端插入元素，而在另一端刪除元素，所以隊列具有先進先出(FistInFistOut，縮寫為FIFO)的特性。在隊列中，允許插入的一端叫做隊尾(rear)，允許刪除的一端則稱為隊頭(front)。假設隊列為q=(a1，a2，…，an)，那么a1就是隊頭元素，an則是隊尾元素。隊列中的元素是按照a1、a2、…、an的順序進入的，退出隊列也必須按照同樣的次序依次出隊，也就是說，只有在a1、a2、…、an-1都離開隊列之后，an才能退出隊列。3.4隊列3.4.1隊列的定義64

數(shù)據(jù)元素：可以是任意類型的數(shù)據(jù)，但必須屬于同一個數(shù)據(jù)對象。

關系：隊列中數(shù)據(jù)元素之間是線性關系?；静僮鳎海?）InitQueue(&Q)：初始化操作。設置一個空隊列。（2）QueueEmpty(Q)：判空操作。若隊列為空，則返回TRUE，否則返回FALSE。（3）EnQueue(&Q，e)：進隊操作。在隊列Q的隊尾插入e。數(shù)據(jù)元素：可以是任意類型的數(shù)據(jù)，但必須屬于同65

（4）DeQueue(&Q,&e)：出隊操作。使隊列Q的隊頭元素出隊，并用e帶回其值。（5）ClearQueue(&Q)：隊列置空操作。將隊列Q置為空隊列。（6）DestroyQueue(&Q)：隊列銷毀操作。釋放隊列的空間。（4）DeQueue(&Q,&e)：出隊操作。使663.4.2隊列的表示和實現(xiàn)1.鏈隊列圖3.13鏈隊列3.4.2隊列的表示和實現(xiàn)1.鏈隊列圖3.13鏈67鏈隊列可以定義如下：＃defineTRUE1＃defineFALSE0typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;鏈隊列可以定義如下：＃defineTRUE168（1）初始化操作StatusInitQueue(LinkQueue&Q){Q.front=Q.rear=(Queueptr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next=NULL;returnOK;}（1）初始化操作69（2）銷毀隊列StatusDestroyQueue(LinkQueue&Q){while(Q.front){ Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear;}returnOK;}（2）銷毀隊列70（3）入隊操作StatusEnQueue(LinkQueue&Q,QelemTypee){p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}（3）入隊操作71（4）出隊操作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);returnOK;}（4）出隊操作722.循環(huán)隊列圖3.14隊列的基本操作2.循環(huán)隊列圖3.14隊列的基本操作73圖3.15循環(huán)隊列圖3.15循環(huán)隊列74如何區(qū)分隊列“空”和“滿”另設一個標志位以區(qū)分隊列是空還是滿；少用一個元素空間，當隊列頭指針在隊列尾指針的下一個位置上時為“滿”。當Q.front=Q.rear時隊空；Q.rear+1=Q.front時隊滿循環(huán)隊列滿足條件

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

如何區(qū)分隊列“空”和“滿”75循環(huán)隊列的類型定義：#defineMAXQSIZE100/*隊列的最大長度*/typedefstruct{QElemType*base;/*隊列的元素空間*/intfront;/*頭指針指示器*

intrear; /*尾指針指示器*/}SqQueue;

循環(huán)隊列的類型定義：76（1）初始化操作StatusInitQueue(SqQueue&Q){Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;returnOK;}（1）初始化操作77（2）入隊操作StatusEnQueue(SqQueue&Q,QElemTypee){if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}（2）入隊操作78（3）出隊操作

StatusDeQueue(SqQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}（3）出隊操作79(4)求隊列長度intQueueLength(SqQueueQ){return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;}(4)求隊列長度80（1）設有一個棧，元素進棧的次序為a,b,c。問經過棧操作后可以得到哪些輸出序列？（2）設有一個循環(huán)隊列S，空間大小為MAX，隊頭和隊尾的指針分別為front和rear，隊列為空的條件是什么？隊列為滿的條件是什么？插入一個元素，指針的變化是什么?刪除一個元素指針的變化是什么?（1）設有一個棧，元素進棧的次序為a,b,c。問經過棧操81（3）設Q是一個初始分配空間為7的順序隊列，初始狀態(tài)為front=rear=0，請畫出做完下列操作后隊列的頭尾，指針的狀態(tài)變化情況，若不能入隊，請指出其元素，并說明理由。a,b,c,d入隊a,b,c出隊i,j,k,l,m入隊d,i出隊n,o,p,q,r入隊（3）設Q是一個初始分配空間為7的順序隊列，初始狀態(tài)為fro82（4）假設Q初始分配空間為6的循環(huán)隊列，初始狀態(tài)為front=rear=0，請畫出做完下列操作后隊列的頭尾，指針的狀態(tài)變化情況，若不能入對，請指出其元素，并說明理由。d,e,b,g,h入隊d,e出隊i,j,k,l,m入隊出隊n,o,p,q,r入隊b（4）假設Q初始分配空間為6的循環(huán)隊列，初始狀態(tài)為front83回憶：什么是數(shù)據(jù)結構？答：數(shù)據(jù)結構是指相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。什么是數(shù)據(jù)？答：對客觀事物的符號表示，在計算機科學中是指所有能輸入到計算機中，并被計算機處理的符號的總稱。什么是數(shù)據(jù)元素：答：是數(shù)據(jù)的基本單位，在計算機中通常作為一個整體進行考慮和處理?；貞洠?4回憶：基本的數(shù)據(jù)邏輯結構都有哪幾種？答：集合，線性結構，樹形結構、網(wǎng)狀結構。存儲結構分為哪幾種？答：順序存儲和鏈式存儲。算法的5個特性是什么？答：有窮性、確定性、可行性、輸入和輸出。算法設計的要求？

答：正確性、可讀性、健壯性、效率與低存儲量需求?；貞洠?5為什么順序表的插入和刪除操作必須移動元素？平均需要移動多少個元素？

答：線性表的順序存儲是用一組連續(xù)的內存單元依次存放線性表的數(shù)據(jù)元素，元素在內存的物理存儲次序與它們在線性表中的邏輯次序相同，順序表中插入時，該位置后面的元素都向后移動一位，不然無法實現(xiàn)插入功能。順序表中刪除時，該位置后面的元素都向前移動一位，從而刪除一個元素。

平均需要移動一半的元素。棧和隊列相對于線性表有什么特點：為什么順序表的插入和刪除操作必須移動元素？平均需要移動多少個86棧和隊列相對于線性表有什么特點：答：棧具有后進先出的特點，只能在棧頂進行插入和刪除操作。隊列具有先進先出的特點，只能在隊頭刪除元素，在隊尾插入元素。判斷棧S和隊列L為空的條件是什么：答：S.top==S.base。L.front==L.rear。循環(huán)隊列L為滿的條件是什么？答：(Q.rear+1)%MAXQSIZE==Q.front棧和隊列相對于線性表有什么特點：87第3章限定性線性表—棧和隊列3.1棧3.2棧的應用舉例3.3棧與遞歸的實現(xiàn)3.4隊列第3章限定性線性表—棧和隊列3.1棧883.1棧3.1.1棧的定義棧作為一種限定性線性表，是將線性表的插入和刪除運算限制為僅在表尾進行，通常將表中允許進行插入、刪除操作的一端稱為棧頂(Top)，因此棧頂?shù)漠斍拔恢檬莿討B(tài)變化的，它由一個稱為棧頂指針的位置指示器指示。同時表的另一端被稱為棧底(Bottom)。當棧中沒有元素時稱為空棧。棧的插入操作被形象地稱為進?；蛉霔＃瑒h除操作稱為出?；蛲藯?。

3.1棧3.1.1棧的定義89設S=(a1,a2,…,an)表示棧，則a1為棧底元素，an

為棧頂元素。棧是一種后進先出（LastInFirstOut）的線性表（簡稱LIFO結構）。圖3.1棧設S=(a1,a2,…,an)表示棧，則a1為棧底元素，an90棧只能對棧頂元素進行插入和刪除操作。例：若輸入A，B，C，D，同時在插入的時候也可能進行刪除操作。可能的輸出序列為：B，A，C，D;

C、D、A、B；D，A，C，B；C、A、D、B；D，C，A，B；C、B、D、A；B，C，A，D；A，C，B，D；棧只能對棧頂元素進行插入和刪除操作。91ADTStack{

數(shù)據(jù)元素：可以是任意類型的數(shù)據(jù)，但必須屬于同一個數(shù)據(jù)對象。數(shù)據(jù)關系：棧中數(shù)據(jù)元素之間是線性關系?；静僮鳎海?）InitStack(&S)

初始條件：S為未初始化的棧。操作結果：將S初始化為空棧。（2）ClearStack(&S)

初始條件：棧S已經存在。操作結果：將棧S置成空棧。ADTStack{92

（3）StackEmpty(S)

初始條件：棧S已經存在。操作結果：若S為空棧，則函數(shù)值為TRUE，否則FALSE

（4）Push(&S,e)

初始條件：棧S已經存在。操作結果：在S的頂部插入(亦稱壓入)元素e；（3）StackEmpty(S)93

（5）Pop(&S,&e)

初始條件：棧S已經存在。操作結果：刪除(亦稱彈出)棧S的頂部元素，并用e帶回該值。（6）GetTop(S,&e)

初始條件：棧S已經存在。操作結果：取棧S的頂部元素。與Pop(&S,e)不同之處在于GetTop(S,&e)不改變棧頂?shù)奈恢谩＃?）Pop(&S,&e)943.1.2棧的表示和實現(xiàn)1.順序棧順序棧是用順序存儲結構實現(xiàn)的棧，即利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時由于棧的操作的特殊性，還必須附設一個位置指針top（棧頂指針）來動態(tài)地指示棧頂元素在順序棧中的位置。通常以top=0表示空棧。順序棧的存儲結構可以用C語言中的一維數(shù)組來表示。棧的順序存儲結構定義如下：3.1.2棧的表示和實現(xiàn)1.順序棧95＃defineTRUE1＃defineFALSE0typedefstruct{SElemType*base;SElemType*top;intstacksize;//棧可使用的最大容量}SqStack;

按初始分配量進行第一次存儲分配，base為棧底指針，始終指向棧底。top為棧頂指針，初值指向棧底，每插入一個元素，top增1；每刪除一個元素，top減1，top始終在棧頂元素的下一個位置上。

＃defineTRUE196圖3.2順序棧中的進棧和出棧43210432104321043210圖3.2順序棧中的進棧和出棧444497順序?；静僮鞯膶崿F(xiàn)如下:(1)初始化。StatusInitStack(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;returnOK;}順序?；静僮鞯膶崿F(xiàn)如下:StatusInitStac98(2)取棧頂元素StatusGetTop(SqStackS,SElemType&e){if(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}(2)取棧頂元素99(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;returnOK;}(3)入棧。100(4)出棧StatusPop(SqStack&S,SelemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}(4)出棧1012.鏈棧圖3.4鏈棧示意圖鏈式棧無棧滿問題，空間可擴充插入與刪除僅在棧頂處執(zhí)行鏈式棧的棧頂在鏈頭適合于多棧操作2.鏈棧圖3.4鏈棧示意圖鏈式棧無棧滿問題，空間可1022.鏈棧

圖3.4鏈棧示意圖棧的鏈式存儲結構實際上就是一個單鏈表，叫做鏈棧。插入和刪除操作只能在鏈棧的棧頂進行。

棧頂指針Top應該在鏈表的哪一頭？

鏈式棧的棧頂在鏈頭插入與刪除僅在棧頂處執(zhí)行鏈式棧無棧滿問題，空間可擴充適合于多棧操作2.鏈棧圖3.4鏈棧示意圖棧的鏈式存儲結構1032.鏈棧/*

鏈棧結構

*/

typedef

struct

StackNode

{

SElemType

data;

//節(jié)點數(shù)據(jù)域

struct

StackNode

*next;//節(jié)點指針域

}StackNode,*LinkStackPtr;

//節(jié)點指針

typedef

struct

LinkStack

{

LinkStackPtr

top;

//棧頂指針

int

count;

//棧中元素個數(shù)}LinkStack;

2.鏈棧/*

鏈棧結構

*/

1042.鏈棧//棧的初始化操作Status

InitStack(LinkStack

*S)

{

S->top

=

(LinkStackPtr)malloc(sizeof(StackNode));

if(!S->top)

return

ERROR;

S->top

=

NULL;

S->count

=

0;

return

OK;

}

2.鏈棧//棧的初始化操作1052.鏈棧/*

把S置為空棧

*/

Status

ClearStack(LinkStack

*S)

{

LinkStackPtr

p,q;

p

=

S->top;

while(p)

{

q

=

p;

p

=

p->next;

free(q);

}

S->count=0;

return

OK;

}

2.鏈棧/*

把S置為空棧

*/

1062.鏈棧/*

若棧S為空棧，則返回TRUE，否則返回FALSE

*/

Status

IsEmptyStack(LinkStack

S)

{

if

(S.count

==

0)

{

return

TRUE;

}

else

{

return

FALSE;

}

}

2.鏈棧/*

若棧S為空棧，則返回TRUE，否則返回FA1072.鏈棧/*

若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR

*/

Status

GetTopElem(LinkStack

S,SElemType

*e)

{

if

(S.top

==

NULL)

{

return

ERROR;

}

else

{

*e

=

S.top->data;

}

return

OK;

}

2.鏈棧/*

若棧不空，則用e返回S的棧頂元素，并返回O1082.鏈棧Status

Push(LinkStack

*S,SElemType

e)

{

LinkStackPtr

s=(LinkStackPtr)malloc(sizeof(StackNode));

if

(!s)

{

return

ERROR;

}

s->data

=

e;

s->next

=

S->top

S->top

=

s;

S->count++;

return

OK;

}

2.鏈棧Status

Push(LinkStack

*S1092.鏈棧/*

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

*/

Status

Pop(LinkStack

*S,SElemType

*e)

{

LinkStackPtr

p;

if(IsEmptyStack(*S))

{

return

ERROR;

}

*e

=

S->top->data;

p

=

S->top;

S->top

=

S->top->next

free(p);

S->count--;

return

OK;

}

2.鏈棧/*

若棧不空，則刪除S的棧頂元素，用e返回其值1103.2棧的應用舉例1.數(shù)制轉換假設要將十進制數(shù)N轉換為d進制數(shù)，一個簡單的轉換算法是重復下述兩步，直到N等于零：X=Nmodd(其中mod為求余運算)N=Ndivd(其中div為整除運算)3.2棧的應用舉例1.數(shù)制轉換111如(1348)10=(2504)8

NN/8N%8134816841682102125202如(1348)10=(2504)8NN/8N%81112voidconversion(){ InitStack(S); scanf(“%d”,&N); while(N) { Push(s,N%8); N=N/8; } while(!StackEmpty(s)){ Pop(S,e); printf(“%d”,e); }}voidconversion()1132.括號匹配問題假設表達式中包含三種括號：圓括號、方括號和花括號，它們可互相嵌套，如([{}]([]))或({([][()])})等均為正確的格式，而{[]})}或{[()]或([]}均為不正確的格式。在檢驗算法中可設置一個空棧。讀入字符直到文件尾。如果字符是一個左括號，則直接入棧。如果字符是一個右括號，那么若棧為空，則報錯；若棧不為空，則將棧頂元素出棧。如果出棧的符號不是對應的左括號，則報錯。在文件尾，如果棧非空則報錯。2.括號匹配問題1143.表達式求值

表達式求值是高級語言編譯中的一個基本問題，是棧的典型應用實例。任何一個表達式都是由操作數(shù)(operand)、運算符(operator)和界限符(delimiter)組成的。操作數(shù)既可以是常數(shù)，也可以是被說明為變量或常量的標識符；運算符可以分為算術運算符、關系運算符和邏輯運算符三類；基本界限符有左右括號和表達式結束符等。3.表達式求值表達式求值是高級語言編譯中的115[例]算術表達式5+6/2-3*4。正確理解：

5+6/2-3*4=5+3-3*4=8-3*4=8-12=-4由兩類對象構成的：（1）操作數(shù)，如2、3、4（2）運算符號，如+、-、*、/不同運算符號優(yōu)先級不一樣[例]算術表達式5+6/2-3*4。正確理解：116后綴表達式

中綴表達式：運算符號位于兩個運算數(shù)之間。如a+b*

c-

d/

e后綴表達式：運算符號位于兩個運算數(shù)之后。如abc*+

de/-〖例〗62/

3-

42*+

=?

后綴表達式求值策略：從左向右“掃描”，逐個處理運算數(shù)和運算符號。1.遇到運算數(shù)怎么辦？如何“記住”目前還不未參與運算的數(shù)？2.遇到運算符號怎么辦？對應的運算數(shù)是什么？啟示：需要有種存儲方法，能順序存儲運算數(shù)，并在需要時“倒序”輸出！后綴表達式中綴表達式：運算符號位于兩個運算數(shù)之間。如a117對象:6(運算數(shù))〖例〗62/

3-

42*+

=?

對象:2(運算數(shù))對象:/

(運算符)對象:3(運算數(shù))

對象:-

(運算符)

對象:4(運算數(shù))

對象:2(運算數(shù))

對象:*

(運算符)對象:+

(運算符)

Pop:8top62toptop2

6

/=33333-=0042top24*=8880+=88T(N)=O(N)8對象:6(運算數(shù))〖例〗62/3-42118中綴表達式求值

基本策略：將中綴表達式轉換為后綴表達式，然后求值

如何將中綴表達式轉換為后綴？觀察一個簡單例子：3+4*5-6345*+6–1.運算數(shù)相對順序不變2.運算符號順序發(fā)生改變需要存儲“等待中”的運算符號要將當前運算符號與“等待中”的最后一個運算符號比較有括號怎么辦？棧中綴表達式求值有括號怎么辦？棧119〖例〗3*

(4+5

)/

6

=?345+*6/top輸出:3輸入對象:3(操作數(shù))

輸入對象:*

(乘法)輸入對象:((左括號)輸入對象:4(操作數(shù))輸入對象:+

(加法)輸入對象:5(操作數(shù))輸入對象:)(右括號)輸入對象:/

(除法)輸入對象:6(操作數(shù))(4+5T(N)=O(N)*+*/6/〖例〗3*(4+5)/6=?345120中綴表達式如何轉換為后綴表達式從頭到尾讀取中綴表達式的每個對象，對不同對象按不同的情況處理。①運算數(shù)：直接輸出；②左括號：壓入棧；③右括號：將棧頂?shù)倪\算符彈出并輸出，直到遇到左括號（出棧，不輸出）；④運算符：?若優(yōu)先級大于棧頂運算符時，則把它壓棧；?若優(yōu)先級小于等于棧頂運算符時，將棧頂運算符彈出并輸出；再比較新的棧頂運算符，直到該運算符大于棧頂運算符優(yōu)先級為止，然后將該運算符壓棧；⑤若各對象處理完畢，則把棧中存留的運算符一并輸出。中綴表達式如何轉換為后綴表達式從頭到尾讀取中綴表達式的1211）無括號算術表達式求值

表達式計算程序設計語言中都有計算表達式的問題，這是語言編譯中的典型問題。

(1)表達式形式：由運算對象、運算符及必要的表達式括號組成；