DIV CSS 佈局教程網

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

上一篇介紹了列表。列表是最簡單的結構,但要處理比較複雜的場景時它顯得過於簡陋,於是我們需要某種類似列表、但能力更強的資料結構——堆疊。堆疊是一種高效的結構,因為資料只能在堆疊頂端加入或移除,操作很快,實作也很容易。

一、堆疊的操作特性

堆疊是一種特殊的列表,其中的元素只能透過同一端存取,這一端稱為「堆疊頂」。想像餐館裡洗盤子:只能先洗最上面那個,洗完之後新的盤子也只能疊回最上面。這種「後進先出」(LIFO, Last In First Out)的特性正是堆疊的核心。

由於後進先出,任何不在堆疊頂的元素都無法存取;要拿到堆疊底的元素,必須先把上面的逐一移開。堆疊的兩項主要操作是入堆疊(push)與出堆疊(pop)。pop 雖然能取得堆疊頂元素,但呼叫後該元素就永久離開堆疊了。另一個常用方法是 peek(),它只回傳堆疊頂元素而不移除。

除了 push、pop、peek 這三個主要方法,實務上通常還會補上:clear() 清除堆疊內所有元素,以及 length() 回傳元素個數。

二、實作堆疊類別

function Stack() {
  this.dataStore = []; // 保存堆疊內的所有元素
  this.top = 0;        // 記錄堆疊頂位置
}

dataStore 負責存放元素,變數 top 記錄堆疊頂位置,初始化為 0,代表堆疊頂對應陣列的起始位置;每當有元素被壓入,這個值就隨之遞增。

push():壓入新元素

把新元素存進陣列中 top 所指的位置,然後 top 加一,指向下一個空位。

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

pop():彈出堆疊頂元素

與 push 相反,回傳堆疊頂元素並將 top 減一。

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

peek():只看不拿

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

length() 與 clear()

function length() {
  return this.top;
}

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

完整程式碼

function Stack() {
  this.dataStore = [];
  this.top = 0;
}

Stack.prototype = {

  // 向堆疊中壓入一個新元素
  push: function(element) {
    this.dataStore[this.top++] = element;
  },

  // 訪問堆疊頂元素,該元素會永久被移除
  pop: function() {
    return this.dataStore[--this.top];
  },

  // 回傳陣列中 top - 1 位置的元素,即堆疊頂元素
  peek: function() {
    return this.dataStore[this.top - 1];
  },

  // 堆疊內存儲了多少個元素
  length: function() {
    return this.top;
  },

  // 清空堆疊
  clear: function() {
    this.top = 0;
  }
};

var stack = new Stack();
stack.push("a");
stack.push("b");
stack.push("c");
console.log(stack.length()); // 3
console.log(stack.peek());   // c

var popped = stack.pop();
console.log(popped);         // c

console.log(stack.peek());   // b

stack.push("d");
console.log(stack.peek());   // d

stack.clear();
console.log(stack.length()); // 0
console.log(stack.peek());   // undefined

實際應用:用堆疊實作階乘

以 5! = 5 × 4 × 3 × 2 × 1 為例:

function fact(n) {
  var s = new Stack();
  while (n > 1) {
    s.push(n--);
  }
  var product = 1;
  while (s.length() > 0) {
    product *= s.pop();
  }
  return product;
}
console.log(fact(5)); // 120

邏輯是:把數字 5 傳入函數後,用 while 迴圈在每次自減之前把當前值壓入堆疊,直到 n 小於 1 為止。接著定義 product,迴圈中每次呼叫 pop() 取出堆疊頂元素並相乘,同時該元素被移除,直到堆疊清空。最終 product 就等于 5 × 4 × 3 × 2 × 1。

堆疊在實務中的用處遠不止於教學示範:函數呼叫堆疊、瀏覽器的后退紀錄、編輯器的復原功能、表達式的括號配對檢查、以及深度優先搜尋,背後都是同一套後進先出的邏輯。

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