萬盛學電腦網

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

JavaScript 數組模擬堆棧:push/pop 實現後進先出 (LIFO) 數據結構

數組原生 push() 和 pop() 完美契合堆棧(Stack)的後進先出(LIFO)特性,無需額外封裝即可直接使用。

基本操作

const stack = [];

// 入棧
stack.push('one');
stack.push('two');
stack.push('three');
console.log(stack); // ['one', 'two', 'three']

// 出棧
console.log(stack.pop()); // 'three'
console.log(stack.pop()); // 'two'
console.log(stack.pop()); // 'one'
console.log(stack.pop()); // undefined (棧空)

封裝 Stack 類(可選)

class Stack {
  constructor() { this.items = []; }
  push(item) { this.items.push(item); }
  pop() { return this.items.pop(); }
  peek() { return this.items[this.items.length - 1]; }
  isEmpty() { return this.items.length === 0; }
  size() { return this.items.length; }
  clear() { this.items = []; }
  toArray() { return [...this.items]; }
}

// 使用
const s = new Stack();
s.push(1).push(2).push(3);
console.log(s.peek()); // 3
console.log(s.pop());  // 3
console.log(s.toArray()); // [1,2]

應用場景

  • 函數調用棧追蹤
  • 瀏覽器前進/後退歷史
  • 撤銷/重做功能
  • 括號匹配、表達式求值
  • 深度優先搜索 (DFS)

括號匹配實例

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

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

總結

JS 數組原生支持堆棧操作,push/pop 時間複雜度 O(1),是實現 LIFO 邏輯的最佳選擇。理解堆棧原理,能優雅解決括號匹配、路徑回溯、狀態回滾等經典問題。

copyright © 萬盛學電腦網 all rights reserved