DIV CSS 佈局教程網

JavaScript 資料結構與演算法(一):堆疊
編輯:JavaScript綜合知識     

《資料結構與演算法 with JavaScript》這本書的講解算是相當淺顯,優點是用 JavaScript 把常用的資料結構描述了一遍,書中不少例子取自常見的面試題目,相當貼近實務。業餘讀過之後順便做點筆記。

堆疊結構

堆疊是一種特殊的列表:其中的元素只能透過列表的一端存取,那一端稱為「堆疊頂」。它是後進先出(LIFO, Last-In-First-Out)的資料結構。

JavaScript 陣列原生就提供了操作方法:入疊用 push、出疊用 pop。不過 pop 會把元素從陣列中移除,所以若要「只看不做」,還需要自己實作一個查詢方法。

實作一個堆疊類別

底層用陣列儲存資料,另外補上三個輔助方法:查詢堆疊頂元素(peek)、清空(clear)、取得元素總量(length)。

function Stack(){
  this.dataStore = [];
  this.top = 0;
  this.push = push;
  this.pop = pop;
  this.peek = peek;
  this.length = length;
}

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

function peek(){
  return this.dataStore[this.top - 1];
}

function pop(){
  return this.dataStore[--this.top];
}

function clear(){
  this.top = 0;
}

function length(){
  return this.top;
}

應用一:判斷回文

回文是指一個單詞、數字或短語,從前往後讀與從後往前讀完全相同,例如 12321、abcba。

最直覺的思路是:把字元反轉之後若與原始字串相等,就是回文。而「反轉」正好是堆疊的拿手好戲:

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;
}

isPalindrome("aarra");   // false
isPalindrome("aaraa");   // true

這個函數把 word 拆成單一字元依序壓入堆疊,再利用後進先出的特性用 pop 反組裝成新字串,最後比較兩者是否相等。

應用二:用堆疊實作階乘

遞歸寫法:

function factorial(n) {
  if (n === 0) {
    return 1;
  } else {
    return 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();
  }
  return product;
}

fact(5);   // 120

先用 while 把 n 遞減壓入堆疊,再用另一個迴圈依後進先出的順序取出相乘。這個例子真正的價值不在效能(遞歸版本更簡潔),而在示範「如何用堆疊把遞歸改寫成迭代」——當語言沒有遞歸、或運算深度可能過深時,這就是標準解法。

補充:現代寫法

今天實作堆疊通常不需要自己寫類別,直接用陣列即可,因為 push/pop 本身就是堆疊操作,而 arr[arr.length - 1] 就是 peek。上面的實作適合用來理解原理;另外原始的 peek 宣告了未使用的參數 element,實作時可以移除。ES6 之後也可以改用 class 語法,並把方法掛在 prototype 上而非每個實例各一份。

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