前言
《資料結構與演算法》這類書通常以 JavaScript 作為描述語言,好處是門檻低、示例輕巧,把常用的資料結構講得相當直觀;書中不少例子直接取自常見的面試題,實用性不錯。業餘時間翻了一遍,順手把筆記整理出來,也方便回頭複習。
Git 原始碼下載:
https://github.com/JsAaron/data_structure.git
堆疊可以理解為一種「受限的列表」:所有元素只能從同一端進出,這一端稱為棧頂。它的核心規則是後進先出(LIFO,Last-In-First-Out),最先放進去的元素,往往是最後才被取出來的那一個。
JavaScript 陣列自帶的 push 與 pop 剛好對應入棧與出棧,只不過 pop 會把元素從陣列中真正移除。

底層直接用陣列存資料,並額外維護一個 top 計數器指向棧頂位置。因為 pop 會刪資料,所以還需要一個只看不能拿的 peek;再加上清空用的 clear、取得元素總量的 length,以及判斷堆疊是否已空的 empty。
function Stack(){
this.dataStore = []
this.top = 0;
this.push = push
this.pop = pop
this.peek = peek
this.length = length;
}
function push(element){
this.dataStore[this.top++] = element;
}
function peek(element){
return this.dataStore[this.top-1];
}
function pop(){
return this.dataStore[--this.top];
}
function clear(){
this.top = 0
}
function length(){
return this.top
}
回文指的是正著讀、反著讀都一模一樣的內容,例如 12321、abcba。最直白的思路是:把字元倒序重組一次,如果和原字串完全相同,那它就是回文。
而「倒序」這件事,正是堆疊最擅長的:
function isPalindrome(word) {
var s = new Stack()
for (var i = 0; i < word.length; i++) {
s.push(word[i])
}
var rword = "";
while (s.length() > 0) {
rword += s.pop();
}
if (word == rword) {
return true;
} else {
return false;
}
}
isPalindrome("aarra") // false
isPalindrome("aaraa") // true
執行過程其實很單純:先把 word 拆成單個字元依序壓入堆疊,再利用後進先出的特性,用 pop 逐一取出並重組,最後把重組結果和原字串比對即可。
以階乘為例:5! = 5 × 4 × 3 × 2 × 1 = 120。
傳統寫法是遞迴:
function factorial(n) {
if (n === 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
但如果改用堆疊,把每一步的中間狀態壓棧,再依序彈出相乘,同樣能得到答案,而且不必依賴呼叫堆疊:
function fact(n) {
var s = new Stack()
while (n > 1) {
// [5,4,3,2]
s.push(n--);
}
var product = 1;
while (s.length() > 0) {
product *= s.pop();
}
return product;
}
fact(5) // 120
第一個迴圈負責把 n 遞減後逐一壓棧,第二個迴圈再把棧中元素依後進先出原則彈出,與 product 累乘,最終得到 120。
堆疊的資料結構本身非常簡單,真正的價值在於它提供了一種「相反的處理順序」。無論是表達式求值、瀏覽器的返回歷史,還是函式呼叫本身,背後都有堆疊的身影。把這個基礎打穩,後續的佇列、鏈表、樹與圖會更好理解。