萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 資料結構與演算法(一):堆疊 實作與應用

堆疊 是「後進先出」(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; }

應用範例 1:回文檢測

將字串字元逐一推入堆疊,再彈出組成反轉字串,比較是否相等:

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

應用範例 2:遞迴與堆疊實現階乘

遞迴版:

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

核心觀念

  • 堆疊將「延遲處理」的資料暫存,最後反序處理
  • 遞迴本質即系統維護的呼叫堆疊,手動堆疊可轉換為迭代形式
  • 適用場景:括號匹配、運算式求值、瀏覽器歷史記錄、撤銷/重做功能
copyright © 萬盛學電腦網 all rights reserved