欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之棧詳解

 更新時(shí)間：2015年03月12日 10:08:08   投稿：junjie  
這篇文章主要介紹了JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之棧詳解,本文講解了對(duì)棧的操作、對(duì)棧的實(shí)現(xiàn)實(shí)例等內(nèi)容,需要的朋友可以參考下

在上一篇博客介紹了下列表，列表是最簡單的一種結(jié)構(gòu)，但是如果要處理一些比較復(fù)雜的結(jié)構(gòu)，列表顯得太簡陋了，所以我們需要某種和列表類似但是更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)---棧。棧是一種高效的數(shù)據(jù)結(jié)構(gòu)，因?yàn)閿?shù)據(jù)只能在棧頂添加或刪除，所以這樣操作很快，而且容易實(shí)現(xiàn)。

一：對(duì)棧的操作。

棧是一種特殊的列表，棧內(nèi)的元素只能通過列表的一端訪問，這一端陳為棧頂。比如餐館里面洗盤子，只能先洗最上面的盤子，盤子洗完后，也只能螺到這一摞盤子的最上面。棧被稱為 "后入先出"（LIFO）的數(shù)據(jù)結(jié)構(gòu)。

由于棧具有后入先出的特點(diǎn)，所以任何不在棧頂?shù)脑囟紵o法訪問，為了得到棧低的元素，必須先拿掉上面的元素。我們可以對(duì)棧的兩種主要操作是將一個(gè)元素 壓入棧 和 將一個(gè)元素 彈出棧。入棧我們可以使用方法push（）方法，出棧我們使用pop（）方法。pop（）方法雖然可以訪問棧頂?shù)脑兀钦{(diào)用該方法后，棧頂元素也就從棧中被永久性的刪除了。另一個(gè)我們很常用的方法是peek（），該方法只返回棧頂元素，而不刪除它。

入棧和出棧的實(shí)列圖如下：

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

clear（）：清除棧內(nèi)的所有元素。

length(): 記錄棧內(nèi)元素的個(gè)數(shù)。

二：對(duì)棧的實(shí)現(xiàn)如下：

我們可以先實(shí)現(xiàn)棧類的方法開始；如下：
 

復(fù)制代碼 代碼如下:

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

 如上：dataStore 是保存棧內(nèi)的所有元素。變量top記錄棧頂?shù)奈恢?，初始化?. 表示棧頂對(duì)應(yīng)數(shù)組的起始位置為0，如果有元素被壓入棧。該變量值將隨之變化。

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

1.  push()方法；當(dāng)向棧內(nèi)壓入一個(gè)新元素時(shí)，需要將其保存在數(shù)組中變量top所對(duì)應(yīng)的位置，然后top值加1，讓其指向數(shù)組中下一個(gè)位置。如下代碼：

復(fù)制代碼 代碼如下:

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

2. pop()方法與push（）方法相反---它返回棧頂元素，同時(shí)將top值減1.如下代碼：
復(fù)制代碼 代碼如下:

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

3. peek()方法返回?cái)?shù)組的第top-1個(gè)位置的元素，即棧頂元素；
復(fù)制代碼 代碼如下:

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

4. length()方法 有時(shí)候我們要知道棧內(nèi)有多少個(gè)元素，我們可以通過返回變量top值的方式返回棧內(nèi)的元素個(gè)數(shù)，如下代碼：
復(fù)制代碼 代碼如下:

     function length(){
         return this.top;
     }

5. clear(); 有時(shí)候我們要清空棧，我們將變量top值設(shè)為0；如下代碼：
復(fù)制代碼 代碼如下:

   function clear() {

        this.top = 0;

    }


如下所有代碼：
復(fù)制代碼 代碼如下:

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

Stack.prototype = {
   
    // 向棧中壓入一個(gè)新元素
    push: function(element) {
        this.dataStore[this.top++] = element;
    },
    // 訪問棧頂元素，棧頂元素永久的被刪除了
    pop: function(){
        return this.dataStore[--this.top];
    },
    // 返回?cái)?shù)組中的 top-1 個(gè)位置的元素，即棧頂元素
    peek: function(){
        return this.dataStore[this.top - 1];
    },
    // 棧內(nèi)存儲(chǔ)了多少個(gè)元素
    length: function(){
        return this.top;
    },
    // 清空棧
    clear: function(){
        this.top = 0;
    }
};

demo實(shí)例如下：

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

下面我們可以實(shí)現(xiàn)一個(gè)階乘函數(shù)的遞歸定義；比如5！的階乘 5！= 5 * 4 * 3 * 2 * 1；

如下代碼：

復(fù)制代碼 代碼如下:

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

上面的代碼含義是：先數(shù)字5傳入函數(shù)，使用while循環(huán)，每次自減1的之前，把自己使用棧的函數(shù)push（）壓入棧內(nèi)，直到變量n  小于 1為止。然后定義一個(gè)變量product；通過棧的length()的方法判斷是否大于0 且每次執(zhí)行 product* = s.pop();  pop()方法返回棧頂元素，且從棧中刪掉該元素。所以每次執(zhí)行一次，就刪掉一個(gè)元素，直到s.length() <= 0 為止。所以 product = 5*4*3*2*1 .等操作。

相關(guān)文章

最新評(píng)論