DIV CSS 佈局教程網

用 JavaScript 實現棧:Stack 類封裝與三個經典應用
編輯:JavaScript技巧     

棧(Stack)是計算機科學裡最基礎的數據結構之一。維基百科的定義是:棧是一種特殊的串列形式數據結構,只允許在鏈表或數組的一端(稱為棧頂,top)進行插入(push)與刪除(pop)操作,因此按照後進先出(LIFO, Last In First Out)的原則運作。

下面用 ES6 的 class 語法把它實現出來,並順手做三道經典練習題。

實現一個 Stack 類

/**
 * Stack 類
 */
class Stack {
  constructor() {
    this.data = []; // 用數組保存數據
    this.top = 0;   // 棧頂指針,同時也是元素個數
  }

  // 入棧,支持一次壓入多個元素
  push() {
    const args = [...arguments];
    args.forEach(arg => this.data[this.top++] = arg);
    return this.top;
  }

  // 出棧
  pop() {
    if (this.top === 0) throw new Error('The stack is already empty!');
    const peek = this.data[--this.top];
    this.data = this.data.slice(0, -1);
    return peek;
  }

  // 查看棧頂元素,不出棧
  peek() {
    return this.data[this.top - 1];
  }

  // 元素個數
  length() {
    return this.top;
  }

  // 清空棧
  clear() {
    this.top = 0;
    return this.data = [];
  }

  // 是否為空
  isEmpty() {
    return this.top === 0;
  }
}

// 使用示例
const stack = new Stack();
stack.push(1);
stack.push(2, 3);
console.log(stack.data);   // [1, 2, 3]
console.log(stack.peek()); // 3
console.log(stack.pop());  // 3,此時 data 為 [1, 2]
stack.push(3);
console.log(stack.length()); // 3
stack.clear();               // data 變為 []

用數組存數據、用 top 記錄棧頂位置,是實現棧最直白的思路。epxress 出棧前先判空也是必要的防禦。

應用一:十進制轉二進制、八進制

進制轉換的核心是「除基取餘,逆序輸出」——「逆序」兩個字正好對應棧的後進先出。

/**
 * 將數字轉換為指定進制
 */
const numConvert = (num, base) => {
  const stack = new Stack();
  let converted = '';

  while (num > 0) {
    stack.push(num % base);      // 取餘入棧
    num = Math.floor(num / base);
  }

  while (stack.length() > 0) {
    converted += stack.pop();    // 依次出棧即為正確順序
  }

  return +converted;
};

console.log(numConvert(10, 2)); // 1010

應用二:判斷回文

把字符串逐個字符壓棧,再全部弹出拼接,得到的就是反轉串。與原串比較即可判定是否回文。

/**
 * 判斷給定字符串或數字是否是回文
 */
const isPalindrome = words => {
  const stack = new Stack();
  let wordsCopy = '';

  words = words.toString();
  Array.prototype.forEach.call(words, word => stack.push(word));

  while (stack.length() > 0) {
    wordsCopy += stack.pop();
  }

  return words === wordsCopy;
};

console.log(isPalindrome('1a121a1')); // true
console.log(isPalindrome(2121));      // false

總結

棧的實現代碼很短,但思想滲透得很廣:函數調用棧、表達式求值、瀏覽器后退、DOM 遍歷的非遞歸改寫,背後都是同一套 LIFO 模型。上面幾個算法僅為演示棧的用法,並非性能最優解,但足以說明問題:遇到「逆序」需求時,先想想棧。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved