堆疊是一個有序的 list ，從上方一個一個加入 (push)，取出時也從上方一個一個取出 (pop)，這就是「後進先出」的概念 Last-In-First-Out (LIFO)
有三種實做的方法
-
利用靜態陣列 (Array) 實作
必需在程式執行前就先給一個空間，給太多會浪費空間，給太少又會溢出來 實作上最簡單
-
利用鏈結串列 (Linked list) 實作
存取位址很浪費記憶體，比如現在的 x64 處理器就得花 64 bits 存取位址
-
利用動態陣列當元素太多時就將陣列空間變為原本的兩倍實作
這種方法實作難度較高，但不管是記憶體還是效能都是三者中最好的
說明 05-用堆疊來計算後序式.c
| Token | Stack [0] | [1] | [2] | |
|---|---|---|---|---|
| 6 | 6 | push() | ||
| 2 | 6 | 2 | push() | |
| / | 3 (因為6/2) | pop() 兩個，然後算完再 push() | ||
| 3 | 3 | 3 | push() | |
| - | 0 (因為3-3) | pop() 兩個，然後算完再 push() | ||
| 4 | 0 | 4 | push() | |
| 2 | 0 | 4 | 2 | push() |
| * | 0 | 8 (因為4*2) | pop() 兩個，然後算完再 push() | |
| + | 8 (因為 0 + 8) | pop()出來即最後答案 |