兩棧共享一向量空間（一維數組）棧底設在數組的兩端兩棧頂相鄰時為棧滿設共享數組為S[MAX]則一個棧頂指針為另一個棧頂指針為MAX時棧為空
用C寫的入棧操作push（ix）如下
const MAX=共享棧可能達到的最大容量
typedef struct node
{elemtype s[MAX]
int top[]
}anode
anode ds;
int push(int ielemtype x)
//ds為容量有MAX個類型為elemtype的元素的一維數組由兩個棧共享其空間i的值為或x為類型為elemtype的元素本算法將x壓入棧中如壓棧成功返回否則返回
{if（dstop[]dstop[]==）{printf（棧滿\n）return（）}
switch（i）
{case dss[++dstop[i]]=xbreak
case dss[dstop[i]]=x
return（）}//入棧成功
}
本程序段查找棧S中有無整數為k的元素如有則刪除采用的辦法使用另一個棧T在S棧元素退棧時若退棧元素不是整數k則壓入T棧遇整數kk不入T棧然後將T棧元素全部退棧並依次壓入棧S中實現了在S中刪除整數k的目的若S中無整數k則在S退成空棧後再將T棧元素退棧並依次壓入S棧直至T棧空這後一種情況下S棧內容操作前後不變
中綴表達式(+)*(/）的後綴表達式是 + / *
棧的變化過程圖略（請參見題）表達式生成過程為
中綴表達式exp轉為後綴表達式exp的規則如下
設操作符棧s初始為空棧後壓入優先級最低的操作符#對中綴表達式從左向右掃描遇操作數直接寫入exp若是操作符（記為w）分如下情況處理直至表達式exp掃描完畢
（）w為一般操作符（+*/等）要與棧頂操作符比較優先級若w優先級高於棧頂操作符則入棧否則棧頂運算符退棧到expw再與新棧頂操作符作上述比較處理直至w入棧
（）w為左括號（（）w入棧
（）w為右括號（））操作符棧退棧並進入exp直到碰到左括號為止左括號退棧（不能進入exp）右括號也丟掉達到exp中消除括號的目的
（）w為#表示中綴表達式exp結束操作符棧退棧到exp直至碰到#退棧整個操作結束
這裡再介紹一種簡單方法中綴表達式轉為後綴表達式有三步首先將中綴表達式中所有的子表達式按計算規則用嵌套括號括起來接著順序將每對括號中的運算符移到相應括號的後面最後刪除所有括號
例如將中綴表達式(+)*(/）轉為後綴表達式按如上步驟
執行完上面第一步後為(((+)*((/))))
執行完上面第二步後為((()+(()/))*)
執行完上面第三步後為 + / *
可用類似方法將中綴表達式轉為前綴表達式
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/22716.html
