數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)集-第三章和隊列3章棧

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

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

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

3、 隊列的順序存儲表示；隊列的鏈接存儲表示；

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

二、教學(xué)要求：

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

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

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

第三章棧和隊列棧和隊列是兩種特殊的線性表，是操作受限的線性表，稱限定性數(shù)據(jù)結(jié)構(gòu)。棧棧的應(yīng)用隊列隊列的應(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表。

棧的基本操作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ī)系2001年考研題（程序設(shè)計基礎(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)闂５孜恢檬枪潭ú蛔兊模钥梢詫５孜恢迷O(shè)置在數(shù)組的兩端的任何一個端點(diǎn)；棧頂位置是隨著進(jìn)棧和退棧操作而變化的，故需用一個整型變量top來指示當(dāng)前棧頂?shù)奈恢?，通常稱top為棧頂指針。因此，順序棧的類型定義只需將順序表的類型定義中的長度屬性改為top即可。順序棧的類型定義如下：

#defineStackSize100typedefstruct{ElemTypedata[StackSize];inttop;}SeqStack;top=0123450?？諚ｍ斨羔榯op,指向?qū)嶋H棧頂后的空位置，初值為0top123450進(jìn)棧Atop出棧棧滿BCDEF設(shè)數(shù)組維數(shù)為Mtop=0,?？?，此時出棧，則下溢（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)?？諘r再做退棧運(yùn)算也將產(chǎn)生溢出，簡稱“下溢”。上溢是一種出錯狀態(tài)，應(yīng)該設(shè)法避免之；下溢則可能是正常現(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];}

順序棧的操作演示棧的共享存儲單元有時，一個程序設(shè)計中，需要使用多個同一類型的棧,這時候，可能會產(chǎn)生一個?？臻g過小，容量發(fā)生溢出，而另一個?？臻g過大，造成大量存儲單元浪費(fèi)的現(xiàn)象。為了充分利用各個棧的存儲空間，這時可以采用多個棧共享存儲單元，即給多個棧分配一個足夠大的存儲空間，讓多個棧實(shí)現(xiàn)存儲空間優(yōu)勢互補(bǔ)。兩個共享存儲單元順序棧的操作演示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)綏５臈ｍ斣阪滎^適合于多棧操作鏈棧的進(jìn)棧算法LinkStack*PUSHLSTACK(LinkStack*top,ElemTypex){LinkStack*p;p＝malloc(sizeof(LinkStack));p->data＝x;p->next＝top;returnp;}鏈棧的出棧算法linkstack*POPLSTACK(linkstack*top,ElemType*datap){linkstack*p;if(top==NULL){printf(“underflow\n”);returnNULL;}else{*datap＝top->data;p＝top;top＝top->next;free(p);returntop;}}

3.2棧的應(yīng)用舉例

由于棧結(jié)構(gòu)具有的后進(jìn)先出的固有特性，致使棧成為程序設(shè)計中常用的工具。以下是幾個棧應(yīng)用的例子。一、棧的應(yīng)用舉例-----數(shù)制轉(zhuǎn)換

十進(jìn)制N和其它進(jìn)制數(shù)的轉(zhuǎn)換是計算機(jī)實(shí)現(xiàn)計算的基本問題,其解決方法很多,其中一個簡單算法基于下列原理:N=(ndivd)*d+nmodd(其中:div為整除運(yùn)算,mod為求余運(yùn)算)

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

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īng)用舉例－－文字編輯器seqstacks;EDIT(){charc;SETNULL(&s);c＝getchar();while(c!=‘*’){if(c==‘#’)POP(&s);elseif(c==‘@’)SETNULL(&s);elsePUSH(&s,c);c＝getchar();}}}(這是棧應(yīng)用的典型例子)

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

a.

從左算到右

b.先乘除，后加減

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

3*（7–2）=3*5=15三、棧的應(yīng)用舉例－－表達(dá)式計算（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ī)用的表?。５膽?yīng)用（表達(dá)式求值）（3）算法思想：設(shè)定兩棧：操作符棧OPTR，操作數(shù)棧OPND棧初始化：設(shè)操作數(shù)棧OPND為空；操作符棧OPTR的棧底元素為表達(dá)式起始符‘#’；依次讀入字符：是操作數(shù)則入OPND棧，是操作符則要判斷：

if

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

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

操作符>棧頂元素，壓入OPTR棧。棧的應(yīng)用（表達(dá)式求值）棧的應(yīng)用（表達(dá)式求值）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‘>’:temat=Pop(OPTR);b=Pop();a=Pop();

result=Operate(a,temat,b);Push(OPND,result);c=getchar();break;}//switch}//whileresult=GetTop(OPND);}//EvaluateExpression例4漢諾儀（Hanoi）塔傳說在創(chuàng)世紀(jì)時，在一個叫Brahma的寺廟里，有三個柱子，其中一柱上有64個盤子從小到大依次疊放，僧侶的工作是將這64個盤子從一根柱子移到另一個柱子上。

移動時的規(guī)則：

每次只能移動一個盤子；只能小盤子在大盤子上面；可以使用任一柱子。當(dāng)工作做完之后，就