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

前の記事 では、次のリストを紹介しました。このリストは最も単純な構造ですが、より複雑な構造を扱いたい場合は、リストが単純すぎるため、何らかの種類のリストが必要です。 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()