【正文】 。 } 下一頁 上一頁 停止放映 [第 15頁 /68頁 ] 多棧共享問題 ? 多棧共享是充分利用?？臻g的一種策略。具體作法是： – 對兩棧共享情況來說，將兩個棧底分別設在兩端，兩個棧頂指針 top1和 top2相對中間位置動態(tài)移動，兩個棧之間的分界線是不定的。 top1 =0 top2=MAXSIZE 空棧 top1 top2 棧 棧 2均有若干元素 top1 top2 棧滿的情況 a. b. c. 示例 下一頁 上一頁 停止放映 [第 16頁 /68頁 ] 棧的鏈式存儲結構 由前面介紹的鏈表結構可知，鏈結構操作靈活。對棧結構也是一樣的。 順序棧最多可用于 2個棧的共享，對于更多的棧就難于表達了。 對于最大空間需要量事先不知的情況，就不能使用順序棧了。這時，就需要采用鏈棧。 下一頁 上一頁 停止放映 [第 17頁 /68頁 ] 棧的鏈式存儲結構實質上就是一個無頭結點、只能在頭部插入、刪除元素的單鏈表。 typedef struct node{ ElemType data。 //數據域 struct node *next。 //指針域 }SNode, *LinkStack。 LinkStack top； //定義棧頂指針 這里 SNode可用來定義結點， LinkStack用來定義棧頂指針。 鏈棧為空的條件： top = NULL 鏈棧為滿的條件 : t = NULL t 為申請的結點 ,為 NULL表示失敗。 鏈棧存儲結構 下一頁 上一頁 停止放映 [第 18頁 /68頁 ] （ 1） 進棧操作 若棧不滿 ， 則在棧頂插入元素 x作為新的棧頂 。 操作步驟 : step1 申請一個鏈棧結點 ,若 t=NULL,則表示鏈滿 。否則 ,執(zhí)行 step2 。 step2 在 top所指結點之前插入新結點 ,并將 top指向新申請的結點 t。 下一頁 上一頁 停止放映 [第 19頁 /68頁 ] 進棧操作程序 void Push(LinkStack amp。top, ElemType x) { SNode *p=new SNode。 if(p!=NULL) { pdata=x。 pnext=top。 top=p。 } } 下一頁 上一頁 停止放映 [第 20頁 /68頁 ] （ 2） 出棧操作 若棧不空 ， 則刪除棧頂元素 ， 用 e返回其值 。 算法操作步驟 : step1 若鏈棧為空 ， 則輸出棧溢出信息；否則 ， 執(zhí)行 step 2。 step2 刪除 top所指結點 ， 并使 top 指向被刪除結點的后繼結點 。 step3 釋放被刪除結點的存儲空間 。 下一頁 上一頁 停止放映 [第 21頁 /68頁 ] 出棧操作程序 void Pop (LinkStack amp。top, ElemType amp。e) { SNode *p。 if(top!=NULL) { e= topdata。 p=top。 top=topnext。 delete p。 } } 下一頁 上一頁 停止放映 [第 22頁 /68頁 ] 棧的應用 表達式計算 子程序的嵌套調用 參數傳遞 鍵盤緩沖區(qū) 遞歸過程的實現 下一頁 上一頁 停止放映 [第 23頁 /68頁 ] 舉例 1 表達式計算 計算表達式，首先要正確地定義運算規(guī)則： – 先乘除、后加減 – 從左到右 – 先括號內，再括號外 為了讓計算機能識別表達式，規(guī)定： – 表達式由操作數（ Operand）和操作符（ Operator）和定界符（ Delimiter）組成。 例如， 3*（ 72） ； – 實際處理表達式是用兩個棧結構 OPTR（算符）和 OPND（操作數）加運算規(guī)則組成； 四則運算 下一頁 上一頁 停止放映 [第 24頁 /68頁 ] 計算表達式算法步驟 Step1 初始化，清空 OPTR和 OPND，將左定界符壓 OPTR棧； Step2 循環(huán)輸入表達式中的每個字符 – 若輸入操作數，則進 OPND棧 – 若是算符，則和 OPTR棧頂元素進行比較，按規(guī)則進行相應操作 – 操作服從優(yōu)先關系表（ Q1是棧中算符， Q2是當前算符） ? Q1Q2 Q2入 OPTR棧，再讀入下一個元素 ? Q1=Q2 Q1出 OPTR棧，脫括號，再讀一個元素 ? Q1Q2 Q1出 OPTR棧，從 OPND中取兩個數運算 Step3 直到出現右定界符為止。 舉例，計算： 3*（ 72） 輸入： 3*（ 72） 下一頁 上一頁 停止放映 [第 25頁 /68頁 ] 計算表達式的處理步驟 步驟 OPTR棧 OPND棧 輸入字符 主要操作 1 3 PUSH（ OPND， 3） 2 3 * PUSH（ OPTR，‘ *’） 3 * 3 （ PUSH（ OPTR，‘（’） 4 *（ 3 7 PUSH（ OPND， 7） 5 *（ 37 PUSH（ OPTR，‘ ’） 6 *（ 37 2 PUSH（ OPND， 2） 7 *（ 372 ） Operate（ 7，‘ ’， 2） 8 *（ 35 ） POP（ OPTR） 9 * 35 Operate（ 3，‘ *’， 5） 10 15 RETURN（ GETTOP（ OPND）） 表達式處理 3*(72) 下一頁 上一頁 停止放映 [第 26頁 /68頁 ] 舉例 :