第三章棧和隊(duì)列通常稱，棧和隊(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ù)類型3.1棧的類型定義3.2棧的應(yīng)用舉例3.3棧類型的實(shí)現(xiàn)3.4隊(duì)列的類型定義3.5隊(duì)列類型的實(shí)現(xiàn)3.1

棧的類型定義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>

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

InitStack(&S)

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

DestroyStack(&S)

初始條件：棧S已存在。

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

StackEmpty(S)

初始條件：棧S已存在。

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

StackLength(S)

初始條件：棧S已存在。

操作結(jié)果：返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度。

GetTop(S,&e)

初始條件：棧S已存在且非空。操作結(jié)果：用e返回S的棧頂元素。a1a2an……

ClearStack(&S)

初始條件：棧S已存在。

操作結(jié)果：將S清為空棧。Push(&S,e)

初始條件：棧S已存在。

操作結(jié)果：插入元素e為新的棧頂元素。a1a2ane……Pop(&S,&e)

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

操作結(jié)果：刪除S的棧頂元素，并用e返回其值。a1a2anan-1

……3.2

棧的應(yīng)用舉例例一、數(shù)制轉(zhuǎn)換例二、括號(hào)匹配的檢驗(yàn)例三、行編輯程序問(wèn)題例四、迷宮求解例五、表達(dá)式求值例六、實(shí)現(xiàn)遞歸

例一、數(shù)制轉(zhuǎn)換

算法基于原理：

N=(Ndivd)×d+Nmodd

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

，其運(yùn)算過(guò)程如下：

NNdiv8Nmod8

13481684

168210

2125

202計(jì)算順序輸出順序voidconversion(){InitStack(S);

scanf("%d",N);

while(N){

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

}

while(!StackEmpty(S)){

Pop(S,e);

printf("%d",e);

}}//conversion例二、括號(hào)匹配的檢驗(yàn)假設(shè)在表達(dá)式中（［］（））或［（［］［］）］等為正確的格式，［（］）或（［（））或(()])均為不正確的格式。則檢驗(yàn)括號(hào)是否匹配的方法可用“期待的急迫程度”這個(gè)概念來(lái)描述。分析可能出現(xiàn)的不匹配的情況:到來(lái)的右括弧非是所“期待”的;例如：考慮下列括號(hào)序列：

[([][])]12345678到來(lái)的是“不速之客”;直到結(jié)束，也沒(méi)有到來(lái)所“期待”的括弧;算法的設(shè)計(jì)思想：1）凡出現(xiàn)左括弧，則進(jìn)棧；2）凡出現(xiàn)右括弧，首先檢查棧是否空若?？?，則表明該“右括弧”多余否則和棧頂元素比較，若相匹配，則“左括弧出?！狈駝t表明不匹配3）表達(dá)式檢驗(yàn)結(jié)束時(shí)，若?？?，則表明表達(dá)式中匹配正確否則表明“左括弧”有余Statusmatching(string&exp){

intstate=1;

while(i<=Length(exp)&&state){

switchofexp[i]{

case

左括弧:{Push(S,exp[i]);i++;break;}

case”)”:{

if(NOTStackEmpty(S)&&GetTop(S)=“(“{Pop(S,e);i++;}

else{state=0;}

break;}……}

if(StackEmpty(S)&&state)returnOK;…...例三、行編輯程序問(wèn)題如何實(shí)現(xiàn)？“每接受一個(gè)字符即存入存儲(chǔ)器”?

并不恰當(dāng)！

設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū);并假設(shè)“#”為退格符，“@”為退行符。

在用戶輸入一行的過(guò)程中，允許用戶輸入出差錯(cuò)，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。合理的作法是：假設(shè)從終端接受了這樣兩行字符：

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

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

while(*s)

putchar(*s++);

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

11

112

222

232

133

134

424

125

126

416

315

314

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

do｛

若當(dāng)前位置可通，

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

若該位置是出口位置，則算法結(jié)束；否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；

｝

否則{

｝｝while(棧不空）；求迷宮中一條從入口到出口的路徑的算法：

…

…若棧不空且棧頂位置尚有其他方向未被探索，則設(shè)定新的當(dāng)前位置為:沿順時(shí)針?lè)较蛐D(zhuǎn)找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則｛刪去棧頂位置；//從路徑中刪去該通道塊

若棧不空，則重新測(cè)試新的棧頂位置，

直至找到一個(gè)可通的相鄰塊或出棧至?？?；｝若?？?，則表明迷宮沒(méi)有通路。

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

表達(dá)式::=(操作數(shù))+(運(yùn)算符)+(操作數(shù))

操作數(shù)::=簡(jiǎn)單變量|表達(dá)式簡(jiǎn)單變量::=標(biāo)識(shí)符|無(wú)符號(hào)整數(shù)例五、表達(dá)式求值

表達(dá)式的三種標(biāo)識(shí)方法：設(shè)

Exp=S1+

OP

+S2則稱

OP

+S1+S2

為前綴表示法

S1+

OP

+S2

為中綴表示法

S1+S2+

OP

為后綴表示法

例如:Exp=a

b

+

(c

d/e)

f前綴式:+

ab

c/def中綴式:a

b

+

c

d/e

f后綴式:ab

cde/

f

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

運(yùn)算符在式中出現(xiàn)的順序恰為表達(dá)式的運(yùn)算順序;

每個(gè)運(yùn)算符和在它之前出現(xiàn)

且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式;如何從后綴式求值？先找運(yùn)算符，再找操作數(shù)例如：

ab

cde/

f

+a

bd/ec-d/e(c-d/e)

f如何從原表達(dá)式求得后綴式？

每個(gè)運(yùn)算符的運(yùn)算次序要由它之后的一個(gè)運(yùn)算符來(lái)定，在后綴式中,優(yōu)先數(shù)高的運(yùn)算符領(lǐng)先于優(yōu)先數(shù)低的運(yùn)算符。分析“原表達(dá)式”和“后綴式”中的運(yùn)算符:原表達(dá)式:a+b

c

d/e

f

后綴式:abc

+de/f

從原表達(dá)式求得后綴式的規(guī)律為：1)設(shè)立暫存運(yùn)算符的棧;2)設(shè)表達(dá)式的結(jié)束符為“#”,

予設(shè)運(yùn)算符棧的棧底為“#”3)若當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴式;4)若當(dāng)前運(yùn)算符的優(yōu)先數(shù)高于棧頂運(yùn)算符，則進(jìn)棧;5)否則，退出棧頂運(yùn)算符發(fā)送給后綴式;

6)“(”對(duì)它之前后的運(yùn)算符起隔離作用，“)”可視為自相應(yīng)左括弧開(kāi)始的表達(dá)式的結(jié)束符。從原表達(dá)式求得后綴式的規(guī)律為：voidtransform(charsuffix[],charexp[]){InitStack(S);Push(S,

#

);p=exp;ch=*p;

while(!StackEmpty(S)){if(!IN(ch,OP))Pass(Suffix,ch);else{}

if(ch!=

#

){p++;ch=*p;}else{Pop(S,ch);Pass(Suffix,ch);}

}//while}//CrtExptree……switch(ch){

case

(

:Push(S,ch);break;

case

)

:

Pop(S,c);

while(c!=

(

)

{Pass(Suffix,c);Pop(S,c)}

break;

defult:while(Gettop(S,c)&&(precede(c,ch)))

{Pass(Suffix,c);Pop(S,c);}

if(ch!=

#

)Push(S,ch);

break;

}

//switch例六、實(shí)現(xiàn)遞歸將所有的實(shí)在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存;為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū);將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。

當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行該被調(diào)用函數(shù)之前，

需先完成三項(xiàng)任務(wù)：保存被調(diào)函數(shù)的計(jì)算結(jié)果;釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū);依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成下列三項(xiàng)任務(wù)：多個(gè)函數(shù)嵌套調(diào)用的規(guī)則是:此時(shí)的內(nèi)存管理實(shí)行“棧式管理”后調(diào)用先返回！例如：voidmain(){voida(){voidb(){

………a();b();

……}//main}//a}//bMain的數(shù)據(jù)區(qū)函數(shù)a的數(shù)據(jù)區(qū)函數(shù)b的數(shù)據(jù)區(qū)遞歸工作棧：遞歸過(guò)程執(zhí)行過(guò)程中占用的數(shù)據(jù)區(qū)。遞歸工作記錄：每一層的遞歸參數(shù)合成一個(gè)記錄。當(dāng)前活動(dòng)記錄：棧頂記錄指示當(dāng)前層的執(zhí)行情況。當(dāng)前環(huán)境指針：遞歸工作棧的棧頂指針。遞歸函數(shù)執(zhí)行的過(guò)程可視為同一函數(shù)進(jìn)行嵌套調(diào)用，例如：voidhanoi(intn,charx,chary,charz){//將塔座x上按直徑由小到大且至上而下編號(hào)為1至n//的n個(gè)圓盤(pán)按規(guī)則搬到塔座z上，y可用作輔助塔座。1if(n==1)2move(x,1,z);//將編號(hào)為１的圓盤(pán)從x移到z3else{4hanoi(n-1,x,z,y);//將x上編號(hào)為１至n-1的

//圓盤(pán)移到y(tǒng),z作輔助塔5move(x,n,z);//將編號(hào)為n的圓盤(pán)從x移到z6hanoi(n-1,y,x,z);//將y上編號(hào)為１至n-1的

//圓盤(pán)移到z,x作輔助塔7}8}83abc返址nxyz52acb51abcvoidhanoi(intn,charx,chary,charz){1if(n==1)2move(x,1,z);3else{4hanoi(n-1,x,z,y);5move(x,n,z);6hanoi(n-1,y,x,z);7}8}71cab3.3 棧類型的實(shí)現(xiàn)順序棧鏈棧//-----棧的順序存儲(chǔ)表示

-----

#defineSTACK_INIT_SIZE100

typedefstruct{

SElemType

*base;

SElemType

*top;

intstacksize;

}

SqStack;

類似于線性表的順序映象實(shí)現(xiàn)，指向表尾的指針可以作為棧頂指針。

StatusInitStack(SqStack&S,intmaxsize){

//構(gòu)造一個(gè)最大空間為maxsize的空順序棧SS.base=new

ElemType[maxsize];

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

S.top=S.base;S.stacksize=maxsize;

returnOK;}

StatusPush(SqStack&S,SElemTypee){//

若棧不滿，則將e插入棧頂

if(S.top-S.base>=S.stacksize)

//棧滿

returnOVERFLOW;*S.top++=e;

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

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

//否則返回ERROR

if

(S.top

==

S.base)

returnERROR;

e=*--S.top;

returnOK;}棧頂指針鏈棧∧a1an注意:鏈棧中指針的方向an-1棧底元素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ì)列的類型定義}

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

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

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

DestroyQueue(&Q)

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

操作結(jié)果：隊(duì)列Q被銷毀，

不再存在。

QueueEmpty(Q)

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

操作結(jié)果：若Q為空隊(duì)列，則返回TRUE，否則返回FALSE。

QueueLength(Q)

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

操作結(jié)果：返回Q的元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度。

GetHead(Q,&e)

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

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

ClearQueue(&Q)

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

操作結(jié)果：將Q清為空隊(duì)列。

EnQueue(&Q,e)

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

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

DeQueue(&Q,&e)

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

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

3.5隊(duì)列類型的實(shí)現(xiàn)鏈隊(duì)列——鏈?zhǔn)接诚笱h(huán)隊(duì)列——順序映象

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

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;鏈隊(duì)列——鏈?zhǔn)接诚髏ypedefstruct{

//鏈隊(duì)列類型

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

QueuePtrrear;//隊(duì)尾指針}LinkQueue;a1∧an…Q.frontQ.frontQ.rear∧空隊(duì)列Q.rear

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

Q.front=Q.rear=

newQNode;

if(!Q.front)exit(OVERFLOW);//存儲(chǔ)分配失敗

Q.front->next=NULL;

returnOK;}

StatusEnQueue(LinkQueue&Q,QElemTypee){

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

p=newQNode;

if(!p)exit(OVERFLOW);//存儲(chǔ)分配失敗

p->data=e;p->next=NULL;

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

returnOK;}a1∧anQ.frontQ.rear∧ep

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

//用e返回其值，并返回OK；否則返回ERROR

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

Q.front->next=p->next;delete(p);

returnOK;}if(Q.rear==p)Q.rear=Q.front;#defineMAXQSIZE100//最大隊(duì)列長(zhǎng)度typedefstruct{QElemType*base;//動(dòng)態(tài)分配存儲(chǔ)空間

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

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

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

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

intqueuesize;}SqQueue;循環(huán)隊(duì)列——順序映象

StatusInitQueue(SqQueue&Q,

intmaxsize){//構(gòu)造一個(gè)最大存儲(chǔ)空間為maxsize的

//空循環(huán)隊(duì)列QQ.base=newElemType[maxsize];

if(!Q.base)exit(OVERFLOW);Q.queuesize=maxsize;Q.front=Q.rear=0;

returnOK;

}StatusEnQueue(SqQueue&Q,ElemTypee){//插入元素e為Q的新的隊(duì)尾元素

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

returnERROR;//隊(duì)列滿

Q.base[Q.rear]=e;

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

returnOK;}

StatusDeQueue(SqQueue&Q,ElemType&e){

//若隊(duì)列不空，則刪除Q的隊(duì)頭元素，

//用e返回其值，并返回OK;否則返回ERRORif(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];

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

returnOK;}隊(duì)列與循環(huán)鏈表

隊(duì)列（包括循環(huán)隊(duì)列）是一個(gè)邏輯概念，而鏈表是一個(gè)存儲(chǔ)概念。一個(gè)隊(duì)列是否是循環(huán)隊(duì)列，不取決于它將采用何種存儲(chǔ)結(jié)構(gòu)，根據(jù)實(shí)際的需要，循環(huán)隊(duì)列可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈