第三章棧和隊(duì)列要點(diǎn)本章主題：棧和隊(duì)列的應(yīng)用教學(xué)目的：1、理解棧和隊(duì)列的定義和特點(diǎn)2、<重點(diǎn)>熟練掌握棧類型的兩種實(shí)現(xiàn)方法。3、

<重點(diǎn)>熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法。

4、<難點(diǎn)>能在相應(yīng)的應(yīng)用問題中正確選用它們。3.1棧

1.棧的定義棧：是限定僅在表尾進(jìn)行插入或刪除操作的線性表。約定稱表尾端為棧頂(top),表頭端為棧底(bottom)。

棧的特點(diǎn)：后進(jìn)先出（LIFO:lastinfirstout）棧又稱為“后進(jìn)先出”的線性表，簡(jiǎn)稱LIFO表。

2.棧的基本操作

InitStack(&S)

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

初始條件：棧S已存在。

操作結(jié)果：棧S被撤銷，即釋放S占用的存儲(chǔ)空間。ClearStack(&S)

初始條件：棧S已存在。

操作結(jié)果：將S清為空棧。StackEmpty(S)初始條件：棧S已存在。

操作結(jié)果：若棧S為空棧，則返回TRUE，否則FALSE。StackLength(S)操作結(jié)果：獲取S的元素個(gè)數(shù)，即棧的長(zhǎng)度。

2.棧的基本操作

GetTop(S,&e)初始條件：棧S已存在且非空。

操作結(jié)果：用e返回S的棧頂元素。Push(&S,e)初始條件：棧S已存在。

操作結(jié)果：插入元素e為新的棧頂元素。Pop(&S,&e)初始條件：棧S已存在且非空。

操作結(jié)果：刪除S的棧頂元素，

并用e返回其值。

3、棧的實(shí)現(xiàn)和表示棧的兩種存儲(chǔ)表示方法：順序棧和鏈棧順序棧:棧的順序存儲(chǔ)結(jié)構(gòu)是利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的位置。top=0表示空棧。

一般情況下使用一維數(shù)組實(shí)現(xiàn)順序棧。

#defineMaxSize<存儲(chǔ)數(shù)據(jù)元素的最大個(gè)數(shù)>

typedefstruct{

ElemTypedata[MaxSize];

inttop;

}STACK;缺點(diǎn)：棧在使用過程中所需最大空間的大小很難估計(jì)，初始化設(shè)空棧時(shí)候不應(yīng)該限定棧的最大容量。

順序棧的實(shí)現(xiàn)和表示:#defineSTACK_INIT_SIZE100;//存儲(chǔ)空間初始分配量

#defineSTACKINCREAMENT10;//存儲(chǔ)空間分配增量

typedefstruct{ElemType*base;

ElemType*top;

intstacksize;}SqStack;順序棧的實(shí)現(xiàn)和表示:

int

InitStack(SqStack

*S){//初始化棧,構(gòu)造一個(gè)空棧SS.base=(ElemType

*)malloc(STACK_INT_SIZE*sizeof(ElemType));

if(!S.base)

return

0;//存儲(chǔ)分配失敗

S.top=S.base;

S.stacksize=STACK_INT_SIZE;

return

1;

}

int

Push(SqStack

*S,ElemType

e){//進(jìn)棧，插入元素e為新的棧頂元素if(S.top–S.base>=STACK_INT_SIZE){//棧滿，追加存儲(chǔ)空間

S.base=(ElemType

*)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(ElemType));

if(!S.base)

return

0;//存儲(chǔ)分配失敗

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREAMENT;

}

*S.top=e;

S.top++;

return

1;

}順序棧的實(shí)現(xiàn)和表示:int

Pop(SqStack

*S,ElemType

*e){//出棧,若棧不空，則刪除S的棧頂元素，用e返回其值。if(S.top==S.base)//棧空

return

0;

S.top--;

*e=*(S.top);return1;

}int

GetTop(SqStackS,ElemType*e){//獲取棧頂元素，用e返回棧頂元素

if(S.top==S.base)//棧空

return

0;

*e=*(S.top-1);return1;}鏈棧的實(shí)現(xiàn)和表示:

由于棧的插入刪除操作只能在一端進(jìn)行，而對(duì)于單鏈表來說，在首端插入刪除結(jié)點(diǎn)要比尾端相對(duì)容易一些，所以，將將單鏈表的首端作為棧頂端，即將單鏈表的頭指針作為棧頂指針。棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)類型定義實(shí)現(xiàn)：//-----棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)-----typedefstructSNode{SElemTypedata;

//數(shù)據(jù)域structSNode*next;

//指針域}SNode,*LinkStack;

鏈棧的實(shí)現(xiàn)和表示://操作結(jié)果：構(gòu)造一個(gè)空棧S。StatusInitStack(LinkStack&S){S=(LinkStack)malloc(sizeof(SNode));if(!S)//存儲(chǔ)分配失敗exit(OVERFLOW);//exit(-2)程序異常退出S->next=NULL;S->data=NULL;returnOK;}//InitStack//操作結(jié)果：插入元素e為新的棧頂元素。StatusPush(LinkStack&S,SElemTypee){LinkStackp=(LinkStack)malloc(sizeof(SNode));p->next=S->next;//新結(jié)點(diǎn)指向棧頂p->data=e;S->next=p;//更新棧頂指針printf("插入的棧頂元素：%c\n",e);returnOK;}//Push

鏈棧的實(shí)現(xiàn)和表示://操作結(jié)果：若棧不空，則刪除S的棧頂元素，并用e返回其值；否則返回ERROR。StatusPop(LinkStack&S,SElemType&e){//若1個(gè)元素也沒有：if(S->next==NULL)returnERROR;//若有1個(gè)以上元素e=S->next->data;LinkStackptmp=S->next->next;free(S->next);S->next=ptmp;printf("刪除的棧頂元素：%d\n",e);returnOK;}//Pop

3.2棧的應(yīng)用舉例棧的特點(diǎn)：后進(jìn)先出1、例子---數(shù)制轉(zhuǎn)換十進(jìn)制數(shù)N和其它d進(jìn)制數(shù)的轉(zhuǎn)換，一個(gè)常用的轉(zhuǎn)換方法：N=(Ndivd)*d+Nmodd(div為整除運(yùn)算，mod為求余運(yùn)算)例如（1348）10=（2504）8NNdiv8Nmod8134816841682102125202計(jì)算順序輸出順序voidconversion(){//對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制InitStack(S);//構(gòu)造空棧scanf("%d",&N);while(N)

{Push(S,N%8);//入棧N=N/8;

}while(!StackEmpty(S)){Pop(S,e);//出棧printf("%d",e);}printf("\n");DestroyStack(S);//銷毀棧}//conversion算法3.12、括號(hào)匹配的檢測(cè)假設(shè)表達(dá)式中允許包含兩種括號(hào)：圓括號(hào)和方括號(hào)，其嵌套順序隨意，即([]())或者[([][])]等為正確的格式，[(]或（[()）為不正確表達(dá)式。檢驗(yàn)表達(dá)式中的括號(hào)格式。

考慮：利用棧結(jié)構(gòu)保存每個(gè)出現(xiàn)的左括號(hào)，當(dāng)遇到右括號(hào)的時(shí)候，則和棧頂元素檢驗(yàn)是否匹配，匹配則彈出棧頂元素，不匹配則出錯(cuò)，格式不正確。算法設(shè)計(jì)思想：（1）凡出現(xiàn)左括號(hào)，則進(jìn)棧；（2）凡出現(xiàn)右括號(hào)，首先檢查棧是否為空，若棧空，則表明“右括號(hào)”多了，

否則和棧頂元素比較，若匹配，則“左括號(hào)出棧”，

否則，不匹配（3）表達(dá)式檢驗(yàn)結(jié)束時(shí)，若棧空，則匹配正確，否則，表明左括號(hào)多了voidcheck()

{//檢驗(yàn)表達(dá)式中括號(hào)()、[]是否配對(duì)

InitStack(S);gets(expression);while(expression[i]!='\0'){switch(expression[i]){case‘左括號(hào)’：Push(S,expression[i]);break;//當(dāng)遇見左符號(hào)時(shí)壓入棧中

case'右括號(hào)'://當(dāng)遇見右符號(hào)時(shí)從棧中彈出棧頂符號(hào)//進(jìn)行匹配if(!StackEmpty(S))

{Pop(S,e);if(!(e=='('&&expression[i]==')'||e=='['&&expression[i]==']'))//匹配成功：繼續(xù)讀入下一個(gè)字符//匹配失敗：立即停止，并報(bào)錯(cuò)exit(ERROR);}

elseexit(ERROR);default:break;//當(dāng)遇見普通字符時(shí)忽略

}i++;}if(StackEmpty(S))//成功：所有字符掃描完畢，且