JavaScript資料結構與演算法堆疊詳解_javascript技巧

在上一篇博客介紹了下列表，列表是最簡單的一種結構，但是如果要處理一些比較複雜的結構，列表顯得太簡陋了，所以我們需要某種和列表類似但是更複雜的資料結構---棧。棧是一種高效率的資料結構，因為資料只能在棧頂新增或刪除，所以這樣操作很快，而且容易實現。

一：對棧的操作。

棧是一種特殊的列表，棧內的元素只能透過列表的一端訪問，這一端陳為棧頂。例如餐廳裡面洗盤子，只能先洗最上面的盤子，盤子洗完後，也只能螺到這一摞盤子的最上面。堆疊被稱為 "後入先出"（LIFO）的資料結構。

由於堆疊具有後入先出的特點，所以任何不在棧頂的元素都無法訪問，為了得到棧低的元素，必須先拿掉上面的元素。我們可以對堆疊的兩種主要操作是將一個元素 壓入堆疊 和 將一個元素 彈出堆疊。入棧我們可以使用方法push（）方法，出棧我們使用pop（）方法。 pop（）方法雖然可以存取棧頂的元素，但是呼叫該方法後，棧頂元素也就從棧中被永久性的刪除了。另一個我們很常用的方法是peek（），該方法只會傳回棧頂元素，而不刪除它。

入棧與出棧的實列圖如下：

push(),pop()和peek（）是堆疊的三個主要方法，但是堆疊還有其他方法和屬性。如下：

clear（）：清除堆疊內的所有元素。

length(): 記錄堆疊內元素的個數。

二：對棧的實作如下：

我們可以先實作堆疊類別的方法開始；如下：
 

複製程式碼 程式碼如下:

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

 如上：dataStore 是保存堆疊內的所有元素。變數top記錄堆疊頂的位置，初始化為0. 表示棧頂對應陣列的起始位置為0，若有元素被壓入堆疊。該變數值將隨之變化。

我們還有以下幾個方法：push(), pop(), peek(),clear()，length();

1.  push()方法；當向棧內壓入一個新元素時，需要將其保存在數組中變數top所對應的位置，然後top值加1，讓其指向數組中下一個位置。如下碼：

複製程式碼 程式碼如下:

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

2. pop()方法與push（）方法相反---它傳回棧頂元素，同時將top值減1.如下程式碼：

複製程式碼 程式碼如下:

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

3. peek()方法傳回數組的第top-1個位置的元素，即棧頂元素；

複製程式碼 程式碼如下:

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

4. length()方法 有時候我們要知道棧內有多少個元素，我們可以透過回傳變數top值的方式來傳回堆疊內的元素個數，如下程式碼：

複製程式碼 程式碼如下:

     function length(){
         return this.top;
     }

5. clear(); 有時候我們要清空棧，我們將變數top值設為0；如下程式碼：

複製程式碼 程式碼如下:

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

demo實例如下：

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！ = 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));

上面的程式碼意義是：先數字5傳入函數，使用while循環，每次自減1的之前，把自己使用棧的函數push（）壓入棧內，直到變數n  小於 1為止。接著定義一個變數product；透過堆疊的length()的方法判斷是否大於0 且每次執行 product* = s.pop();  pop()方法傳回棧頂元素，且從堆疊中刪掉該元素。所以每次執行一次，就刪掉一個元素，直到s.length()