堆疊(stack)是什麼？何時會用到這種資料結構？
今天來簡單介紹什麼是堆疊，以及堆疊常見的應用。
目次
什麼是堆疊？
堆疊在程式設計中是一種資料結構，具有先進後出的特性。
所謂的先進後出，是指越早進入堆疊的資料要比較晚才能取出來。
舉例來說，如果我們在一根直立的木棍上，依序放入很多甜甜圈，當你想取出最底下的甜甜圈時，就一定要先拿走在它之上的甜甜圈，這就是先進後出的概念。
常見應用
因為堆疊具有先進後出的特徵，所以經常會被用在記錄返回路徑，比如我們在逛網頁的時候，瀏覽器會知道我們開啟每個網頁的順序，所以我們才能不斷返回上一頁，最終回到第一頁。
如何實作堆疊？
堆疊實作一般會用到陣列（Array）或串列（Linked list）。
以上面甜甜圈的例子來說，陣列就是直立的木棍，存入陣列的資料就是甜甜圈。
來看個程式例子，這裡我們以 javascript 為例：
let stack = [];
let topIndex = -1;
// 存入(push)堆疊
stack[++topIndex] = "a";
stack[++topIndex] = "b";
stack[++topIndex] = "c";
// 從堆疊取出(pop)
let c = stack[topIndex--];
stack = stack.slice(0, stack.length - 1);
let b = stack[topIndex--];
stack = stack.slice(0, stack.length - 1);
let a = stack[topIndex--];
stack = stack.slice(0, stack.length - 1);stack = stack.slice(0, stack.length - 1); 在這裡的意思是，把陣列裡最後一個元素移除，同時陣列的長度也會縮減，若最後 stack 的長度為 0，表示堆疊裡已經沒有東西了。
也可以寫成 stack = stack.slice(0, topIndex); 因為此例中的 topIndex = stack.length - 1。
因為這不是單純邏輯上的巧合，所以這樣寫可能會更符合堆疊的語義，當 topIndex = -1 時，也表示堆疊清空。
不過這在作法上並不是唯一的選擇，你也可以填入 0 或 null 等等，去表示某個堆疊位址是沒有值的，藉此保證堆疊空間的大小是固定不變的。
在上例中我們可以發現，一個資料結構是不是堆疊，主要是跟我們存取資料的方式有關，如果我們用別的步驟存取資料，這個名為 stack 的陣列就不是堆疊了。
為了有效限制存取方式，藉此保證陣列一定會以堆疊的形式被使用，通常來說都會進行某種程度的封裝或抽象化。
事實上，javascript 就內建堆疊的使用方式，所以上面的程式可以改寫成這樣：
let stack = [];
// 存入(push)堆疊
stack.push("a");
stack.push("b");
stack.push("c");
// 從堆疊取出(pop)
let c = stack.pop();
let b = stack.pop();
let a = stack.pop();push() 會從陣列前端開始存入資料，pop() 會從陣列尾端依序取出資料，執行結果會跟第一個例子一模一樣。
經過封裝或抽象化後的程式碼有了清楚的語義，變得更白話，這樣是不是更容易維護了呢～
經典例子
程式設計中最經典的堆疊應用題型是老鼠走迷宮。
如果我們希望有隻老鼠能成功走出迷宮，我們必須讓老鼠知道哪些路徑已經探索過，不要重複走進死路，這時堆疊就能派上用場。
假設迷宮的地板有格子，最簡單的作法就是讓老鼠按照上、右、下、左的順序，一次往一個方向前進一個格子，步驟大致如下：
(1) 站在起點，把起點的座標丟入堆疊，並在地圖上標記這格為已探索。
(2) 檢查上方是否有未探索過的路，若有則前進一格，並把這格的座標丟入堆疊，另在地圖上標記為己探索。
(3) 如果上方不能走，就檢查右方是否有未探索過的路，若有則前進一格，並把這格的座標丟入堆疊，另在地圖上標記為已探索，然後再次從(2)開始判斷。
(4) 如果右方不能走，就檢查下方是否有未探索過的路，若有則前進一格，並把這格的座標丟入堆疊，另在地圖上標記為已探索，然後再次從(2)開始判斷。
(5) 如果下方不能走，就檢查左方是否有未探索過的路，若有則前進一格，並把這格的座標丟入堆疊，另在地圖上標記為已探索，然後再次從(2)開始判斷。
(6) 如果左方不能走，表示老鼠走到死路了，我們要依照堆疊的記錄沿途返回，每返回一格都要再次從(2)開始判斷。
畫成流程圖來看會比較清楚（點圖可放大）：
從執行結果來看，因為老鼠有用堆疊記錄行走順序，所以可以沿途返回而不會迷路，並且地圖上有標記哪些路已探索，所以不會去重複探索那些已知的死路，只要迷宮確實有出口，老鼠就能用機械化的步驟走出迷宮，而最後堆疊裡的記錄也會是老鼠走出迷宮的路徑記錄。
這個解決問題的過程正好也是深度優先搜尋（DFS）演算法的一種應用。
呼叫堆疊
現代程式語言幾乎都有函式(function)的設計，讓我們先來看一段 javascript 程式碼。
1. let a = 10;
2. let b = 20;
3. let result = 0;
4.
5. result = add(a, b);
6. console.log("結果: " + result);
7.
8. function add(a, b) {
9. return a + b;
10. }以上面的例子來說，當程式碼執行到第 5 行時，遇到了 add()，但是 add() 的定義是在第 8 行，所以程式必須先跳到第 8 行執行完該程式區塊後，再返回第 5 行，把 add() 的結果賦值給 result，接著才執行第 6 行顯示結果。
函式呼叫同樣有沿路返回的特性，所以許多程式語言的底層會使用堆疊來實現，一般稱為「呼叫堆疊（Call stack）」。
如此一來，當你的函式裡還有另一個函式、一層又一層呼叫下去時，程式依然知道最終該返回哪一行繼續執行。
（為求說明簡單，此處省略了程式計數器與記憶體位址等較複雜的觀念，但概念上大致相同。）
其他應用
堆疊還有很多其他應用，比如在系統程式設計中，四則運算會利用堆疊來達成先乘除、後加減、括號優先處理的目的。
某些程式語言在呼叫函式時，可以傳入不定數量的參數，也和堆疊的運用有關。
總的來說，在解決工程學問題時，堆疊是很常見的應用，但是大多數程式語言的函式庫都已經提供了現成工具，讓我們在開發商務軟體或系統時，能在不知不覺中使用堆疊，減少了直接碰觸堆疊的需要。
總結
堆疊是一種典型資料結構，應用情境很多，只是一般的業務邏輯比較少有機會運用，所以有時難以察覺它的重要性。
比較有可能的或許是Debug，比如在瀏覽器的開發人員工具裡就有觀察呼叫堆疊的視窗。
只要在 js 程式碼某處寫一行 debugger（或是在開發人員工具中找到 js 程式碼，指定中斷點），讓程式中斷、改用單步執行，就能看到函式的呼叫順序，藉此尋找問題。
我自己幾乎不會這麼做，但的確在公司見過有人這麼做，供大家參考。
（業務邏輯是泛指所有與解決工程學問題無關的程式邏輯，通常出現在 OSI 模型中的應用層，是構成應用程式核心功能的主要部份。大部份軟體公司的工作都活躍在應用層，舉凡網頁前後端、手機APP、Word、Excel，這些程式開發大多屬於應用層的範疇。）