JavaScript のデータ構造とアルゴリズム (1): stack_javascript スキル

序文

データ構造とアルゴリズム JavaScript は、JavaScript 言語を使用して一般的に使用されるデータ構造を説明する本であり、一般的なインタビューの質問に基づいていると考えられます。時代の流れに合わせて、素人ながら録画してみました

git コードのダウンロード: https://github.com/JsAaron/data_structor.git

スタック構造

特別なリスト。スタック内の要素には、リストの一端、つまりスタックの最上位からのみアクセスできます

後入れ先出し (LIFO、後入れ先出し) データ構造

JavaScript はプッシュとポップという操作可能なメソッドを提供しますが、ポップはスタック内のデータを削除します

スタックを実装する実装クラス

基礎となるデータ構造は配列を使用します

pop はスタック内のデータを削除するため、検索メソッド Peak を実装する必要があります

明確なクリーニング方法を実装します

スタック長の要素の合計数を確認します

まだ空の要素があるかどうかを確認します

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

関数 Stack(){
This.dataStore = []
This.top = 0;
This.push = プッシュ
This.pop = ポップ
This.peek = 覗く
This.length = 長さ;
}

関数プッシュ(要素){
This.dataStore[this.top] = 要素;
}

関数ピーク(要素){
this.dataStore[this.top-1];
を返す }

関数 Pop(){
this.dataStore[--this.top];
を返します }

関数クリア(){
This.top = 0
}

関数 length(){
これを返します。トップ
}

回文

回文とは、前から後ろまで同じである単語、配列、または語句を指します 12321.abcba

回文の最も単純な考え方は、要素が反転されて元の要素と等しい場合、それは回文であることを意味するというものです

ここでの操作にはこのスタック クラスを使用できます

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

function isPalindrome(word) {
var s = 新しいスタック()
for (var i = 0; i s.push(word[i])
}
var rword = "";
while (s.length() > 0) {
rword = s.pop();
}
If (word == rword) {
true を返します;
} else {
return false;
}
}

isPalindrome("aarra") //false
isPalindrome("aaaa") //true

この isPalindrome 関数を見てください。この関数は実際に Stack クラスを呼び出し、スタックの原理 (後入れ先出し使用) に従って、分解された各ユニットに渡された単語要素をスタックにプッシュします。 Popメソッドでこの要素を分解し、最後に組み立て前と組み立て後を比較し、等しい場合は回文です

。

再帰

再帰を使用して階乗アルゴリズムを実装します

5 = 5 * 4 * 3 * 2 * 1 = 120

再帰を使用する

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

関数階乗(n) {
If (n === 0) {
1 を返します;
} else {
return n *階乗(n - 1);
}
}

スタック操作を使用する

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

関数ファクト(n) {
var s = 新しいスタック()
while (n > 1) {
//[5,4,3,2]
s.push(n--);
}
var product = 1;
while (s.length() > 0) {
製品 *= s.pop();
}
製品を返品する;
}

fact(5) //120

while を通じて n = 5 を段階的にスタックにプッシュし、次にループを通じて、またはスタックの後入れ先出しの原則に従って、一番前のものを取り出し、ポップ メソッドを通じて積とスタックします。