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