第3章棧和隊列

3.1棧

3.2隊列

3.3本章小結(jié)第3章棧和隊列3.1棧3.2隊列3.3本章小結(jié)13.1.1棧的定義

3.1.2棧的順序存儲結(jié)構(gòu)及其基本運算實現(xiàn)3.1.3棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本運算的實現(xiàn)3.1.4棧的應(yīng)用例子3.1棧

3.1.1棧的定義3.1棧2

棧是一種只能在一端進行插入或刪除操作的線性表。表中允許進行插入、刪除操作的一端稱為棧頂。

棧頂?shù)漠?dāng)前位置是動態(tài)的,棧頂?shù)漠?dāng)前位置由一個稱為棧頂指針的位置指示器指示。表的另一端稱為棧底。

當(dāng)棧中沒有數(shù)據(jù)元素時,稱為空棧。棧的插入操作通常稱為進?；蛉霔?棧的刪除操作通常稱為退?；虺鰲?。3.1.1棧的定義

棧是一種只能在一端進行插入或刪除操作的線性表3圖3-1順序棧示意圖a1a2aian????bottomtop進棧（push）出棧(pop)圖3-1順序棧示意圖a1a2aian????botto4順序棧進棧和出棧示意圖順序棧進棧和出棧示意圖5棧的幾種基本運算如下:(1)初始化棧InitStack(&s):構(gòu)造一個空棧s。(2)銷毀棧ClearStack(&s):釋放棧s占用的存儲空間。(3)求棧的長度StackLength(s):返回棧s中的元素個數(shù)。(4)判斷棧是否為空StackEmpty(s):若棧s為空,則返回真；否則返回假。棧的幾種基本運算如下:6(5)進棧Push(&S,e):將元素e插入到棧s中作為棧頂元素。(6)出棧Pop(&s,&e):從棧s中退出棧頂元素,并將其值賦給e。(7)取棧頂元素GetTop(s,&e):返回當(dāng)前的棧頂元素,并將其值賦給e。(8)顯示棧中元素DispStack(s):從棧頂?shù)綏５醉樞蝻@示棧中所有元素。(5)進棧Push(&S,e):將元素e插入到棧s中作為73.1.2棧的順序存儲結(jié)構(gòu)及其基本運算實現(xiàn)

假設(shè)棧的元素個數(shù)最大不超過正整數(shù)MaxSize,所有的元素都具有同一數(shù)據(jù)類型ElemType,則可用下列方式來定義棧類型SqStack:typedefstruct{ElemTypedata[MaxSize]；inttop； /*棧指針*/}SqStack；3.1.2棧的順序存儲結(jié)構(gòu)及其基本運算實現(xiàn)8在順序棧中實現(xiàn)棧的基本運算算法:(1)初始化棧initStack(&s)建立一個新的空棧s,實際上是將棧頂指針指向-1即可。對應(yīng)算法如下:voidInitStack(SqStack*&s){s=(SqStack*)malloc(sizeof(SqStack));s->top=-1;}在順序棧中實現(xiàn)棧的基本運算算法:9順序棧進棧和出棧示意圖順序棧進棧和出棧示意圖10(2)銷毀棧ClearStack(&s)釋放棧s占用的存儲空間。對應(yīng)算法如下:voidClearStack(SqStack*&s){ free(s);}(2)銷毀棧ClearStack(&s)11(3)求棧的長度StackLength(s)返回棧s中的元素個數(shù),即棧指針加1的結(jié)果。對應(yīng)算法如下:intStackLength(SqStack*s){ return(s->top+1);}(3)求棧的長度StackLength(s)12

(4)判斷棧是否為空StackEmpty(s)棧S為空的條件是s->top==-1。對應(yīng)算法如下:intStackEmpty(SqStack*s){ return(s->top==-1);}(4)判斷棧是否為空StackEmpty(s)13(5)進棧Push(&s,e)在棧不滿的條件下,先將棧指針增1,然后在該位置上插入元素e。對應(yīng)算法如下:intPush(SqStack*&s,ElemTypee){ if(s->top==MaxSize-1)return0; /*棧滿的情況,即棧上溢出*/ s->top++; s->data[s->top]=e; return1;}(5)進棧Push(&s,e)14(6)出棧Pop(&s,&e)在棧不為空的條件下,先將棧頂元素賦給e,然后將棧指針減1。對應(yīng)算法如下:intPop(SqStack*&s,ElemType&e){if(s->top==-1)return0; /*棧為空的情況,即棧下溢出*/ e=s->data[s->top]; s->top--; return1;}(6)出棧Pop(&s,&e)15

(7)取棧頂元素GetTop(s)在棧不為空的條件下,將棧頂元素賦給e。對應(yīng)算法如下:intGetTop(SqStack*s,ElemType&e){if(s->top==-1)return0; /*棧為空的情況,即棧下溢出*/ e=s->data[s->top]; return1;}(7)取棧頂元素GetTop(s)16(8)顯示棧中元素DispStack(s)從棧頂?shù)綏５醉樞蝻@示棧中所有元素。對應(yīng)算法如下:voidDispStack(SqStack*s){ inti; for(i=s->top;i>=0;i--) printf("%c",s->data[i]); printf("\n");}(8)顯示棧中元素DispStack(s)17例3.4編寫一個算法利用順序棧判斷一個字符串是否是對稱串。所謂對稱串是指從左向右讀和從右向左讀的序列相同。解intsymmetry(ElemTypestr[]){inti;ElemTypee;SqStack*st;InitStack(st);For(i=0;str[i]!=‘\0’;i++);Push(st,str[i]);For(i=0;str[i]!=‘\0’;i++);{Pop(st,e);if(str[i]!=e)Return(0);}Return(1);}例3.4編寫一個算法利用順序棧判斷一個字符串是否是對稱串。183.1.3棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本運算的實現(xiàn)采用鏈?zhǔn)酱鎯Φ臈７Q為鏈棧,這里采用單鏈表實現(xiàn)。鏈棧的優(yōu)點是不存在棧滿上溢的情況。我們規(guī)定棧的所有操作都是在單鏈表的表頭進行的,下圖是頭結(jié)點為*lhead的鏈棧,第一個數(shù)據(jù)結(jié)點是棧頂結(jié)點,最后一個結(jié)點是棧底結(jié)點。棧中元素自棧頂?shù)綏５滓来问莂1、a2、…、an。3.1.3棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本運算的實現(xiàn)19鏈棧示意圖鏈棧示意圖20鏈棧中數(shù)據(jù)結(jié)點的類型LiStack定義如下:typedefstructlinknode{ElemTypedata; /*數(shù)據(jù)域*/structlinknode*next; /*指針域*/}LiStack;鏈棧中數(shù)據(jù)結(jié)點的類型LiStack定義如下:21在鏈棧中,棧的基本運算算法如下:(1)初始化棧initStack(&s)建立一個空棧s。實際上是創(chuàng)建鏈棧的頭結(jié)點,并將其next域置為NULL。對應(yīng)算法如下:voidInitStack(LiStack*&s){s=(LiStack*)malloc(sizeof(LiStack));s->next=NULL;}^s在鏈棧中,棧的基本運算算法如下:^s22(2)銷毀棧ClearStack(&s)釋放棧s占用的全部存儲空間。對應(yīng)算法:voidClearStack(LiStack*&s){ LiStack*p=s;*q=s->next; while(q!=NULL) { free(p); p=q; q=p->next; }free(p);}(2)銷毀棧ClearStack(&s)23(3)求棧的長度StackLength(s)從第一個數(shù)據(jù)結(jié)點開始掃描單鏈表,用n記錄訪問的數(shù)據(jù)結(jié)點個數(shù),最后返回n值。對應(yīng)算法如下:intStackLength(LiStack*s){ intn=0; LiStack*p; p=s->next; while(p!=NULL) {n++;p=p->next;} return(n);}(3)求棧的長度StackLength(s)24(4)判斷棧是否為空StackEmpty(s)棧S為空的條件是s->next==NULL,即單鏈表中沒有數(shù)據(jù)結(jié)點。對應(yīng)算法如下:intStackEmpty(LiStack*s){ return(s->next==NULL);}^s(4)判斷棧是否為空StackEmpty(s)^s25(5)進棧Push(&s,e)將新數(shù)據(jù)結(jié)點插入到頭結(jié)點之后。對應(yīng)算法如下:voidPush(LiStack*&s,ElemTypee){LiStack*p;p=(LiStack*)malloc(sizeof(LiStack));p->data=e;p->next=s->next;/*插入*p結(jié)點作為第一個數(shù)據(jù)結(jié)點*/s->next=p;}(5)進棧Push(&s,e)26(6)出棧Pop(&s,&e)在棧不為空的條件下,將頭結(jié)點后繼數(shù)據(jù)結(jié)點的數(shù)據(jù)域賦給e,然后將其刪除。對應(yīng)算法如下:intPop(LiStack*&s,ElemType&e){ LiStack*p; if(s->next==NULL)return0;/*?？盏那闆r*/ p=s->next; /*p指向第一個數(shù)據(jù)結(jié)點*/ e=p->data; s->next=p->next; free(p); return1;}(6)出棧Pop(&s,&e)27(7)取棧頂元素GetTop(s)在棧不為空的條件下,將頭結(jié)點后繼數(shù)據(jù)結(jié)點的數(shù)據(jù)域賦給e。對應(yīng)算法如下:intGetTop(LiStack*s,ElemType&e){ if(s->next==NULL)return0;/*?？盏那闆r*/ e=s->next->data; return1;}(7)取棧頂元素GetTop(s)28(8)顯示棧中元素DispStack(s)從第一個數(shù)據(jù)結(jié)點開始掃描單鏈表,并輸出當(dāng)前訪問結(jié)點的數(shù)據(jù)域值。對應(yīng)算法如下:voidDispStack(LiStack*s){LiStack*p=s->next; while(p!=NULL) { printf("%c",p->data); p=p->next; } printf("\n");}(8)顯示棧中元素DispStack(s)29例3.5編寫一個算法判斷輸入的表達式中括號是否匹配（假設(shè)只有左、右圓括號）。解:intMatch(charexp[],intn){inti=0;chare;SqStack*st;InitStack(st);while(i<n){if(exp[i])==‘（’;Push(st,exp[i]);elseif(exp[i]==‘)’){if(GetTop(st,e)==1){if(e!=‘(’)return(0)elsePop(st,e);}elsereturn(0);}i++;}if(StackEmpty(st)==1)return(1);elseReturn(0);}例3.5編寫一個算法判斷輸入的表達式中括號是否匹配（假設(shè)只303.1.4棧的應(yīng)用例子1.表達式求值這里限定的表達式求值問題是:用戶輸入一個包含“+”、“-”、“*”、“/”、正整數(shù)和圓括號的合法數(shù)學(xué)表達式,計算該表達式的運算結(jié)果。3.1.4棧的應(yīng)用例子31在程序語言中,運算符位于兩個操作數(shù)中間的表達式稱為中綴表達式。例如：1+2*3就是一個中綴表達式,中綴表達式是最常用的一種表達式方式。對中綴表達式的運算一般遵循“先乘除,后加減,從左到右計算,先括號內(nèi),后括號外”的規(guī)則。因此,中綴表達式不僅要依賴運算符優(yōu)先級,而且還要處理括號。在程序語言中,運算符位于兩個操作數(shù)中間的表達式稱為中32

所謂后綴表達式,就是運算符在操作數(shù)的后面,如1+2*3的后綴表達式為123*+。在后綴表達式中已考慮了運算符的優(yōu)先級,沒有括號,只有操作數(shù)和運算符。對后綴表達式求值過程是:從左到右讀入后綴表達式,若讀入的是一個操作數(shù),就將它入數(shù)值棧,若讀入的是一個運算符op,就從數(shù)值棧中連續(xù)出棧兩個元素(兩個操作數(shù)),假設(shè)為x和y,計算xopy之值,并將計算結(jié)果入數(shù)值棧；對整個后綴表達式讀入結(jié)束時,棧頂元素就是計算結(jié)果。

所謂后綴表達式,就是運算符在操作數(shù)的后面,如1+2*33

算術(shù)表達式求值過程是:先將算術(shù)表達式轉(zhuǎn)換成后綴表達式,然后對該后綴表達式求值。假設(shè)算術(shù)表達式中的符號以字符形式由鍵盤輸入,并存放在字符型數(shù)組exp中,其后綴表達式存放在字符型數(shù)組postexp中.在將算術(shù)表達式轉(zhuǎn)換成后綴表達式的過程中用一個字符型數(shù)組op作為棧。將算術(shù)表達式轉(zhuǎn)換成后綴表示的方法如下:算術(shù)表達式求值過程是:先將算術(shù)表達式轉(zhuǎn)換成后綴表達式34while(從exp讀取字符ch,ch!='\0'){若ch為數(shù)字,將后續(xù)的所有數(shù)字均依次存放到postexp中,并以字符“#”標(biāo)志數(shù)值串結(jié)束。若ch為左括號“(”,則將此括號進棧到運算符棧op中。若ch為右括號“)”,則將運算符棧op中左括號“(”以前的運算符依次出棧并存放到postexp中,然后將左括號“(”刪除。若ch運算符優(yōu)先級小于或等于op棧頂運算符的優(yōu)先級(除棧頂運算符為“(”外),則依次出棧并存入到postexp中,然后將ch進棧。}中綴表達式后綴表達式while(從exp讀取字符ch,ch!='\0')中綴表35若字符串exp掃描完畢,則將運算棧op中的所有運算符依次出棧并存放到postexp中。最后得到后綴表達式postexp。若字符串exp掃描完畢,則將運算棧op中的所有運算符36對于表達式“(56-20)/(4+2)”,其轉(zhuǎn)換成后綴表達式的過程如下：exp操作過程oppostexp(56-20)/(4+2)遇到ch為“(”,將此括號進棧op。(

56-20)/(4+2)遇到ch為數(shù)字,將56存入postexp中,并插入一個字符“#”。(56#-20)/(4+2)遇到ch為“-”,由于op中“(”以前沒有字符,則直接將ch進棧op中。(-56#20)/(4+2)遇到ch為數(shù)字,將20#存入數(shù)組exp中。(-56#20#對于表達式“(56-20)/(4+2)”,其轉(zhuǎn)換成后37exp操作過程oppostexp)/(4+2)遇到ch為“)”,則將棧op中“(”以前的字符依次出棧并存入postexp中,然后將“(”刪除。

56#20#-/(4+2)遇到ch為“/”,將將ch進棧op中。/56#20#-(4+2)遇到ch為“(”,將此括號進棧op中。/(56#20#-4+2)遇到ch為數(shù)字,將4#存入數(shù)組postexp中。/(56#20#-4#exp操作過程oppostexp)/(4+2)遇到ch為“)38exp操作過程oppostexp+2)遇到ch為“+”,由于op棧頂運算符為“(”,則直接將ch進棧op中。/(+56#20#-4#2)遇到ch為數(shù)字,將2#存入postexp中。/(+56#20#-4#2#)遇到ch為“)”,則將棧op中“(”以前的字符依次出棧并存放到postexp中,然后將“(”出棧。/56#20#-4#2#+

exp掃描完畢,則將棧op中的所有運算符依次彈出并存放到postexp中,得到后綴表達式。

56#20#-4#2#+/exp操作過程oppostexp+2)遇到ch為“+”,由于39將算術(shù)表達式exp轉(zhuǎn)換成后綴表達式postexpvoidtrans(charexp[],charpostexp[]){ struct {chardata[MaxSize];/*存放運算符*/ inttop; /*棧指針*/ }op; /*定義運算符棧*/ charch; inti=0,t=0; /*i作為exp的下標(biāo),t作為postexp的下標(biāo)*/ op.top=-1; ch=exp[i];i++;將算術(shù)表達式exp轉(zhuǎn)換成后綴表達式postexp40while(ch!='\0')/*exp表達式未掃描完時循環(huán)*/{switch(ch){case'(': /*判定為左括號*/op.top++;

op.data[op.top]=ch;break; case')': /*判定為右括號*/ while(op.data[op.top]!='(') {postexp[t]=op.data[op.top];op.top--;t++;} op.top--;break;

while(ch!='\0')/*exp表達式未掃描完時循環(huán)41case'+':case'-': /*判定為加或減號*/while(op.top!=-1&&op.data[op.top]!='('){postexp[t]=op.data[op.top];op.top--;t++;}op.top++;op.data[op.top]=ch;break;case'*':case'/':/*判定為'*'或'/'號*/ while(op.data[op.top]=='*'||op.data[op.top]=='/') {postexp[t]=op.data[op.top];op.top--;t++;} op.top++;op.data[op.top]=ch;break;case'+':case'-': /*判定為加或減號42case'':break; /*過濾掉空格*/default:while(ch>='0'&&ch<='9')/*判定為數(shù)字*/{postexp[t]=ch;t++; ch=exp[i];i++;}i--;postexp[t]='#';t++;/*用#標(biāo)識一個數(shù)值串結(jié)束*/}ch=exp[i];i++;}case'':break; /*過濾掉空格*/43while(op.top!=-1)/*此時exp掃描完畢,棧不空時循環(huán)*/{postexp[t]=op.data[op.top];t++;op.top--;}postexp[t]='\0';/*給postexp表達式添加結(jié)束標(biāo)識*/}while(op.top!=-1)/*此時exp掃描44

下面對后綴表達式求值。在后綴表達式求值算法中要用到一個數(shù)值棧st,該算法實現(xiàn)過程如下:后綴表達式存放在字符型數(shù)組postexp中,從頭開始依次掃描這個后綴表達式,當(dāng)遇到運算數(shù)時,就把它插入到數(shù)值棧st中；當(dāng)遇到運算符時,就執(zhí)行兩次退棧,并根據(jù)該運算符對退棧的數(shù)值進行相應(yīng)的運算,再把結(jié)果入棧st。重復(fù)上述過程,直至后綴表達式postexp掃描完畢,此時數(shù)值棧st中棧頂?shù)臄?shù)值即為表達式的值。

下面對后綴表達式求值。在后綴表達式求值算法中要用到一個45while(從postexp讀取字符ch,ch!='\0'){若ch為數(shù)字,將后續(xù)的所有數(shù)字構(gòu)成一個整數(shù)存放到數(shù)值棧st中。若ch為“+”,則從數(shù)值棧st中退棧兩個運算數(shù),相加后進棧st中。若ch為“－”,則從數(shù)值棧st中退棧兩個運算數(shù),相減后進棧st中。若ch為“*”,則從數(shù)值棧st中退棧兩個運算數(shù),相乘后進棧st中。若ch為“/”,則從數(shù)值棧st中退棧兩個運算數(shù),相除后進棧st中(若除數(shù)為零,則提示相應(yīng)的錯誤信息)。}若字符串postexp掃描完畢,則數(shù)值棧op中的棧頂元素就是表達式的值。對后綴表達式求值while(從postexp讀取字符ch,ch!='\0'46對于后綴表達式“56#20#-4#2#+/”的求值過程如下：

postexp操作過程st56#20#-4#2#+/遇到56#,將56進棧。5620#-4#2#+/遇到20#,將20進棧。56,20-4#2#+/遇到“-”,出棧兩次,將56-20=36進棧。364#2#+/遇到4#,將4進棧。36,42#+/遇到2#,將2進棧。36,4,2+/遇到“+”,出棧兩次,將4+2=6進棧。36,6/遇到“/”,出棧兩次,將36/6=6進棧。6

postexp掃描完畢,算法結(jié)束,棧頂?shù)脑?即為所求。

對于后綴表達式“56#20#-4#2#+/”的求值過程如下：47floatcompvalue(charpostexp[])/*計算后綴表達式的值*/{struct{floatdata[MaxSize];/*存放數(shù)值*/inttop; /*棧指針*/}st; /*定義數(shù)值棧*/floatd;charch;intt=0;/*t作為postexp的下標(biāo)*/st.top=-1;ch=postexp[t];t++;

floatcompvalue(charpostexp[]48while(ch!='\0')/*postexp字符串未掃描完循環(huán)*/{switch(ch){case'+':st.data[st.top-1]=st.data[st.top-1]+st.data[st.top]; st.top--;break;case'-':st.data[st.top-1]=st.data[st.top-1]-st.data[st.top]; st.top--;break;case'*':st.data[st.top-1]=st.data[st.top-1]*st.data[st.top]; st.top--;break;while(ch!='\0')/*postexp字符串未掃描49case'/':if(st.data[st.top]!=0) st.data[st.top-1]=st.data[st.top-1]/st.data[st.top]; else{printf("\n\t除零錯誤!\n"); exit(0); /*異常退出*/ }