棧的順序存儲(chǔ)結(jié)構(gòu)順序棧

1、3. 2棧的順序存儲(chǔ)結(jié)構(gòu)-順序棧棧的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱(chēng)順序棧，它是運(yùn)算受限的順序表。順序棧的存儲(chǔ)結(jié)構(gòu)是：利 用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的位置。3. 2. 1順序棧的類(lèi)型定義類(lèi)似于順序表，用一維數(shù)組描述順序棧中的數(shù)據(jù)元素的存儲(chǔ)區(qū)域，并預(yù)設(shè)一個(gè) 數(shù)組的最大空間。描述順序棧的通常的習(xí)慣做法是以top=0表示空棧，鑒于C語(yǔ)言 中數(shù)組的下標(biāo)約定是從0開(kāi)始，則當(dāng)以C作描述語(yǔ)言時(shí)，如此設(shè)定會(huì)帶來(lái)很大不便； 另一方面，由于棧在使用過(guò)程中所需最大空間的大小很難估計(jì)，因此，一般來(lái)說(shuō)， 在初始化設(shè)空棧時(shí)不應(yīng)限定棧的最大容量。一個(gè)較合理的做法是：先為

2、棧分配一個(gè) 基本容量，然后在應(yīng)用過(guò)程中，當(dāng)棧的空間不夠使用時(shí)再逐段擴(kuò)大。為此，可設(shè)定 兩個(gè)常量：STACKCSL存儲(chǔ)空間初始分配量）和 STACKZ（存儲(chǔ)空間分配增量）。 下面給出順序棧的類(lèi)型定義：#in cludestdlib.h#define STACKCSL 64 /*順序棧存儲(chǔ)空間初始分配量*/#define STACKZL 8 /*順序棧存儲(chǔ)空間分配增量*/typedef int ElemType; /*棧元素的數(shù)據(jù)類(lèi)型定義，它可以是任意的，具體問(wèn)題時(shí) 只需根據(jù)需要修改本定義語(yǔ)句即可*/typedef struct ElemType *top; /*棧頂指針 */ElemType *

3、bottom; /* 棧底指針 */int stacksize; /*當(dāng)前已分配的存儲(chǔ)空間，以棧元素為單位 */seqstack; /* 順序棧類(lèi)型定義*/seqstack *seqs; /*seqs是順序棧類(lèi)型指針*/其中，stacksize指示棧的當(dāng)前可使用的最大容量，初始化棧時(shí)， stacksize 的值等于STACKCSL以后根據(jù)需要按分配增量STACKZL曾長(zhǎng)。bottom是棧底指針，在順序棧中，它始終指向棧底的位置，如果bottom的值 等于NULL，就意味著棧結(jié)構(gòu)不存在。top是棧頂指針，其初值指向棧底，也就是說(shuō)top=bottom可作為?？盏臉?biāo)記。 每當(dāng)插入新的棧頂元素時(shí)，指針

4、top增1；刪除棧頂元素時(shí)，指針top減一。所以, 非空棧中的棧頂指針始終在棧頂元素的下一個(gè)位置上。圖3.2表示了棧頂指針top和順序棧中數(shù)據(jù)元素之間的對(duì)應(yīng)關(guān)系。1 1 13top片4optop *bottombottombottom（a）空棧（b） 元素5、8 1進(jìn)棧（c）元素1出棧top（d）元素4、3進(jìn)棧（e）元素3出棧（f）棧滿圖3.2棧頂指針與數(shù)據(jù)元素的關(guān)系3. 2. 2基本運(yùn)算的實(shí)現(xiàn)上述順序棧的類(lèi)型定義以及本小節(jié)將介紹的基本運(yùn)算操作均放在文件“seqstack.c ”中，使用時(shí)需要用命令：#includeseqstack.c將其包含到具體的應(yīng)用程序中去。由于順序棧的插入、刪除只在棧

5、頂進(jìn)行，因此順序棧的基本操作比順序表要簡(jiǎn) 單得多。在順序棧上可以實(shí)現(xiàn)初始化棧、進(jìn)棧、出棧、判?？铡⑷ｍ斣氐葞追N 基本運(yùn)算，具體算法如下：1. 初始化棧該算法用于建立一個(gè)容量為STACKCS的空順序棧ss。建立時(shí)首先使用malloc 函數(shù)進(jìn)行內(nèi)存儲(chǔ)區(qū)的分配，并將所分配的存儲(chǔ)區(qū)的起始地址賦給棧底指針bottom 如果 bottom 不為空，說(shuō)明分配成功，否則說(shuō)明分配失敗。成功時(shí)進(jìn)行置空棧的操 作，失敗則退出。具體算法如下：算法 3.1void initstack ( seqstack *ss )/* 初始化一個(gè)順序棧 ss*/ss-bottom=( ElemType *)malloc( STA

6、CKCS*sLizeof( ElemType); if(!ss-bottom) printf( “初始化棧失敗” );return; ss-top=ss-bottom;ss-stacksize= STACKCS;Lprintf( 初始化棧成功！ );2. 進(jìn)棧該算法用于向順序棧SS的棧頂插入一個(gè)元素x。算法首先判斷棧是否已滿， 如果棧不滿， 就直接進(jìn)行插入操作， 否則就使用 reallo c 函數(shù)為該順序棧再多分配 增量STACKZ個(gè)元素的存儲(chǔ)空間。如果分配成功，則修改棧頂指針top的位置和棧 的容量 StackSize ，然后將元素 x 插入在棧頂位置。具體算法如下： 算法 3.2Void

7、puSh(SeqStack *SS, ElemType x)/* 將元素 x 插入順序棧 SS 的頂部 */if(SS-top-SS-bottom=SS-StackSize) /*判斷順序棧是否已滿 */SS-bottom=( ElemType *)realloc(SS-bottom,(SS-StackSize+STACKZL)* Sizeof( ElemType);if(!SS-bottom) printf(“ 棧容量擴(kuò)充失敗 ”);return;SS-top=SS-bottom+SS-StackSize;SS-StackSize=SS-StackSize+STACKZL;*SS-top=x

8、;SS-top+; 注意：如果在順序棧已滿的情況下再執(zhí)行進(jìn)棧操作時(shí)， 就會(huì)發(fā)生“上溢出” 的錯(cuò)誤， 必須進(jìn)行棧容量的擴(kuò)充 。3. 判?？赵撍惴ㄓ糜谂袛囗樞驐s是否為空棧。算法以棧頂指針top和棧底指針bottom 是否指向同一位置為判斷條件。這是因?yàn)閷?duì)于棧來(lái)說(shuō)， bottom 永遠(yuǎn)指向棧底的位 置，只有棧中沒(méi)有元素時(shí)， top 和 bottom 才可能指向同一個(gè)位置。具體算法如下： 算法 3.3int stackempty(seqstack *ss)/* 判斷順序棧 ss 是否為空 */if(ss-top=ss-bottom) return 1; elsereturn 0;4出棧該算法用于從

9、順序棧 ss 的棧頂刪除一個(gè)元素，并將該元素的值通過(guò) x 返回。 算法進(jìn)行時(shí)， 首先判斷棧是否為空， 如果為空則是錯(cuò)誤操作， 不空則將棧頂指針向 下移動(dòng)一個(gè)位置。具體算法如下：算法 3.4void pop(seqstack *ss ， ElemType x)/* 從順序棧 ss 中彈出棧頂元素置于 x 中*/if(ss-top=ss-bottom) return ERROR;ss-top-;x=*ss-top;需要注意的是 : 在該算法中，刪去棧頂元素只要將棧頂指針減 1即可，但該元 素在下次進(jìn)棧操作之前仍然是存在的，因此函數(shù)pop中應(yīng)利用變量x返回被刪元素。另外，當(dāng)順序棧為空時(shí)，進(jìn)行出棧操作

10、會(huì)發(fā)生“下溢出”錯(cuò)誤，應(yīng)盡量避免。5取棧頂元素將順序棧SS的棧頂元素通過(guò)變量x返回。該算法與pop操作有所類(lèi)似，只是 此算法中棧頂指針不發(fā)生變化。算法 3.5Void gettop (SeqStack *SS, ElemType x)/*取順序棧SS的棧頂元素置于x中*/if(SS-top=SS-bottom) exit(0); x=*(SS-top-1);在以上順序棧的實(shí)現(xiàn)算法中， 雖然設(shè)置了一個(gè)存儲(chǔ)空間分配增量 STACKZL 用 于堆棧容量不夠時(shí)進(jìn)行擴(kuò)容調(diào)整，但是還是要面對(duì)“溢出”問(wèn)題。尤其堆棧的使用 非常廣泛， 經(jīng)常出現(xiàn)在一個(gè)程序中需要同時(shí)使用多個(gè)堆棧的情形。 為了避免出現(xiàn)溢 出，需要

11、為每個(gè)堆棧分配一個(gè)足夠大小的空間。 然而，要做到這一點(diǎn)往往是很不容 易的，原因之一是各個(gè)堆棧所需要的空間大小很難估計(jì)； 原因之二是由于堆棧是個(gè) 動(dòng)態(tài)結(jié)構(gòu)， 各個(gè)堆棧的實(shí)際大小在使用過(guò)程中都會(huì)發(fā)生動(dòng)態(tài)變化， 有時(shí)其中一個(gè)堆 棧發(fā)生了上溢出， 而其他各堆棧還保留很多可用空間。 這就要求設(shè)法來(lái)解決多棧共 享空間的問(wèn)題。323 多棧共享空間假設(shè)將多個(gè)堆棧順序地映射到一個(gè)已知大小為 m的存儲(chǔ)空間上。如果只有兩個(gè)堆棧 來(lái)共享這m個(gè)存儲(chǔ)空間，問(wèn)題比較容易解決：只需要讓第一個(gè)棧的棧底位于 1處,讓另一個(gè)棧的棧底位于 m處。在使用堆棧時(shí)，兩棧各自向中間伸展，僅當(dāng)兩個(gè)棧的 棧頂指針相遇時(shí)才發(fā)生上溢出。這樣，兩個(gè)堆

12、棧之間就做到了余缺互補(bǔ)，互相調(diào)劑, 從而大大減少了空間的浪費(fèi)現(xiàn)象，如圖 3.3所示。1丨棧1棧2_人_棧1底棧1頂棧2頂棧2底(m)圖3.3兩個(gè)棧共享向量空間示意圖如果有兩個(gè)以上的堆棧共享空間m問(wèn)題的處理就要復(fù)雜一些。當(dāng)然，如果事先知道每個(gè)堆棧可能存放的元素的最多個(gè)數(shù)，那也可以將這m個(gè)空間根據(jù)各個(gè)堆棧的大小合理分配。但是，更多的情況是人們事先并不知道各個(gè)堆棧的最大容量。一個(gè)解決的辦法就是：先將m個(gè)存儲(chǔ)空間平均分配給n個(gè)(n2)棧，每個(gè)棧占|lm/n (不 大于m/n的最大整數(shù))個(gè)存儲(chǔ)空間，當(dāng)其中任意一個(gè)堆棧發(fā)生上溢出而整個(gè)空間并 未占滿時(shí)，就要進(jìn)行再調(diào)整。進(jìn)行調(diào)整操作時(shí)，首先設(shè)top1.n為n

13、個(gè)堆棧的棧頂指針的集合，topi為 第i個(gè)堆棧的棧頂指針；設(shè)bot1.n+1為n+1個(gè)棧底指針的集合，boti為第i 個(gè)堆棧的棧底指針，位于第i個(gè)堆棧實(shí)際棧底元素的前一個(gè)位置(為了方便對(duì)應(yīng)描 述，數(shù)組元素top0和bot0不使用)。其中設(shè)置第n+1個(gè)棧底指針botn+1的目的 是為了測(cè)試第n個(gè)堆棧棧滿與否。初始狀態(tài)如圖3.4所示：boti=topi= (i-1) * ( m/n)( K i 人人A -bot1 top1 bot2 top2 boti topi botn topn botn+1圖 3.5 多棧共享空間一般狀態(tài)示意圖很顯然，表示第i個(gè)堆棧為?？盏臈l件是：topi=boti (K i

14、 n),表示第i 個(gè)堆棧為棧滿的條件是：topi=boti+1( K i n)在上述情況中,很容易出現(xiàn)“假溢出”的情況,也就是當(dāng)用戶想在第 i 個(gè)堆棧中 插入一個(gè)新元素,此時(shí)第 i 個(gè)堆棧已滿,而其他堆棧實(shí)際上可能還很空,整個(gè)存儲(chǔ) 空間可能還有剩余。 要想有效利用其他堆棧的剩余存儲(chǔ)空間, 調(diào)整第 i 個(gè)堆?？臻g, 使得該新元素能夠插入到第 i 個(gè)堆棧中,可以進(jìn)行以下調(diào)整：方法一：右移法。該方法在i j n中確定有可用空間的最小j，也就是找到第 i 個(gè)棧右邊的第 1 個(gè)有可用空間的棧 j (此時(shí)必然有 topjbotj+1 ),然后將 第i+1、i+2第j個(gè)棧的所有元素連同棧底指針與棧頂指針都右

15、移一個(gè)位置， 使得第 i 個(gè)?？粘鲆粋€(gè)空間。方法二： 左移法。 該方法相對(duì)于右移法而言，當(dāng)?shù)?i 個(gè)棧的右邊不再有可用空間 時(shí)，就在 Kj 1），并作 為一個(gè)新的運(yùn)算對(duì)象重復(fù)進(jìn)行上述過(guò)程，直到表達(dá)式處理完畢。例如：abcd*+e/-的運(yùn)算過(guò)程如表3.1所示。表3.1后綴表達(dá)式的計(jì)算過(guò)程操作順序后綴表達(dá)式Tk c*dabT1+e/-T2 J b+TaEe/-T3 J T2/eaT3-T4 a-T3T4從上面的討論知道，后綴表達(dá)式之所以容易被編譯程序處理，是由于它具有 以下特點(diǎn)：（1）后綴表達(dá)式中不出現(xiàn)括號(hào)；（2） 后綴表達(dá)式與中綴表達(dá)式的運(yùn)算對(duì)象的先后次序相同，只是所讀到的運(yùn)算符先后次序可能有所

16、改變。正是由于后綴表達(dá)式具有以上特點(diǎn)，所以，處理時(shí)不必考慮運(yùn)算符的優(yōu)先關(guān)系。 在具體的處理過(guò)程中，需要設(shè)置一個(gè)堆棧，用來(lái)保存已經(jīng)讀到的運(yùn)算對(duì)象。也就是 說(shuō)，從左至右依次掃描后綴表達(dá)式，每讀到一個(gè)運(yùn)算對(duì)象就將其壓入堆棧； 每讀到 一個(gè)運(yùn)算符，就從堆棧中取出相應(yīng)的運(yùn)算對(duì)象進(jìn)行該運(yùn)算符所代表的操作，并把運(yùn)算結(jié)果作為一個(gè)新的運(yùn)算對(duì)象壓入堆棧。 表達(dá)式最后的計(jì)算結(jié)果就是位于堆棧中棧 頂?shù)闹?。綜上所述，表達(dá)式的值的計(jì)算過(guò)程需要經(jīng)過(guò)兩個(gè)步驟：一是把中綴表達(dá)式變 換為后綴表達(dá)式； 二是根據(jù)后綴表達(dá)式產(chǎn)生計(jì)算表達(dá)式的機(jī)器指令序列。 相對(duì)而言， 第二個(gè)步驟較為簡(jiǎn)單些，我們先討論實(shí)現(xiàn)第二個(gè)步驟的算法。算法 3.8#

17、includeseqstack.cVoid evalution() char c;int op1,op2,c1,result,x=0,val();seqstack *opd; /* 棧 opd 存放操作數(shù)及計(jì)算結(jié)果 */ initstack(opd); /*初始化棧 */空格則讀入下一個(gè)字符 */若讀入字符是數(shù)字 */ 將字符數(shù)字轉(zhuǎn)化為數(shù)值數(shù)字 */ 將該數(shù)值數(shù)字作為操作數(shù)進(jìn)棧 */ 若讀入字符為運(yùn)算printf( “請(qǐng)從鍵盤(pán)輸入后綴表達(dá)式：”)； while(c=getchar()!=n) /* 后綴表達(dá)式未結(jié)束 */ if(c= ) continue; /* if(c=0)&(c、-*/(

18、#opt1,則將opt2進(jìn)棧，然后讀下一個(gè)單詞；如果 opt2opt1 , opt1退棧作為后綴表達(dá)式中的一員輸出。 此后，繼續(xù)比較opt2與opt1 的優(yōu)先級(jí)（注意，此時(shí)的opt1已經(jīng)不是先前的那個(gè)運(yùn)算符了），直到 opt2得到合 適的處理。如果opt2=opt1,并且opt2工“ #”，則opt1退棧且消去opt2，然后繼 續(xù)讀下一個(gè)單詞，重復(fù)以上步驟，直到opt仁“#”、opt2= “#”時(shí)，算法結(jié)束。算法3.10#in cludeseqstackzztohz()/*設(shè)opt為運(yùn)算符棧，op為運(yùn)算符集合，super ()為運(yùn)算符優(yōu)先比較函數(shù)*/seqstack *opt;char c,x;in itstack(opt);push(opt, #);c=getchar();while(c!= # | gettop(opt)!= #)if(!I n( c,op)putchar(c); /*不是運(yùn)算符就將其作為后綴表達(dá)式的部分輸出*/c=getchar ();elseswitch(super(gettop(opt),c)case :putchar(pop(opt,x);/*棧頂元素優(yōu)先權(quán)高，棧頂元素退棧并輸出為后綴表達(dá)式*/break;利用上述算法，中綴表