【正文】 e x) { if(stop sstacksize1) //是否為空 { stop++。 } 下一頁 上一頁 停止放映 [第 10頁 /68頁 ] （ 2） 進棧操作 若棧不滿 ， 則在棧頂插入元素 x作為新的棧頂 。 sdata = new ElemType[size]。 void InitStack(SqStack *s, int size) { if( size 0 ) { sstacksize = size。寫出可能的出棧序列 。 //定義一個堆棧 s Top = 1 表示空棧； top = stacksize1 表示棧滿 。 //最大可用空間數(shù)量 }。 //存儲元素的數(shù)組 int top。 下一頁 上一頁 停止放映 [第 5頁 /68頁 ] 棧的順序存儲結(jié)構(gòu) 同順序表一樣 ， 可利用一維數(shù)組來實現(xiàn) 。 棧下溢 若棧空，再要執(zhí)行出棧操作，則會發(fā)生下溢。 ? 棧結(jié)構(gòu)也稱為 后進先出 表（ LIFO）。下一頁 上一頁 停止放映 第 2章之 棧與隊列 西安交通大學計教中心 下一頁 上一頁 停止放映 [第 2頁 /68頁 ] 要點 ? 棧和隊列結(jié)構(gòu)的特點 ? 邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的特點 ? 操作的特點 下一頁 上一頁 停止放映 [第 3頁 /68頁 ] 棧的定義 堆棧 (Stack) ? 棧是允許在同一端進行插入和刪除操作的特殊線性表。 ? 允許進行插入和刪除操作的一端稱為 棧頂 (top)，另一端為 棧底 (bottom)；棧底固定，而棧頂浮動； ? 棧中元素個數(shù)為零時稱為空棧。 棧示意圖 a1 a3 a2 進棧 出棧 top 下一頁 上一頁 停止放映 [第 4頁 /68頁 ] 棧有關(guān)概念 棧上溢 ?？臻g是有限的，若棧已滿，在進行入棧操作時，就要產(chǎn)生上溢。 棧頂指針 在棧操作過程中，有一個專門的棧指針（習慣上稱它為 TOP），指出棧頂元素所在的位置。 C++語言定義如下： struct SqStack{ ElemType *data。 //棧頂指針 ， 存儲棧頂元素下標 int stacksize。 SeqStack s。 下一頁 上一頁 停止放映 [第 6頁 /68頁 ] 棧操作舉例 a1 a2 …… a n 棧底 棧頂 MAXSIZE TOP 1. top=0 A B C 2. (空棧 ) top=3 (A、 B、 C進棧 ） A B 3. top=2 (C出棧） 4. A B C D E F top=MAXSIZE (棧滿） 下一頁 上一頁 停止放映 [第 7頁 /68頁 ] 例 有三個元素的進棧序列是 1， 2， 3。 出棧序列 操作序列 1 2 3 s x s x s x 1 3 2 s x s s x x 2 1 3 s s x x s x 2 3 1 s s x s x x 3 2 1 s s s x x x 下一頁 上一頁 停止放映 [第 8頁 /68頁 ] 棧的基本運算 InitStack（ Stack） 置棧為空； Empty（ Stack） 判定棧是否為空； Push（ Stack， x） 進棧操作，在棧頂插入元素； Pop（ Stack） 出棧操作，刪除棧頂元素； Gettop（ Stack） 取棧頂元素 下一頁 上一頁 停止放映 [第 9頁 /68頁 ] （ 1） 順序棧初始化 棧的初始化主要是為存儲元素的數(shù)組申請空間（ 長度為 size） 。 stop = 1。 // 申請空間 } else cout堆棧初始化長度錯誤 。 算法步驟 : – step1 判別棧滿否，若滿，則顯示棧溢出信息，停止執(zhí)行；否則，執(zhí)行 step 2； – Step2 棧頂指針 top上移 (加 1)； – Step3 在 top所指的位置插入元素 x。 //Top加 1 sdata[top]=x。 } 示例 下一頁 上一頁 停止放映 [第 12頁 /68頁 ] （ 3） 出棧操作 若棧不空 ， 則刪除 s的棧頂元素 ， 用 e返回其值 。 下一頁 上一頁 停止放映 [第 13頁 /68頁 ] 出棧算法程序 void Pop (SqStack *s, ElemType amp。 stop。 } 示例 下一頁 上一頁 停止放映 [第 14頁 /68頁 ] （ 4） 取棧頂元素 若棧不空 ， 則用 e返回 s的棧頂元素 。e) { if(stop 1) //若棧非空 e= sdata[stop]。 } 下一頁 上一頁 停止放映 [第 15頁 /68頁 ] 多棧共享問題 ? 多棧共享是充分利用棧空間的一種策略。 top1 =0 top2=MAXSIZE 空棧 top1 top2 棧 棧 2均有若干元素 top1 top2 棧滿的情況 a. b. c. 示例 下一頁 上一頁 停止放映 [第 16頁 /68頁 ] 棧的鏈式存儲結(jié)構(gòu) 由前面介紹的鏈表結(jié)構(gòu)可知，鏈結(jié)構(gòu)操作靈活。 順序棧最多可用于 2個棧的共享，對于更多的棧就難于表達了。這時，就需要采用鏈棧。 typedef struct node{ ElemType data。 //指針域 }SNode, *LinkSt