Stack: Intro(簡介)

先備知識與注意事項

Stack(堆疊)是一種概念性的抽象資料結構，可以分別使用Array(陣列)與Linked list(連結串列)來實作。

本篇文章將介紹Stack的基本概念，程式實作留在下一篇。

簡介：Stack

Stack是具有「Last-In-First-Out」的資料結構(可以想像成一種裝資料的容器)，「最晚進入Stack」的資料會「最先被取出」，「最早進入Stack」的資料則「最晚被取出」。

就像搬家的時候要把書(資料)裝進箱子(Stack)，假設箱子的開口大小剛剛好只能平放一本書，如果先放入《灌籃高手》，再放《笑傲江湖》，再放《搶救國文大作戰》，那麼到了新家之後，因為箱子底下沒有破洞，所以要拿到最底下的《灌籃高手》，就一定得先把上面的《搶救國文大作戰》與《笑傲江湖》拿出箱子才行。

觀察以上的敘述，《灌籃高手》符合「最早放入箱子」而且「最晚拿出來」，而《搶救國文大作戰》符合「最晚放入箱子」且「最早拿出來」，其餘的資料也勢必符合此規則(每個資料至少會位於「最上面」一次)，便能夠將這個箱子視為一個Stack。
由此可見，Stack是一個抽象的概念，只要符合「Last-In-First-Out」的資料結構，都可以視為Stack。

一般的Stack，會有以下幾個處理資料結構的功能：

Push(data)：把資料放進Stack。
- 把書放進箱子。
Pop：把「最上面」的資料從Stack中移除。
- 把位於箱子「最上面」的書拿出來。
Top：回傳「最上面」的資料，不影響資料結構本身。
- 確認目前位於箱子「最上面」的是哪本書。
IsEmpty：確認Stack裡是否有資料，不影響資料結構本身。
- 確認箱子裡面有沒有書。
getSize：回傳Stack裡的資料個數，不影響資料結構本身。
- 記錄目前箱子已經裝了多少本書。

圖一。

以圖一為例，一開始Stack是空的：

當Push(6)後，便把\(6\)放入Stack。並用一個稱為top的變數，記錄Stack最上面的資料為何，在此即為\(6\)。
當Push(3)、Push(7)後，便把\(3、7\)放入Stack。並更新top，使其記錄\(7\)。
當Pop()後，便把Stack中「最上面」的資料(\(7\))給移除，所以Stack中剩下\(6、3\)，並更新top記錄\(3\)。
當Push(14)、Push(8)後，便把\(14、8\)放入Stack。並更新top，使其記錄\(8\)。
在以上的任何階段，只要Stack有資料，使用函式Top()會回傳變數top所記錄的資料。
在以上的任何階段，使用IsEmpty()便能判斷Stack裡是否有存放資料。
在以上的任何階段，使用getSize()會回傳Stack中的資料個數。

Stack還有一項重要的特徵：

除了最上面的資料可以使用Top()來讀取，無法得知Stack裡面還有其餘哪些資料。要知道Stack裡的所有資料，只能靠Pop()，把資料一個一個拿出來檢查。

Stack的應用

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

編輯器(如word、sublime等等)中的undo。
網頁瀏覽器的「回到前一頁」功能。
編譯器(compiler)中的Parsing。
- 參考：Compiler Design - Top-Down Parser。
任何遞迴(recursion)形式的演算法，都可以用Stack改寫，例如Depth-First Search(DFS，深度優先搜尋)。
- 參考：GeeksforGeeks:Iterative Depth First Traversal of Graph。
- 因為遞迴(recursion)使用了系統的Call Stack。
於記憶體管理(memory management)中的Call Stack。
- 參考：Wikipedia：Call stack。
- 參考：Stack Overflow：What and where are the stack and heap?。

以上是Stack的初步介紹。

下一篇文章將介紹以Array與Linked list實作Stack的方法。

參考資料：

Stack系列文章

Stack: Intro(簡介)
Stack: 以Array與Linked list實作
 Stack: 能夠在O(1)取得最小值的MinStack

回到目錄：

目錄：演算法與資料結構