資料結構系列就從堆疊(Stack)開始。
堆疊是一種遵循後進先出原則(LIFO,Last In First Out)的有序集合,堆疊頂永遠是最新加入的元素。
最貼切的比喻是一疊放在箱子裡的書:要拿最底下那本,得先把上面的書一本本移開。你不能跳過上面的直接拿底下那本。

用陣列來模擬堆疊是最省事的做法,因為陣列本身就有 push 與 pop:
/**
* 堆疊的建構函式
*/
function Stack() {
// 用陣列來模擬堆疊
var items = [];
}
注意 items 宣告在閉包內部而非 this 上,這樣外部就無法直接存取,達到封裝的效果。
新元素放在陣列的最後一位,直接用陣列的 push 即可:
/**
* 將元素送入堆疊,置於陣列的最後一位
* @param {Any} element 可接受任意型別
*/
this.push = function(element) {
items.push(element);
};
把堆疊頂元素彈出並回傳其值,同樣直接借用陣列的 pop:
/**
* 彈出堆疊頂元素
* @return {Any} 回傳被彈出的值
*/
this.pop = function() {
return items.pop();
};
只讀不取,用陣列長度定位最後一個元素:
/**
* 查看堆疊頂元素
* @return {Any} 回傳堆疊頂元素
*/
this.peek = function() {
return items[items.length - 1];
}
前三者是堆疊的核心,其餘一次列出。因為接下來要談的佇列(Queue)會與這部分有大量重疊:
/**
* 確認堆疊是否為空
* @return {Boolean} 為空回傳 true,否則 false
*/
this.isEmpty = function() {
return items.length === 0;
};
/** 清空堆疊中所有內容 */
this.clear = function() {
items = [];
};
/**
* 回傳堆疊的長度
* @return {Number}
*/
this.size = function() {
return items.length;
};
/** 以字串顯示堆疊中所有內容 */
this.print = function() {
console.log(items.toString());
};
書中有個經典範例:把十進位數字轉成二進位。原理是反覆除以 2 並取餘數,得到的餘數序列剛好是「由低位到高位」,因此用堆疊反轉一次就能得到正確結果——這正是堆疊最典型的用途。
/**
* 將 10 進位數字轉為 2 進位數字
* @param {Number} decNumber 要轉換的 10 進位數字
* @return {String} 轉換後的 2 進位字串
*/
function divideBy2(decNumber) {
var remStack = new Stack(),
rem,
binaryString = '';
while (decNumber > 0) {
rem = Math.floor(decNumber % 2);
remStack.push(rem);
decNumber = Math.floor(decNumber / 2);
}
while (!remStack.isEmpty()) {
binaryString += remStack.pop().toString();
}
return binaryString;
}
一、ES6 可以用 class 寫得更清楚。上面的寫法刻意用 var items 藏在閉包裡來模擬私有成員,這是 ES6 之前的通用手法。今天可以改用 class 搭配 # 私有欄位:
class Stack {
#items = [];
push(element) { this.#items.push(element); }
pop() { return this.#items.pop(); }
peek() { return this.#items[this.#items.length - 1]; }
get isEmpty() { return this.#items.length === 0; }
get size() { return this.#items.length; }
clear() { this.#items = []; }
}
二、clear() 有一個隱藏問題。items = [] 會讓 items 指向一個新陣列,若外部曾經透過閉包持有舊陣列的參照,兩者就會分離。改用 items.length = 0 則會原地清空,語意更準確,也避免了這個潛在的混淆。
三、邊界情況值得處理。空堆疊呼叫 pop() 會回傳 undefined,peek() 同理。若呼叫方未做檢查,錯誤會延後到很遠的地方才爆發。實務上可以選擇拋出錯誤,或明確回傳 undefined 並在文件註明。
堆疊在實際開發中應用很廣:函式呼叫的呼叫堆疊、瀏覽器的後退紀錄、運算式的括號配對檢查、縮排(undo)機制、深度優先搜尋,都是堆疊的場景。掌握它的核心只有三個操作——push、pop、peek,而其餘一切都建立在「後進先出」這個簡單約束上。
到此堆疊的學習告一段落,希望對你的 JavaScript 資料結構學習有所幫助。