DIV CSS 佈局教程網

JavaScript 資料結構與演算法入門(一):堆疊(Stack)完整實作
編輯:關於JavaScript     

前言

《資料結構與演算法》這類書通常以 JavaScript 作為描述語言,好處是門檻低、示例輕巧,把常用的資料結構講得相當直觀;書中不少例子直接取自常見的面試題,實用性不錯。業餘時間翻了一遍,順手把筆記整理出來,也方便回頭複習。

Git 原始碼下載:
https://github.com/JsAaron/data_structure.git

一、堆疊到底是什麼

堆疊可以理解為一種「受限的列表」:所有元素只能從同一端進出,這一端稱為棧頂。它的核心規則是後進先出(LIFO,Last-In-First-Out),最先放進去的元素,往往是最後才被取出來的那一個。

JavaScript 陣列自帶的 push 與 pop 剛好對應入棧與出棧,只不過 pop 會把元素從陣列中真正移除。

二、動手實作一個堆疊類

底層直接用陣列存資料,並額外維護一個 top 計數器指向棧頂位置。因為 pop 會刪資料,所以還需要一個只看不能拿的 peek;再加上清空用的 clear、取得元素總量的 length,以及判斷堆疊是否已空的 empty。

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(element){
  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();
  }
  if (word == rword) {
    return true;
  } else {
    return false;
  }
}

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

執行過程其實很單純:先把 word 拆成單個字元依序壓入堆疊,再利用後進先出的特性,用 pop 逐一取出並重組,最後把重組結果和原字串比對即可。

四、應用場景二:用堆疊取代遞迴

以階乘為例:5! = 5 × 4 × 3 × 2 × 1 = 120。

傳統寫法是遞迴:

function factorial(n) {
  if (n === 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

但如果改用堆疊,把每一步的中間狀態壓棧,再依序彈出相乘,同樣能得到答案,而且不必依賴呼叫堆疊:

function fact(n) {
  var s = new Stack()
  while (n > 1) {
    // [5,4,3,2]
    s.push(n--);
  }
  var product = 1;
  while (s.length() > 0) {
    product *= s.pop();
  }
  return product;
}

fact(5) // 120

第一個迴圈負責把 n 遞減後逐一壓棧,第二個迴圈再把棧中元素依後進先出原則彈出,與 product 累乘,最終得到 120。

五、小結

堆疊的資料結構本身非常簡單,真正的價值在於它提供了一種「相反的處理順序」。無論是表達式求值、瀏覽器的返回歷史,還是函式呼叫本身,背後都有堆疊的身影。把這個基礎打穩,後續的佇列、鏈表、樹與圖會更好理解。

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