【文章內(nèi)容簡(jiǎn)介】 44 2. 棧的特征：最先放入棧中元素在棧底，最后放入的元素在棧頂，而刪除元素剛好相反，最后放入的元素最先刪除，最先放入的元素最后刪除。也就是說，棧是一種后進(jìn)先出 (Last In First Out)的線性表，簡(jiǎn)稱為 LIFO表。 入棧順序： e0 e1 e2 … e n2 en1 出棧順序： en1 en2 … e 2 e1 e0 ?？梢詫?duì)序列實(shí)現(xiàn)求逆 en1 e0 e1 en2 … 進(jìn)棧（ Push） 出棧（ Pop） 棧頂 top 棧底 45 用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的堆棧稱為順序堆棧（ SequentStack）。圖 3―6 是一個(gè)順序堆棧的動(dòng)態(tài)示意圖。圖中，最大元素個(gè)數(shù)設(shè)為 6， top為棧頂指示器。圖 3―6 （ a)表示一個(gè)空棧；圖 3―6(b) 表示插入一個(gè)數(shù)據(jù)元素 A后的狀態(tài)；圖 3―4(c) 表示插入數(shù)據(jù)元素 B、C、 D后的狀態(tài)；圖 3―6(d) 表示刪除數(shù)據(jù)元素 D、 C后的狀態(tài)；圖 3―6(e) 表示刪除數(shù)據(jù)元素 B、 A后的狀態(tài)。 46 圖 3― 6 順序堆棧的動(dòng)態(tài)示意圖 （ a)空棧； (b)插入數(shù)據(jù)元素 A后； (c)插入數(shù)據(jù)元素 B、 C、 D后； (d)刪除數(shù)據(jù)元素 D、 C后； (e)刪除數(shù)據(jù)元素 B、 A后 d a t a543210t o p( a )d a t a543210( b )At o pd a t a543210t o p( c )ABCDd a t a543210( d )d a t a543210t o p( e )t o pAB47 棧頂位置指示器 top和順序表中的當(dāng)前元素個(gè)數(shù) size的含義完全相同 ， 只是在堆棧中用 top更能反映它的棧頂位置指示器的含義 ， 所以在此使用了不同的名字 。 此外 ， 順序堆棧中的數(shù)組 data[]和順序表中的數(shù)組 data[]也完全相同 。 因此我們說 ，順序堆棧和順序表的邏輯結(jié)構(gòu)完全相同 ， 只是兩者允許的操作集合不同 ， 順序表允許在任意位置插入和刪除 ， 而順序堆棧只允許在棧頂位置插入和刪除 ， 所以我們也可以說 ， 順序堆棧是操作受限制的順序表 。 48 順序堆棧定義和函數(shù)實(shí)現(xiàn) 直接定義是指直接定義順序堆棧類 ， 不考慮順序堆棧類數(shù)據(jù)成員對(duì)順序表類數(shù)據(jù)成員的繼承 。下面的順序堆棧定義中部分類成員函數(shù)使用了內(nèi)聯(lián)函數(shù)的方法 。 const int maxstacksize=100。 struct SequentStack { elemtype stack[maxstacksize]。 //將棧中元素定義為 elemtype類型 int top。 // 指向棧頂位置 }。 49 1).初始化棧： IniStack(amp。s) 將棧 s置為一個(gè)空棧 (不含任何元素 )。 2).進(jìn)棧： Push(amp。s,x) 將元素 x插入到棧 s中，也稱為 “入?！?、 “插入”、 “壓入”。 3).出棧： Pop(amp。s) 刪除棧 s中的棧頂元素，也稱為”退?！?、 “刪除”、 “彈出”。 4).取棧頂元素： GetTop(s) 取棧 s中棧頂元素。 5).判?？眨? Empty(s) 判斷棧 s是否為空，若為空，返回值為 1，否則返回值為0。 50 ADT Stack is Data： 含有 n個(gè)元素 a1,a2,a3,…,an, 按 LIFO規(guī)則存放，每個(gè)元素的類型都為 elemtype。 operation： void IniStack (amp。s) //將棧 s置為一個(gè)空棧 (不含任何元素 ) void Push(amp。s,item) //將元素 item插入到棧 s中， //也稱為 “入?！薄? “插入”、 “壓入” void Pop(amp。s) //刪除棧 s中的棧頂元素， //也稱為”退?！?、 “刪除”、 “彈出” Elemtype GetTop(s) //取棧 s中棧頂元素 Int Empty(s) //判斷棧 sS是否為空，若為空， //返回值為 1，否則返回值為 0 End stack 51 ： （ 1）初始化棧 void IniStack(SequentStack amp。s) { =0。 } 52 （ ２ ） 進(jìn)棧 //把元素 item void Push(SequentStack amp。s,elemtype item) { if(==maxstacksize) { cerr堆棧已滿 !endl。 exit(1)。 } []=item。 //top的初始值為 0是有效存儲(chǔ)單元 ,所以先存儲(chǔ) item s. top++。 //然后 top加 1 } 53 （ ３ ） 退棧 // elemtype Pop(SequentStack amp。s) { if(==0) { cout堆棧已空 !endl。 exit(1)。 } 。 //top先減 1 return []。 //然后取 top } 54 （ ４ ） 取棧頂元素 // elemtype GetTop(SequentStack s) { if(==0) { cerr堆?？?!endl。 exit(1)。 } return []。 //top指在棧頂?shù)南乱粋€(gè)位置 ,取 top1 } 55 （ 5） 判?？辗? int Empty(SequentStack s) { if (= =0) return 1。 else return 0。 } 56 5． 棧的共享存儲(chǔ)單元 有時(shí) ， 一個(gè)程序設(shè)計(jì)中 ， 需要使用多個(gè)同一類型的棧 ,這時(shí)候 ， 可能會(huì)產(chǎn)生一個(gè)棧空間過小 ， 容量發(fā)生溢出 ，而另一個(gè)?？臻g過大 ， 造成大量存儲(chǔ)單元浪費(fèi)的現(xiàn)象 。 為了充分利用各個(gè)棧的存儲(chǔ)空間 ， 這時(shí)可以采用多個(gè)棧共享存儲(chǔ)單元 ， 即給多個(gè)棧分配一個(gè)足夠大的存儲(chǔ)空間 ， 讓多個(gè)棧實(shí)現(xiàn)存儲(chǔ)空間優(yōu)勢(shì)互補(bǔ) 。 棧 1 頂 棧 2 頂 棧 1 底 棧 2 底 圖 3 7 兩個(gè)棧共享存儲(chǔ)單元示意圖 57 兩個(gè)棧共享存儲(chǔ)單元可用如下 C++語(yǔ)句描述： CONST int maxstacksize=100。 struct duSequentStack { elemtype stack[maxstacksize]。 int top[2] 。 //兩個(gè)棧的棧頂標(biāo)志位 ……… }。 58 （ 1） 兩個(gè)棧共享存儲(chǔ)單元的進(jìn)棧算法 void DuPush(duSequentStack amp。s, elemtype x, int k) //將元素 x進(jìn)入到以 S為?？臻g的第 k個(gè)棧中 { if ([0]+1==[1]) { cerr堆棧已滿 !endl。 exit(1)。 } else if (k==0) {[[0]]=x。 [0]++。 } else {[[1]]=x。 [1]。 } } 59 （ 2） 兩個(gè)棧共享存儲(chǔ)單元的退棧算法 elemtype Pop(duseqstack amp。s, int k) //將以 s為?？臻g的棧中第 k個(gè)棧進(jìn)行退棧 { elemtype temp。 if (k==0) { if ([0]==0) {cout ”堆棧 0已空” endl。 exit(1)。} else {[0]。 temp=[[0]]。 return temp。} } else { if ([1]==maxstacksize1) {cout ”堆棧 1已空” endl。 exit(1)。} else {[1]++。 temp=[[1]]。 return temp。} } } 60 順序堆棧應(yīng)用 ——表達(dá)式計(jì)算 堆棧是各種軟件系統(tǒng)中應(yīng)用最廣泛的數(shù)據(jù)結(jié)構(gòu)之一 。 例如 ， 表達(dá)式計(jì)算是編譯系統(tǒng)中的基本問題 ， 其實(shí)現(xiàn)方法是堆棧的一個(gè)典型應(yīng)用 。 在編譯系統(tǒng)中 ， 要把便于人理解的表達(dá)式翻譯成能正確求值的機(jī)器指令序列 ， 通常需要先把表達(dá)式變換成機(jī)器便于理解的形式 ， 這就要變換表達(dá)式的表示序列 。 借助順序堆棧即可實(shí)現(xiàn)這樣的變換 。 61 算術(shù)表達(dá)式中包含了算術(shù)運(yùn)算符和算術(shù)量 (常量、變量、函數(shù) )，而運(yùn)算符之間又存在著優(yōu)先級(jí)，不能簡(jiǎn)單地進(jìn)行從左到右運(yùn)算，編譯程序在求值時(shí)，不能簡(jiǎn)單從左到右運(yùn)算，必須先算運(yùn)算級(jí)別高的，再算運(yùn)算級(jí)別低的，同一級(jí)運(yùn)算才從左到右 (C++中有些從右到左 )。 步驟 ： 1).建兩個(gè)棧，一個(gè)棧存放運(yùn)算符，另一個(gè)棧存放操作數(shù)（算術(shù)量），并讓兩個(gè)棧為空。 62 2).編譯程序從左到右將算術(shù)表達(dá)式掃描完。 掃描中處理規(guī)則： ⑴ . 遇到操作數(shù)：一律進(jìn)入操作數(shù)棧。 ⑵ . 遇到運(yùn)算符：則應(yīng)與運(yùn)算符棧的棧頂元素進(jìn)行比較： （運(yùn)算符?？諘r(shí)也是進(jìn)棧） . ，退棧后，在操作數(shù)棧中退出兩個(gè)元素 (先退出在運(yùn)算符右，后退出在運(yùn)算符左 )，然后用運(yùn)算符棧中退出的棧頂元素進(jìn)行運(yùn)算，運(yùn)算結(jié)果存入操作數(shù)棧中。 63 3).檢查運(yùn)算符棧中是否為空 : ，算術(shù)表達(dá)式運(yùn)算結(jié)束，則操作數(shù)棧中只有一個(gè)元素，即為運(yùn)算的結(jié)果。 ，退出運(yùn)算符棧棧頂元素，在操作數(shù)棧中退出兩個(gè)元素 (先退出在運(yùn)算符右，后退出在運(yùn)算符左 )進(jìn)行運(yùn)算，運(yùn)算結(jié)果存入操作數(shù)棧中。 按照這個(gè)規(guī)則直到運(yùn)算符棧為空，這時(shí)，操作數(shù)棧中只有一個(gè)元素，即為運(yùn)算的結(jié)果。 例求表達(dá)式 1+2*34/2的值，棧的變化如下。 64 步驟 操作數(shù)棧 運(yùn)算符棧 說明 開始 兩棧均為空 1 1 1進(jìn)入操作數(shù)棧 +進(jìn)入運(yùn)算符棧 2進(jìn)入操作數(shù)棧 *進(jìn)入運(yùn)算符棧 3進(jìn)入操作數(shù)棧 退棧 2*3進(jìn)入操作數(shù)棧 退棧 1+6進(jìn)入操作數(shù)棧 2 3