本文為清華大學開放式課程上課心得整理。
The Stack Abstract Data Type
Stack 是一個有順序的清單，透過端點（top）來做資料的新增或刪除，特性為後進先出（Last-In-First-Out，LIFO），當物件儲存進 Stack 時，會依照次序一個一個向上堆疊，刪除時則相反，會從最上面（最後存進去的物件）開始刪除。
Stack 有很多應用，像是在處理遞迴、或是程式需要回傳儲存的 adress 時都會用到。
The Queue Abstract Type
Queue 是另一種作法與 Stack 相反的有順序清單，不同於 Stack 的 insertion 和 deletion 在同一端點，Queue 有兩個端點，新的物件會從佇列尾端放入，刪除則是從最前端最舊的資料開始刪，是先進先出（First-in-First-out，FIFO）的操作形式。
由於 Queue 在刪除時會移動指向舊資料的頂點，一直移動下去，最後就會來到尾端資料頂點的前面，如果要繼續儲存資料，此時 Queue 有幾個操作方法：
（1）在末端頂點後面加空間給 Queue 繼續存資料，但這種作法會導致前面已刪除的儲存空間浪費。
（2）整串資料向右移動，但這樣在設計上就會變得複雜。
為了解決刪除之後儲存空間分配的問題，出現了另一種改良版的設計，稱為 Circular Queue，也就是將儲存空間變成一個密閉的圓，在 insertion 時做 rear = (rear + 1) % capacity 的計算，deletion 同理，做 front = (front + 1) % capacity，用以求得端點位置。
Queue 還有另一個要探討的問題，就是當 front point 等於 rear point 的時候。滿足這個條件的有兩個狀況，一個是這個佇列是空的，另一個則是這個佇列已經滿了。由於這個狀況比較難處理，所以通常會在出現此狀況之前就將 Queue 的儲存空間變大。
Evaluation of Expressions
當我們拿到一個算式時，通常會先分別出算式中的運算子（加減乘除……）與運算元（數字），然後再根據運算元的優先順序，計算出最後的結果。在運算子中，括號的優先權最高，一個運算元、運算子皆相同的算式，可能會因為括號的位置不同而得到不同的結果，所以對電腦來說，計算規則就變得很重要。以下是幾個計算的要點：
1. 運算子有其優先序
2. 優先序高的運算子要優先被計算
3. 當運算子的優先序相同時，依序從左邊計算至右邊
4. 運算子優先序相同時，一元運算子的計算方式為由右至左下圖為 C++ 中運算子的優先序：
Infix and Postfix Notation
程式算式有兩種表達方法：
- 中序式（Infix Notation）：運算子夾在兩個運算元中間，例如：A + B * C，這種表達式在使用程式做計算的時候非常困難。
- 後序式（Postfix Notation）：運算子集中在算式後方，如： ABC*+，在程式計算上相對簡單。
後序式的好處是，它不需要使用括號來區別運算的先後次序，也不需要特別設定運算子的優先序；後序式的計算方式如下：
1. 從左到右掃描算式
2. 用 Stack 儲存運算元
3. 遇到運算子便做計算
4. 將計算的結果再放回 Stack依序進行便可以得到最後的結果。
Infix 與 Postfix 的轉換
後序式計算表達式可以將它看成已經將括號都放上去了來做分組，以下方的算式為例：
A / B - C + D * E - A * C加上括號之後變成這樣：
((((A / B) - C) + (D * E)) - (A * C))接下來只要依序把括號中的運算子搬到右邊：
AB/C-DE*+AC*-就變成後序式了。
後序式轉換也可以用 Stack 來進行，規則如下：
1. 由左至右掃描算式
2. 不改變運算元的順序，當掃到運算元的時候直接輸出
3. 掃到運算子即儲存，直到最後一個物件的優先序比下一個要進入的運算子優先序高或相等時才輸出若算式中有括號，則左括號的權重最高，當左括號被推進 Stack 之後，權重變成最低；右括號的權重最低，因此會一直將 Stack 中的物件輸出，直到碰到左括號為止。此時兩個括號會互相消除，不進入後序式中。
