JavaScriptのデータ構造とアルゴリズムの詳しい説明 stack_javascriptスキル-jsチュートリアル-php.cn

JavaScriptのデータ構造とアルゴリズムの詳しい説明 stack_javascriptスキル

WBOY

リリース： 2016-05-16 16:10:14

オリジナル

1165 人が閲覧しました

前の記事では、次のリストを紹介しました。このリストは最も単純な構造ですが、より複雑な構造を扱いたい場合は、リストが単純すぎるため、何らかの種類のリストが必要です。 of と List はスタックに似ていますが、より複雑なデータ構造です。データはスタックの最上部でのみ追加または削除できるため、スタックは効率的なデータ構造であり、この操作は高速かつ簡単に実装できます。

1: スタック上の操作。

スタックは特殊な種類のリストです。スタック内の要素には、リストの一方の端 (スタックの最上部) からのみアクセスできます。例えば、飲食店で食器を洗うときは、まず天板を洗ってから、山盛りのお皿の上にネジを締めるだけです。スタックは、「後入れ先出し」(LIFO) と呼ばれるデータ構造です。

スタックは後入れ先出しの性質を持っているため、スタックの最上位にない要素にはアクセスできません。スタックの最下位の要素を取得するには、上の要素を取得する必要があります。最初に削除されました。スタック上で実行できる 2 つの主な操作は、要素をスタックにプッシュすることと、要素をスタックからポップすることです。 Push() メソッドを使用してスタックにプッシュし、pop() メソッドを使用してスタックからポップアウトできます。 Pop() メソッドはスタックの最上位の要素にアクセスできますが、このメソッドを呼び出した後、スタックの最上位の要素はスタックから完全に削除されます。よく使用されるもう 1 つのメソッドは、スタックの最上位要素のみを削除せずに返す Peak() です。

スタックへのプッシュとポップの実際の図は次のとおりです:

push()、pop()、peek() がスタックの 3 つの主要なメソッドですが、スタックには他のメソッドとプロパティもあります。以下のように:

clear(): スタック内のすべての要素をクリアします。

length(): スタック内の要素の数を記録します。

2: スタックの実装は次のとおりです:

次のようにスタッククラスのメソッドを実装することから始めます。

コードをコピーコードは次のとおりです:

関数 Stack() {

This.dataStore = [];

This.top = 0;

}

上記と同様: dataStore はすべての要素をスタックに保存します。変数 top はスタックの先頭の位置を記録し、0 に初期化されます。これは、要素がスタックにプッシュされた場合、スタックの先頭に対応する配列の開始位置が 0 であることを意味します。それに応じて変数の値も変化します。

次のメソッドもあります:push()、pop()、peek()、clear()、length();

1. Push() メソッド; 新しい要素をスタックにプッシュするときは、配列内の変数の先頭に対応する位置に保存する必要があり、その後、先頭の値が次の値を指すように 1 増加されます。配列内の位置。次のコード:

コードをコピーコードは次のとおりです:

関数プッシュ(要素) {

This.dataStore[this.top] = 要素;

}

2. Pop() メソッドは、push() メソッドの逆です。スタックの最上位の要素を返し、最上位の値を 1 ずつ減分します。次のコード:

コードをコピーコードは次のとおりです:

関数pop(){

return this.dataStore[--this.top];

}

3. Peak() メソッドは、配列の先頭から 1 番目の要素、つまりスタックの先頭の要素を返します。

コードをコピーコードは次のとおりです:

関数peek(){

return this.dataStore[this.top - 1];

}

4. length() メソッド 場合によっては、スタック内に要素がいくつあるかを知る必要があります。次のコードに示すように、変数 top の値を返すことでスタック内の要素の数を返すことができます。

コードをコピーコードは次のとおりです: 関数 length(){

return this.top;

}

5. clear(); 場合によっては、スタックをクリアしたい場合は、次のコードを使用して変数の先頭の値を 0 に設定します。

コードをコピー

コードは次のとおりです:

関数クリア() {

this.top = 0;

}

以下のすべてのコード:

コードをコピーコードは次のとおりです:

関数 Stack() {
This.dataStore = [];
This.top = 0;
}

Stack.prototype = {

//新しい要素をスタックにプッシュします
プッシュ: function(element) {
This.dataStore[this.top] = 要素;
}、
// スタックの最上位要素にアクセスすると、スタックの最上位要素は完全に削除されます
ポップ: function(){
return this.dataStore[--this.top];
}、
// 配列の先頭から 1 番目の要素、つまりスタックの先頭の要素を返します
ピーク: function(){
return this.dataStore[this.top - 1];
}、
//スタックに格納される要素の数
長さ: function(){
return this.top;
}、
//スタックをクリア
; クリア: function(){
This.top = 0;
}
};

デモの例は次のとおりです:

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(ポップ); // 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()) // 未定義

以下では、5! などの階乗関数の再帰定義を実装できます。 5の階乗です！ = 5 * 4 * 3 * 2 * 1;

次のコード:

コードをコピーコードは次のとおりです:

関数ファクト(n) {

var s = 新しいスタック();

; while(n > 1) {

s.push(n--);

}

var product = 1;

While(s.length() > 0) {

製品 *= s.pop();

}

製品を返品する;

}

console.log(fact(5));

上記のコードの意味は次のとおりです。まず数値 5 を関数に渡し、while ループを使用し、変数 n がゼロになるまで毎回 1 ずつデクリメントする前に、スタックを使用して関数 Push() をスタックにプッシュします。 1未満。次に、変数 product を定義します。スタックの length() メソッドを使用して、それが 0 より大きいかどうかを判断し、そのたびに product* = s.pop() を実行します。pop() メソッドはスタックの最上位要素を返し、削除します。スタックからの要素。したがって、実行されるたびに、s.length()