數(shù)據(jù)結(jié)構(gòu)-棧教材

一、教學(xué)內(nèi)容：

1、 棧和隊(duì)列的定義及特點(diǎn)；

2、 棧的順序存儲表示和鏈接存儲表示；

3、 隊(duì)列的順序存儲表示和鏈接存儲表示；

4、 棧和隊(duì)列的應(yīng)用舉例。

第三章棧和隊(duì)列二、教學(xué)要求：

1、掌握棧和隊(duì)列的定義、特性，并能正確應(yīng)用它們解決實(shí)際問題；

2、熟練掌握棧的順序表示、鏈表表示以及相應(yīng)操作的實(shí)現(xiàn)。特別注意?？蘸蜅M的條件；

3、熟練掌握隊(duì)列的順序表示、鏈表表示以及相應(yīng)操作的實(shí)現(xiàn)。特別是循環(huán)隊(duì)列中隊(duì)頭與隊(duì)尾指針的變化情況

棧和隊(duì)列是兩種特殊的線性表，是操作受限的線性表，稱限定性數(shù)據(jù)結(jié)構(gòu)。棧棧的應(yīng)用隊(duì)列隊(duì)列的應(yīng)用3.1棧（stack）一、棧的定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表，表尾—棧頂，表頭—棧底，不含元素的空表稱空棧特點(diǎn)：先進(jìn)后出（FILO）或后進(jìn)先出（LIFO）ana1a2……...棧底棧頂...出棧進(jìn)棧棧s=(a1,a2,……,an)棧的特點(diǎn)根據(jù)棧的定義可知，最先放入棧中元素在棧底，最后放入的元素在棧頂，而刪除元素剛好相反，最后放入的元素最先刪除，最先放入的元素最后刪除。也就是說，棧是一種后進(jìn)先出(LastInFirstOut)的線性表，簡稱為LIFO表。

stack棧的基本操作1.初始化棧：INISTACK(&S)將棧S置為一個空棧(不含任何元素)。2.進(jìn)棧：PUSH(&S,X)將元素X插入到棧S中，也稱為“入?！?、“插入”、“壓入”。3.出棧：POP(&S)

刪除棧S中的棧頂元素，也稱為”退?！?、“刪除”、“彈出”。4.取棧頂元素：GETTOP(S,&e)取棧S中棧頂元素。5.判?？眨篠tackEmpty(S)判斷棧S是否為空，若為空，返回值為true，否則返回值為false。例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例2：一個棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實(shí)現(xiàn)嗎？12345的輸出呢？43512不可能實(shí)現(xiàn)，主要是其中的12順序不能實(shí)現(xiàn)；

12345的輸出可以實(shí)現(xiàn)，只需壓入一個立即彈出一個即可。435612中到了12順序不能實(shí)現(xiàn)；

135426可以實(shí)現(xiàn)。例3：如果一個棧的輸入序列為123456，能否得到435612和135426的出棧序列？答：答：例4：計(jì)算機(jī)系2005年考研題（程序設(shè)計(jì)基礎(chǔ)）設(shè)依次進(jìn)入一個棧的元素序列為c，a，b，d，則可得到出棧的元素序列是：

Ａ）a，b，c，dＢ）c，d，a，bＣ）b，c，d，aＤ）a，c，d，bA、D可以（B、C不行）。答：二、順序棧由于棧是運(yùn)算受限的線性表，因此線性表的存儲結(jié)構(gòu)對棧也適應(yīng)。棧的順序存儲結(jié)構(gòu)簡稱為順序棧，它是運(yùn)算受限的線性表。因此，可用數(shù)組來實(shí)現(xiàn)順序棧。因?yàn)闂５孜恢檬枪潭ú蛔兊?，所以可以將棧底位置設(shè)置在數(shù)組的兩端的任何一個端點(diǎn)；棧頂位置是隨著進(jìn)棧和退棧操作而變化的，故需用一個整型變量top來指示當(dāng)前棧頂?shù)奈恢茫ǔ７Qtop為棧頂指針。因此，順序棧的類型定義只需將順序表的類型定義中的長度屬性改為top即可。順序棧的類型定義如下（靜態(tài)）

#defineStackSize100typedefstruct{ElemTypedata[StackSize];inttop;}SeqStack;//-----棧的順序存儲表示

-----（動態(tài)）

#defineSTACK_INIT_SIZE100;

#defineSTACKINCREMENT10;

typedefstruct{

SElemType

*base;

SElemType

*top;

intstacksize;

}

SqStack;top=0123450?？諚ｍ斨羔榯op,指向?qū)嶋H棧頂后的空位置，初值為0top123450進(jìn)棧Atop出棧棧滿BCDEF設(shè)數(shù)組維數(shù)為Mtop=0,?？眨藭r出棧，則下溢（underflow)top=M,棧滿，此時入棧，則上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop?？諚ｍ攖op的值為下一個將要進(jìn)棧的元素下標(biāo)。

設(shè)S是SeqStack類型的指針變量。若棧底位置在向量的低端，即s–>data[0]是棧底元素，那么棧頂指針s–>top是正向增加的，即進(jìn)棧時需將s–>top加1，退棧時需將s–>top減1。因此，s–>top=0表示空棧，s–>top=stacksize表示棧滿。當(dāng)棧滿時再做進(jìn)棧運(yùn)算必定產(chǎn)生空間溢出，簡稱“上溢”;當(dāng)棧空時再做退棧運(yùn)算也將產(chǎn)生溢出，簡稱“下溢”。上溢是一種出錯狀態(tài)，應(yīng)該設(shè)法避免之；下溢則可能是正?，F(xiàn)象，因?yàn)闂Ｔ诔绦蛑惺褂脮r，其初態(tài)或終態(tài)都是空棧，所以下溢常常用來作為程序控制轉(zhuǎn)移的條件。1、置空棧

voidinitstack(seqstack*s){s–>top=0;}2、判斷?？?/p>

intstackempty(seqstack*s){return(s–>top==0);}3、判斷棧滿

intstackfull(seqstack*s){return(s–>top==stacksize);}4、進(jìn)棧

voidpush(seqstack*s，ElemTypex){if(stackfull(s))error(“stackoverflow”);s–>data[s–>top++]=x;}5、退棧

voidpop(seqstack*s,ElemType*x){if(stackempty(s))error(“stackunderflow”);s–>top--;*x=s–>data[top];}

6、取棧頂元素ElemTypestacktop(seqstack*s){if(stackempty(s)error(“stackisempty”);returns–>data[s–>top-1];}

3.1.3鏈棧

棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧，它的運(yùn)算是受限的單鏈表，插入和刪除操作僅限制在表頭位置上進(jìn)行。由于只能在鏈表頭部進(jìn)行操作，故鏈表可以沒有必要像單鏈表那樣附加頭結(jié)點(diǎn)。棧頂指針就是鏈表的頭指針。鏈棧的類型說明如下：

棧的鏈接存儲結(jié)構(gòu)鏈棧的結(jié)點(diǎn)定義typedefstructnode{ElemTypedata;structnode*next;}LinkStack;

棧的鏈接表示—鏈?zhǔn)綏ｆ準(zhǔn)綏o棧滿問題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^適合于多棧操作在鏈棧中,棧的基本運(yùn)算算法如下:(1)初始化棧initStack(&L)

建立一個空棧L。實(shí)際上是創(chuàng)建鏈棧的頭結(jié)點(diǎn),并將其next域置為NULL。對應(yīng)算法如下:voidInitStack(ListStack*&L){ L=(ListStack*)malloc(sizeof(ListStack)); L->next=NULL;}

(2)銷毀棧ClearStack(&L)

釋放棧L占用的全部存儲空間。對應(yīng)算法如下:voidClearStack(ListStack*&L){ ListStack*p=L->next; while(p!=NULL) { free(L); L=p; p=p->next; }}

(3)求棧的長度StackLength(L)

從第一個數(shù)據(jù)結(jié)點(diǎn)開始掃描單鏈表,用i記錄訪問的數(shù)據(jù)結(jié)點(diǎn)個數(shù),最后返回i值。對應(yīng)算法如下:intStackLength(ListStack*L){ inti=0; ListStack*p; p=L->next; while(p!=NULL) {i++;p=p->next;} return(i);}

(4)判斷棧是否為空StackEmpty(L)

棧L為空的條件是L->next==NULL,即單鏈表中沒有數(shù)據(jù)結(jié)點(diǎn)。對應(yīng)算法如下:intStackEmpty(ListStack*L){ return(L->next==NULL);}

(5)進(jìn)棧Push(&L,e)

將新數(shù)據(jù)結(jié)點(diǎn)插入到頭結(jié)點(diǎn)之后。對應(yīng)算法如下:voidPush(ListStack*&L,ElemTypee){ ListStack*p; p=(ListStack*)malloc(sizeof(ListStack)); p->data=e; p->next=L->next; /*插入*p結(jié)點(diǎn)作為第一個數(shù)據(jù)結(jié)點(diǎn)*/ L->next=p;}

(6)出棧Pop(&L,&e)

在棧不為空的條件下,將頭結(jié)點(diǎn)后繼數(shù)據(jù)結(jié)點(diǎn)的數(shù)據(jù)域賦給e,然后將其刪除。對應(yīng)算法如下:intPop(ListStack*&L,ElemType&e){ ListStack*p; if(L->next==NULL)return0;/*?？盏那闆r*/ p=L->next; /*p指向第一個數(shù)據(jù)結(jié)點(diǎn)*/ e=p->data; L->next=p->next; free(p); return1;}

(7)取棧頂元素GetTop(L)

在棧不為空的條件下,將頭結(jié)點(diǎn)后繼數(shù)據(jù)結(jié)點(diǎn)的數(shù)據(jù)域賦給e。對應(yīng)算法如下:

intGetTop(ListStack*L,ElemType&e){ if(L->next==NULL)return0; /*?？盏那闆r*/ e=L->next->data; return1;}

(8)顯示棧中元素DispStack(L)

從第一個數(shù)據(jù)結(jié)點(diǎn)開始掃描單鏈表,并輸出當(dāng)前訪問結(jié)點(diǎn)的數(shù)據(jù)域值。對應(yīng)算法如下:voidDispStack(ListStack*L){ ListStack*p=L->next; while(p!=NULL) { printf("%c",p->data); p=p->next; } printf("\n");}3.2棧的應(yīng)用舉例

由于棧結(jié)構(gòu)具有的后進(jìn)先出的固有特性，致使棧成為程序設(shè)計(jì)中常用的工具。以下是幾個棧應(yīng)用的例子。一、棧的應(yīng)用舉例-----數(shù)制轉(zhuǎn)換十進(jìn)制N和其它進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問題,其解決方法很多,其中一個簡單算法基于下列原理:N=(ndivd)*d+nmodd(其中:div為整除運(yùn)算,mod為求余運(yùn)算)

例如(1348)10=(2504)8，其運(yùn)算過程如下：

nndiv8nmod8134816841682102125202

voidconversion(){initstack(s);scanf(“%d”,&n);while(n){push(s,n%8);n=n/8;}while(!Stackempty(s)){pop(s,e);printf(“%d”,e);}}二、括號匹配的檢驗(yàn)假設(shè)在表達(dá)式中（［］（））或［（［］［］）］等為正確的格式，［（］）或（［（））或（（）］)均為不正確的格式。則檢驗(yàn)括號是否匹配的方法可用“期待的急迫程度”這個概念來描述。分析可能出現(xiàn)的不匹配的情況:到來的右括弧并非是所“期待”的；例如：考慮下列括號序列：

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

，否則表明不匹配。3）表達(dá)式檢驗(yàn)結(jié)束時，若?？眨瑒t表明表達(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;…...三、行編輯程序問題如何實(shí)現(xiàn)？“每接受一個字符即存入存儲器”?

并不恰當(dāng)！

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

在用戶輸入一行的過程中，允許用戶輸入出差錯，并在發(fā)現(xiàn)有誤時可以及時更正。合理的作法是：假設(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();//從終端接收下一個字符

}ClearStack(S);//重置S為空棧if(ch!=EOF)ch=getchar();while(ch!=EOF){//EOF為全文結(jié)束符將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)；(這是棧應(yīng)用的典型例子)

這里，表達(dá)式求值的算法是“算符優(yōu)先法”。例如：3*（7–2）（1）要正確求值，首先了解算術(shù)四則運(yùn)算的規(guī)則：

a.

從左算到右

b.先乘除，后加減

c.先括號內(nèi)，后括號外由此，此表達(dá)式的計(jì)算順序?yàn)椋?/p>

3*（7–2）=3*5=15四、棧的應(yīng)用舉例－－表達(dá)式計(jì)算（2）根據(jù)上述三條運(yùn)算規(guī)則，在運(yùn)算的每一步中，對任意相繼出現(xiàn)的算符

1和

2

，都要比較優(yōu)先權(quán)關(guān)系。算符優(yōu)先法所依據(jù)的算符間的優(yōu)先關(guān)系見教材P53表3.1

（是提供給計(jì)算機(jī)用的表?。５膽?yīng)用（表達(dá)式求值）（3）算法思想：設(shè)定兩棧：操作符棧OPTR，操作數(shù)棧OPND棧初始化：設(shè)操作數(shù)棧OPND為空；操作符棧OPTR的棧底元素為表達(dá)式起始符‘#’；依次讀入字符：是操作數(shù)則入OPND棧，是操作符則要判斷：

if操作符<棧頂元素，則退棧、計(jì)算，結(jié)果壓入OPND棧；

操作符=棧頂元素且不為‘#’，脫括號（彈出左括號）；

操作符>棧頂元素，壓入OPTR棧。OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,’3’)

#*(7-2)#3#Push(optr,’*’)#,*3(7-2)#Push(optr,’(’)#,*,(37-2)#Push(opnd,’7’)#,*,(3,7-2)#Push(optr,’-’)#,*,(,－3,72)#Push(opnd,’2’)#,*,(,－3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)StatusEvaluateExpression(OperandType&result){InitStack(OPND);InitStack(OPTR);Push(OPTR,’#’);c=getchar();while((c!=‘#’)&&(GetTop(OPTR)!=‘#’)){if(!In(c,OP){Push(OPND,c);c=getchar();}elseswitch(compare(c,GetTop(OPTR))){case‘>’:Push(OPTR,c);c=getchar();break;case‘=’:Pop(OPTR);c=getchar();break;

case‘<’:op=Pop(OPTR);b=Pop();a=Pop();//退棧

result=Operate(a,op,b);Push(OPND,result);c=getchar();break;}//switch}//whileresult=GetTop(OPND);}//EvaluateExpression此函數(shù)在哪里？五、實(shí)現(xiàn)遞歸將所有的實(shí)在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存；為被調(diào)用函數(shù)的局部變量分配存儲區(qū)；將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。

當(dāng)在一個函數(shù)的運(yùn)行期間調(diào)用另一個函數(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ù)：多個函數(shù)嵌套調(diào)用的規(guī)則是：此時的內(nèi)存管理實(shí)行“棧式管理”后調(diào)用先返回！例如：voidmain(){voida(){voidb(){……