前のブログでは、次のリストを紹介しました。リストは最も単純な構造ですが、より複雑な構造に対処したい場合、リストは単純すぎるため、リストと同様のデータ構造が必要ですが、より複雑なスタックが必要です。スタックは効率的なデータ構造です。これは、データをスタックの上部に追加または削除できるため、この操作は非常に高速で実装が簡単です。
1:スタックの操作。
スタックは特別なリストです。スタック内の要素は、リストの一方の端からのみアクセスでき、この端はスタックの上部です。たとえば、レストランで皿を洗うときは、最初にトッププレートを洗うことができます。皿を洗った後、皿の山の上部をカタツムリしかできません。スタックは、「後期後期」(LIFO)データ構造と呼ばれます。
スタックにはバックイン、ファーストアウトの特性があるため、スタックの上部にない要素はアクセスできません。低いスタックの要素を取得するには、上記の要素を最初に削除する必要があります。スタックでできる2つの主要な操作は、要素をスタックに押し込み、要素をスタックにポップすることです。スタックを入力するとき、メソッドプッシュ()メソッドを使用でき、それを装着すると、POP()メソッドを使用できます。 POP()メソッドはスタックの上部にある要素にアクセスできますが、メソッドを呼び出すと、スタックの上部にある要素はスタックから永続的に削除されます。使用するもう1つの方法はPeek()です。これは、削除せずにスタックの上部要素のみを返します。
スタックエントリとスタックの出口の実際の列図は次のとおりです。
push()、pop()、peek()は、スタックの3つの主要な方法ですが、スタックには他のメソッドとプロパティがあります。次のように:
Clear():スタック内のすべての要素をクリアします。
長さ():スタック内の要素の数を記録します。
2:スタックの実装は次のとおりです。
最初にStackクラスメソッドを実装することから始めることができます。次のように:
コードコピーは次のとおりです。
function stack(){
this.datastore = [];
this.top = 0;
}
上記のように:DataStoreはスタック内のすべての要素を保存します。変数トップは、スタックの上部に位置を記録し、0に初期化されます。これは、スタックの上部にある対応する配列の開始位置が0であることを意味します。この変数の値はそれに応じて変更されます。
また、次の方法があります:push()、pop()、peek()、clear()、length();
1。プッシュ()メソッド;新しい要素をスタックに押し込むときは、変数トップに対応する配列に保存する必要があり、その後、トップ値が1だけ増加して、配列の次の位置を指すようにします。次のコード:
コードコピーは次のとおりです。
関数プッシュ(要素){
this.datastore [this.top ++] = element;
}
2。POP()メソッドはPush()メソッドとは反対です - 上部要素を返し、次のコードを次のコードで控除します。
コードコピーは次のとおりです。
function pop(){
this.datastore [ - this.top];
}
3。PEEK()メソッドは、アレイの上位1位、つまりスタックの上位1位置に要素を返します。
コードコピーは次のとおりです。
function peek(){
this.datastore [this.top -1]を返します。
}
4。length()メソッドスタックにある要素がいくつあるかを知る必要がある場合があります。次のコードに示すように、変数最高値を返すことにより、スタック内の要素の数を返すことができます。
コードコピーは次のとおりです。
function length(){
this.topを返します。
}
5。clear();スタックをクリアしたい場合があり、変数の最上位を0に設定します。次のコード:
コードコピーは次のとおりです。
function clear(){
this.top = 0;
}
以下のすべてのコード:
コードコピーは次のとおりです。
function stack(){
this.datastore = [];
this.top = 0;
}
stack.prototype = {
//スタックに新しい要素を押します
プッシュ:function(element){
this.datastore [this.top ++] = element;
}、
//スタックの上部要素にアクセスすると、スタックの上部要素が永続的に削除されます
pop:function(){
this.datastore [ - this.top];
}、
//配列の上位1位で要素を返します。つまり、スタックの上部要素
ピーク:function(){
this.datastore [this.top -1]を返します。
}、
//スタックに保存されている要素の数
長さ:function(){
this.topを返します。
}、
//スタックをクリアします
clear: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;
次のコード:
コードコピーは次のとおりです。
function fact(n){
var s = new stack();
while(n> 1){
s.push(n-);
}
var product = 1;
while(s.length()> 0){
製品 *= s.pop();
}
返品製品。
}
console.log(fact(5));
上記のコードは、最初に数字を関数に渡し、whileループを使用し、毎回1を減らす前に、変数nが1未満になるまでスタックにプッシュ()を押します。次に可変製品を定義します。スタックの長さ()メソッドによって0を超えるかどうかを判断し、製品* = s.pop()メソッドが実行されるたびに、POP()メソッドはスタックの上部要素を返し、スタックから要素を削除します。したがって、実行するたびに、s.length()<= 0になるまで要素を削除します。したがって、製品= 5*4*3*2*1。等