DIV CSS 佈局教程網

 DIV+CSS佈局教程網 >> 網頁腳本 >> JavaScript入門知識 >> JavaScript綜合知識 >> JavaScript數據結構與算法之棧詳解
JavaScript數據結構與算法之棧詳解
編輯:JavaScript綜合知識     

 這篇文章主要介紹了JavaScript數據結構與算法之棧詳解,本文講解了對棧的操作、對棧的實現實例等內容,需要的朋友可以參考下

   

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

一:對棧的操作。

棧是一種特殊的列表,棧內的元素只能通過列表的一端訪問,這一端陳為棧頂。比如餐館裡面洗盤子,只能先洗最上面的盤子,盤子洗完後,也只能螺到這一摞盤子的最上面。棧被稱為 "後入先出"(LIFO)的數據結構。

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

入棧和出棧的實列圖如下:

JavaScript數據結構與算法之棧詳解

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() <= 0 為止。所以 product = 5*4*3*2*1 .等操作。

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