jsのデータ構造とアルゴリズムのスタックとキューについて詳しく解説

1. 定義

スタックは重要な線形構造です。スタックは後入れ先出し (LIFO) 線形リストであり、テーブルの最後でのみ削除および挿入操作が必要です。スタックの場合、このテールはスタックの最上部と呼ばれ、対応するヘッダーはスタックの最下部と呼ばれます。

スタック操作は、この線形テーブルの最後でのみ実行できます:

スタックの挿入操作 (プッシュ) はプッシュと呼ばれ、プッシュまたはプッシュとも呼ばれます。

スタックの削除操作 (Pop) は、スタックのポップと呼ばれ、スタックのポップとも呼ばれます。

2. スタックの逐次記憶構造

スタックの本質は線形テーブルであり、線形テーブルには 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 中国語 Web サイトの他の関連記事を参照してください。