前綴表達式 -+abc/de
中綴表達式 a+bc-d/e
后綴表達式 abc*+de/-

堆棧（stack）:具有一定操作約束的線性表，只在一端（棧頂：Top）做插入、刪除
插入數據：入棧（push）
刪除數據：出棧（pop）
后入先出：Last In First Out（LIFO）

堆棧操作：
1、Stack CreateStack(int MaxSize)：生成空堆棧，最大長度為MaxSize
2、int IsFull(Stack S,int MaxSize)：判斷堆棧S是否已滿
3、void Push(Stack S,ElementType item)：將元素item壓入堆棧
4、int isEmpty(Stack S)：判斷堆棧是否為空
5、ElementType Pop(Stack S)：刪除并返回棧頂元素

堆棧的鏈式存儲實現(xiàn)

實際就是一個單鏈表，叫做鏈棧，棧頂指針Top應該在鏈表的頭部（尾部則Pop操作無法完成）
數組大小固定，鏈表不固定

中綴表達式求值

解決方法：中綴表達式通過堆棧轉化為后綴表達式，求值 （T(N) = O(N)）
轉化方法：
1、運算數：直接輸出
2、左括號：壓入堆棧
3、右括號：將棧頂的運算符彈出并輸出，直到遇到左括號（左括號出棧，不操作）
4、運算符：
1、優(yōu)先級大于棧頂運算符時、壓棧
2、優(yōu)先級小于棧頂運算符時，將棧頂運算符彈出并輸出，并對新的棧頂運算符做相同比較直到大于棧頂運算符優(yōu)先級，然后將新運算符壓棧
5、各運算符操作完畢，將堆棧中的剩余運算符一并輸出

例：
3+2*((8+12)/10)-(100/5)

3 2 8 12 + 10 / * + 100 5 / -

-13

堆棧應用：
1、函數調用及遞歸實現(xiàn)
2、深度優(yōu)先搜索(?
3、回溯算法(? 老鼠走迷宮?