堆棧（Stack）：後進先出#
在實現遞歸算法時，需要將從頂部到底部的很多中間狀態保留，走到最底部完成最基本的操作，然後根據保留的中間狀態回溯，直到最頂部。
- 為了配合遞歸算法，最好有一個數據結構能做到後進先出（Last-In, First-Out，LIFO）
- 這種數據結構就是堆棧（Stack）
以漢諾塔理解堆棧#
- Hanoi(64,A,B,T) 最先進入堆棧，放在最底下
- 然後是 Hanoi(63,A,T,B)……最後進來的是 Hanoi(1,A,T,B)，放在最頂上
- 最頂上的 Hanoi(1,A,T,B) 最先被執行並清除
- 最底部的 Hanoi(64,A,B,T) 最後被執行，整個程序執行完畢
堆棧這種「後進先出」的機制在生活中並不多見，因此很多剛進入計算機專業的人會覺得不合理。但在計算機處理問題時，經常要把一個大問題自上而下分解成很多小問題，堆棧能夠記錄這中間一步步分解的複雜過程，最後合併的過程和拆解的過程正好相反，正適合後進先出的特點。
堆棧的重要性#
- 計算機中所有函數和過程調用都是在堆棧的幫助下實現的
- 對堆棧的深刻理解可以幫助開發者從上往下俯視一個程序
例題 2.5：簡單計算器問題#
實現一個支持不帶括號的四則運算計算器（先乘除後加減）。
計算 “5+4-2=”#
- 先把 5 壓入堆棧
- 壓入 “+” 和 4，然後遇到 “-"，因為 “-” 和棧頂的 “+” 優先級相同，出棧計算 4+5=9，再壓回
- 壓入 “-” 和 2，遇到 “=” 時做兩步操作：計算 9-2=7，輸出結果
計算 “5-4x3/4=”#
- 遇到更高優先級的 “x” 時，不能先算 5-4，需要將運算符和後面的數字壓棧
- 遇到同優先級的 “/” 時，先做 4x3=12 的運算
- 遇到 “=” 時，先算 12/4=3，再算 5-3=2
使用堆棧時要注意邊壓邊處理，而不是將整個算式全部壓入堆棧後才考慮如何處理。否則遇到 “5-4-3=” 這類算式時，棧頂端先做 4-3 是錯誤的。
隊列（Queue）：先進先出#
有些場景需要先進先出（First-In, First-Out，FIFO），例如視頻處理中按時間順序處理每一幀。
隊列的數據結構#
- 通常採用一個數組和兩個指針（頭指針和尾指針）
- 新數據加入隊列尾部，尾指針後移
- 數據從隊列頭部取出，頭指針後移
用隊列實現廣度優先遍歷#
BreadthFirstTraverseTree(BinaryTree tree) {
if (tree = NIL) return;
將根節點送到隊列 queue 中;
while (隊列 queue 不為空) {
取出隊列頭一個數據 node;
if (node.left_subtree != NIL)
將 node.left_subtree 放進隊列 queue;
if (node.right_subtree != NIL)
將 node.right_subtree 放進隊列 queue;
}
}- 根節點先入隊列，取出時將其子節點加入隊尾
- 按照節點進入隊列和被處理的次序，就完成了廣度優先遍歷
堆棧的另一大應用：模塊嵌套#
- 現代計算機程序都是由功能模塊（函數/過程）相互嵌套而成
- 模塊之間的相互調用需要使用堆棧來記錄調用過程
要點回顧#
- 堆棧是後進先出（LIFO），支撐遞歸算法和深度優先遍歷
- 隊列是先進先出（FIFO），實現廣度優先遍歷
- 堆棧在實際工程中廣泛用於函數調用、表達式求值等場景