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;         // 記錄堆疊頂位置
}

top 初始化為 0,代表堆疊頂對應陣列的起始位置;每壓入一個元素,它就隨之遞增。

push():壓入新元素

把元素放在 top 所指的位置,然後 top 加一指向下一格:

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

pop():彈出堆疊頂

與 push 相反,先減一再取值:

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

peek():僅讀取堆疊頂

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

length():元素個數

function length(){
  return this.top;
}

clear():清空堆疊

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 迴圈每次遞減 1 並把當前值壓入堆疊,直到 n 不再大於 1。接著定義 product,透過 length() 判斷堆疊是否還有元素,每次 pop() 取出堆疊頂並相乘。由於 pop() 取完就移除,迴圈會自動收束,最終得到 5×4×3×2×1。

堆疊在真實場景中的用武之地

這個階乘例子只是為了示範操作,實務上堆疊的價值遠不止於此。函數呼叫本身就是一個堆疊(呼叫堆疊),這也是遞迴太深會拋出堆疊溢出的原因;瀏覽器的返回上一頁是堆疊;程式的撤銷(undo)功能、括號配對檢查、表達式的中序轉後序、以及深度優先搜尋,背後都是同一個資料結構。理解「後進先出」這四個字,等於拿到了這一整類問題的鑰匙。

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