《資料結構與演算法 with JavaScript》這本書的講解算是相當淺顯,優點是用 JavaScript 把常用的資料結構描述了一遍,書中不少例子取自常見的面試題目,相當貼近實務。業餘讀過之後順便做點筆記。
堆疊是一種特殊的列表:其中的元素只能透過列表的一端存取,那一端稱為「堆疊頂」。它是後進先出(LIFO, Last-In-First-Out)的資料結構。
JavaScript 陣列原生就提供了操作方法:入疊用 push、出疊用 pop。不過 pop 會把元素從陣列中移除,所以若要「只看不做」,還需要自己實作一個查詢方法。

底層用陣列儲存資料,另外補上三個輔助方法:查詢堆疊頂元素(peek)、清空(clear)、取得元素總量(length)。
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(){
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();
}
return word == rword;
}
isPalindrome("aarra"); // false
isPalindrome("aaraa"); // true
這個函數把 word 拆成單一字元依序壓入堆疊,再利用後進先出的特性用 pop 反組裝成新字串,最後比較兩者是否相等。
遞歸寫法:
function factorial(n) {
if (n === 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
堆疊寫法:
function fact(n) {
var s = new Stack();
while (n > 1) {
s.push(n--); // 依序壓入 5, 4, 3, 2
}
var product = 1;
while (s.length() > 0) {
product *= s.pop();
}
return product;
}
fact(5); // 120
先用 while 把 n 遞減壓入堆疊,再用另一個迴圈依後進先出的順序取出相乘。這個例子真正的價值不在效能(遞歸版本更簡潔),而在示範「如何用堆疊把遞歸改寫成迭代」——當語言沒有遞歸、或運算深度可能過深時,這就是標準解法。
今天實作堆疊通常不需要自己寫類別,直接用陣列即可,因為 push/pop 本身就是堆疊操作,而 arr[arr.length - 1] 就是 peek。上面的實作適合用來理解原理;另外原始的 peek 宣告了未使用的參數 element,實作時可以移除。ES6 之後也可以改用 class 語法,並把方法掛在 prototype 上而非每個實例各一份。