堆疊 是「後進先出」(LIFO, Last-In-First-Out)的線性結構,僅允許在棧頂進行插入與移除。JavaScript 陣列原生 push/pop 即可模擬堆疊操作,但封裝類別可提供更豐富介面(如 peek 查看頂端不移除)。
function Stack() {
this.dataStore = [];
this.top = 0;
this.push = push;
this.pop = pop;
this.peek = peek;
this.length = length;
this.clear = clear;
}
function push(element) { this.dataStore[this.top++] = element; }
function pop() { return this.dataStore[--this.top]; }
function peek() { return this.dataStore[this.top - 1]; }
function length() { return this.top; }
function clear() { this.top = 0; }
將字串字元逐一推入堆疊,再彈出組成反轉字串,比較是否相等:
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;
}
console.log(isPalindrome("aarra")); // false
console.log(isPalindrome("aaraa")); // true
遞迴版:
function factorial(n) {
return n === 0 ? 1 : 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(); } // 彈出 2,3,4,5 相乘
return product;
}
console.log(fact(5)); // 120
