js資料結構和演算法之棧和佇列詳解

1.定義

堆疊是重要的線性結構。堆疊（Stack）是一個後進先出（Last in first out,LIFO）的線性表，它要求只在表尾進行刪除和插入操作。對棧來說，這個表尾稱為棧的棧頂，對應的表頭稱為棧底。

堆疊的操作只能在這個線性表的表尾進行：
     堆疊的插入操作（Push），稱為進棧，也稱為壓棧，入棧。

     堆疊的刪除作業（Pop），叫做出堆疊，也稱為彈棧。

2.堆疊的順序儲存結構

因為堆疊的本質是線性表，線性表有兩種儲存形式，那麼堆疊也有分成堆疊的順序儲存結構和堆疊的鍊式儲存結構。

順序儲存結構：是把資料元素存放在位址連續的儲存單元裡，其資料間的邏輯關係和物理關係是一致的。

例如我們程式語言的陣列結構就是這樣滴。

鍊式儲存結構：是把資料元素存放在任意的儲存單元裡，這組儲存單元可以是連續的，也可以是不連續的。

很顯然，這樣說的話鍊式儲存結構的資料元素儲存關係並不能反映其邏輯關係，因此需要用一個指標存放資料元素的位址，這樣子透過位址就可以找到相關聯資料元素的位置。

最開始堆疊中不含有任何數據，叫做空棧，此時棧頂就是棧底。然後資料從棧頂進入，棧頂棧底分離，整個棧的目前容量變大。資料出棧時從棧頂彈出，棧頂下移，整個棧的目前容量變小。

3.堆疊操作

#（1）.基本操作

/** * 
 * 栈的构造函数 
 * */ 
function Stack() { 
 	// 用数组来模拟栈 
	this.dataStore = []; //底层数据结构是数组
	this.top = 0; //top应该是等于数组的length的
}
//栈需要有如下的方法
Stack.prototype = {
	/**
	 * 1. push()
	 * 向栈中压入一个新元素， 需要将其保存在数组中变量 top 所对
	 * 应的位置， 然后将 top 值加 1， 让top指向数组中下一个空位置
	 * 特别注意 ++ 操作符的位置， 它放在 this.top 的后面， 这样新入栈的元素就被放在
	 * top 的当前值对应的位置， 然后再将变量 top 的值加 1， 指向下一个位置
	 * */
	push:function(element){
		this.dataStore[this.top++] = element;
	},
	/**
	 * pop() 方法恰好与 push() 方法相反——它返回栈顶元素， 同时将变量 top 的值减 1
	 * 也可以改造一下,只--this.top,不返回栈顶元素
	 * */
	pop:function(){
		return this.dataStore[--this.top];
	},
	/**
	 * peek() 方法返回数组的第 top-1 个位置的元素， 即栈顶元素
	 * */
	peek:function(){
		return this.dataStore[this.top-1];
	},
	length:function(){
		return this.top;
	},
	clear:function(){
		 this.top = 0;
	}
};
//测试 Stack 类的实现
var s = new Stack();
s.push("David");
s.push("Raymond");
s.push("Bryan");
console.log("length: " + s.length());//length: 3
console.log(s.peek());//Bryan
var popped = s.pop();
console.log("The popped element is: " + popped);//The popped element is: Bryan
s.push("Cynthia");
s.clear();
console.log("length: " + s.length());//length: 0

相關推薦：

PHP基於陣列實作的堆疊和佇列功能實例分享

以上是js資料結構和演算法之棧和佇列詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！