Stack

Stack 資料結構的主要特性是「Last-In-First-Out」。這個特性就好像我們使用一個只能從頂部取放物品的盒子。

為了更加具體化這個概念，想像吃洋芋片時，我們只能從上面取出、和放入洋芋片，當我們想要吃罐子最底下的洋芋片時，我們得先取出再其之上的所有洋芋片才能拿到。

這個特定的行為揭示了堆疊的核心特點，即最後進入的物品將會是最先被取出的。因此，任何符合這一「後進先出」特性的資料結構都可以稱作Stack。

一般的 Stack，會有以下幾個功能：

• PUSH(data)：把資料放進 Stack
• POP()：把「最上面」的資料移除
• TOP()：查看「最上面」的資料
• IsEmpty()：檢查 Stack 是否為空

Stack的應用

Stack最主要的功能是「記得剛才的資訊」，所以時常用來處理需要「回復到先前的狀態」的問題，也稱為Back-Tracking問題，例如：

• 編輯器(如word、sublime等等)中的undo。
• 網頁瀏覽器的「回到前一頁」功能。
• 任何遞迴(recursion)形式的演算法，都可以用Stack改寫，例如Depth-First Search(DFS，深度優先搜尋)。
• 記憶體管理(memory management)中的Call Stack。