萬盛學電腦網

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

JavaScript 數據結構與算法:堆疊(Stack)完整實現與應用

堆疊概念

堆疊是**後進先出(LIFO, Last In First Out)**的線性表,僅允許在一端(棧頂)進行插入(push)與刪除(pop)操作。生活範例:疊盤子、瀏覽器歷史記錄、函式呼叫堆疊。

核心操作

  • push(element):元素入棧。
  • pop():移除並回傳棧頂元素。
  • peek():查看棧頂元素但不移除。
  • length() / size():元素數量。
  • clear():清空堆疊。

ES6 Class 實現

class Stack {
  constructor() {
    this.dataStore = [];
    this.top = 0; // 指向下一個可插入位置,即棧頂索引
  }

  push(element) {
    this.dataStore[this.top++] = element;
  }

  pop() {
    if (this.top === 0) return undefined; // 空棧
    return this.dataStore[--this.top];
  }

  peek() {
    if (this.top === 0) return undefined;
    return this.dataStore[this.top - 1];
  }

  length() { return this.top; }
  size() { return this.top; } // 別名

  clear() { this.top = 0; } // 保留底層陣列,避免頻繁 GC

  // 迭代器:從棧頂到棧底
  *[Symbol.iterator]() {
    for (let i = this.top - 1; i >= 0; i--) yield this.dataStore[i];
  }

  toString() { return this.dataStore.slice(0, this.top).join(' <- '); }
}

應用範例一:十進制轉二進制

function toBinary(num) {
  const stack = new Stack();
  if (num === 0) return '0';
  while (num > 0) {
    stack.push(num % 2);
    num = Math.floor(num / 2);
  }
  let binary = '';
  while (stack.length()) binary += stack.pop();
  return binary;
}
console.log(toBinary(10)); // 1010

應用範例二:括號匹配驗證

function isBalanced(str) {
  const stack = new Stack();
  const pairs = { ')': '(', ']': '[', '}': '{' };

  for (const ch of str) {
    if ('([{'.includes(ch)) stack.push(ch);
    else if (')]}'.includes(ch)) {
      if (stack.length() === 0 || stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length() === 0;
}

console.log(isBalanced('({[]})')); // true
console.log(isBalanced('({[})'));  // false

應用範例三:中綴表達式轉後綴(逆波蘭表示法)

function infixToPostfix(expr) {
  const stack = new Stack();
  const output = [];
  const prec = { '+': 1, '-': 1, '*': 2, '/': 2, '^': 3 };

  const tokens = expr.match(/\d+|\+|\-|\*|\/|\^|\(|\)/g);
  for (const token of tokens) {
    if (!isNaN(token)) output.push(token);
    else if (token === '(') stack.push(token);
    else if (token === ')') {
      while (stack.length() && stack.peek() !== '(') output.push(stack.pop());
      stack.pop(); // 移除 '('
    } else { // 運算子
      while (stack.length() && stack.peek() !== '(' && prec[stack.peek()] >= prec[token]) {
        output.push(stack.pop());
      }
      stack.push(token);
    }
  }
  while (stack.length()) output.push(stack.pop());
  return output.join(' ');
}

console.log(infixToPostfix('3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'));
// 3 4 2 * 1 5 - 2 3 ^ ^ / +

應用範例四:階乘計算(非遞迴)

function factorial(n) {
  const stack = new Stack();
  while (n > 1) stack.push(n--);
  let result = 1;
  while (stack.length()) result *= stack.pop();
  return result;
}
console.log(factorial(5)); // 120

複雜度分析

操作時間空間
push / pop / peek / lengthO(1)O(1)
clearO(1)O(1)

現代 JS 替代方案

陣列原生 push/pop 已是高度優化的堆疊實現,簡單場景直接使用 [] 即可:

const stack = [];
stack.push(1); stack.push(2);
stack.pop(); // 2

自定義 Class 適用於:需要封裝額外邏輯(如最小值棧、持久化、序列化)、教學示範、或需明確語義區分「堆疊」與「陣列」的大型專案。

copyright © 萬盛學電腦網 all rights reserved