定義棧是一種只能在頂端插入和刪除的列表。頂端是指最后一個操作的元素，數組中指下標最大的元素，鏈表中指末尾的元素。所以棧是一種LIFO（后進先出）的數據結構。實現棧可以使用數組、鏈表兩種方式實現。自己動手coding，可以學習怎么處理異常，還有一些其他細節。上一篇中分析到如果在表的末端插入和刪除都是O(1)的時間復雜度。 棧的基本操作有：1.E push(E item);2.E pop();3.E peek();4.boolean empty();5.int search(Object o);6.int size() ;應用棧的常用在 1 代碼編輯器檢查語法錯誤；2 計算器實現；3 計算機函數遞歸調用。代碼語法檢查寫代碼過程中有”(“必定有”)”，有”[“必定有”]”。這些是平衡符號。實現這個功能的過程中用到棧。思路是這樣的： 做一個空棧，讀入字符一直到文件結尾。 如果字符是一個封閉符號（])}），則當棧空時報錯。否則將棧元素彈出。如果彈出的符號不是對應的開放符號，則報錯。 在文件結尾，如果棧非空則報錯。 時間復雜度：線性的，與輸入的字符串長度有關系。計算器應用例如寫一個計算器實現：4.99*1.06+5.99+6.99*1.06，不同計算器給出的答案可能不同，可能是18.69或者19.37。在正確的計算過程中計算順序是 01 4.99*1.06=A1； 02 A1+5.99=A1; 03 6.99*1.06=A2; 04 A1+A2=答案 這種操作的順序書寫出來：4.99 1.06 * 5.99 + 6.99 1.06 * +。這叫做后綴表達法或者逆波蘭記法。4.99*1.06+5.99+6.99*1.06 這種表示方法叫做中綴表達式。如何從中綴到后綴？ 假設輸入的字符串是表達式合法的，可以使用棧，實現中綴到后綴的轉換。例如中綴表達式為：a+b*c+(d*e+f)*g。這里有兩個站，一個是輸出棧，一個是符號棧。 01 讀到一個操作數，push到輸出棧； 02 讀到一個操作符，push到符號棧；如果符號是”)”，則彈出符號棧元素到輸出棧，直到碰到”(“，”(“彈出，不進入輸出棧。如果是其他操作符號（例如：+-*/），從符號棧中彈出元素直到發現優先級更低的元素為止。對于”(“,”)”要特殊對待。 03 讀到輸入的末尾，把符號棧所有元素彈出，放入輸出棧。方法調用在計算機中，當從方法A執行一段，調用方法B，執行B之后，返回A繼續執行。當然可能會嵌套多層方法調用。每一次方法跳出，都需要把當前執行狀態記錄到棧中。保存的信息稱為活動記錄。當方法調用太多的時候就會發生棧溢出的錯誤。這種保存是計算機主動幫我們做的。解決棧溢出，首先檢查代碼邏輯，是否忘記了基本情況判斷；其次，如果真的是因為數據量太大，必須進行多次遞歸調用，則可以顯示的使用棧，將遞歸改為遞推，當然要損失的是代碼的可讀性。代碼任務01 棧的數組實現 02 棧的鏈表實現 03 語法檢查工具 04 計算器，中綴到后綴，后綴計算