JavaScriptはスタック構造Stockプロセスの詳細を実現する。
5102 ワード
JavaScriptはスタック構造(Stck)を実現する。
はじめに
1.1.
データ構造とは?
データ構造とは、コンピュータにデータを格納し、組織することです。
例えば、図書管理はどのようにすれば、本をたくさん置くことができますか?
主に二つの問題を考慮する必要があります。
操作一:新書はどうやって挿入しますか?操作二:どのように特定の本を見つけますか?
一般的なデータ構造:
配列スタック(Stock)チェーン図(Grash)列(Queue)ツリー(Tree)ヒープ(Heap)
注意:データ構造はアルゴリズムと言語に関係なく、一般的なプログラミング言語は、上述の一般的なデータ構造を直接または間接的に使用している。
1.2.アルゴリズムとは?
アルゴリズムの定義
有限命令セットで、各命令の説明は言語に依存しない。いくつかの入力を受信します。入力を生成する必ず限られたステップの後で終了します。
アルゴリズムは分かりやすい:問題を解決する方法/ステップロジック。データ構造の実現は,アルゴリズムから切り離せない。
二、スタック構造(Stck)
2.1.概要
配列は線形構造であり、配列の任意の位置に要素を挿入して削除することができます。スタックとキューは、比較的一般的に限定された線形構造である。下図のように:
スタックの特徴は先進的な後進先出(LIFO:last in first out)です。
プログラムのスタック構造:
関数コールスタック:A(B(C(D()))))):すなわちA関数でBを呼び出し、BはCを呼び出し、CはDを呼び出す。A実行中にAをスタックに押し込み、その後B実行時にBもスタックに押し込まれ、関数CとD実行時にスタックに押し込まれます。したがって、現在のスタックの順序は、A−B−C−D(スタックトップ)である。関数Dが実行された後、イジェクトスタックは解放され、イジェクトスタックの順序はD->C->B->Aである。
再帰:なぜ停止条件の再帰がないとスタックオーバーフローを引き起こすのですか?例えば関数Aは再帰関数として、絶えず自分を呼び出します。(関数はまだ実行されていないので、関数をスタックから飛び出さないです。)
3.練習:
タイトル:
6つの要素があります。6、5、4、3、2、1は順番にスタックに入ります。次のどれが合法的な出庫順ではないですか?
A:5 4 3 6 1 2(√)B:4 3 2 1 6(√)C:3 4 6 5 2 2 1(√)×)D:2 3 4 1 5(√)
タイトルの順にスタックに入るというのは一回に全部入るのではなくて、入る順が6->>5->4->3->2->1ということです。
解析: A答え:65進桟、5出桟、4進桟、3進桟、6出桟、21進桟、1出桟、2出桟(全体の入構順は654321に適合); B答え:654進スタック、4出スタック、5出スタック、3進スタック、2進スタック、1進スタック、6出スタック(全体の入スタック順序は654321に適合); C答え:6543はスタックに入って、3はスタックを出して、4はスタックを出して、その後は6ではなく5はスタックを出すべきで、だから誤り; D答え:65432はスタックに入り、2はスタックに出て、3はスタックを出して、4はスタックを出して、1はスタックを出して、5は倉庫を出して、6は倉庫を出します。受入順序に適合する。 スタックの一般的な操作: push(element):スタックの一番上の位置に新しい要素を追加します。 pop():スタックトップの要素を除去し、除去された要素を返します。 peek():スタックの一番上の要素を返して、スタックに対して何の変更もしない(この方法はスタックの一番上の要素を除去しないで、それだけを返す)。 isEmpty():もしスタックに何の要素もないなら、trueに戻ります。そうでなければfalseに戻ります。 size():スタック内の要素の個数を返します。この方法は配列のlength属性と類似している。 toString():スタック構造の内容を文字列で返す。 2.2.パッケージスタック類
コードの実装:
スタック構造の簡単な応用:
スタック構造の特性を利用して10進をカプセル化し、2進至の関数に変換する。
以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。
はじめに
1.1.
データ構造とは?
データ構造とは、コンピュータにデータを格納し、組織することです。
例えば、図書管理はどのようにすれば、本をたくさん置くことができますか?
主に二つの問題を考慮する必要があります。
操作一:新書はどうやって挿入しますか?操作二:どのように特定の本を見つけますか?
一般的なデータ構造:
配列スタック(Stock)チェーン図(Grash)列(Queue)ツリー(Tree)ヒープ(Heap)
注意:データ構造はアルゴリズムと言語に関係なく、一般的なプログラミング言語は、上述の一般的なデータ構造を直接または間接的に使用している。
1.2.アルゴリズムとは?
アルゴリズムの定義
有限命令セットで、各命令の説明は言語に依存しない。いくつかの入力を受信します。入力を生成する必ず限られたステップの後で終了します。
アルゴリズムは分かりやすい:問題を解決する方法/ステップロジック。データ構造の実現は,アルゴリズムから切り離せない。
二、スタック構造(Stck)
2.1.概要
配列は線形構造であり、配列の任意の位置に要素を挿入して削除することができます。スタックとキューは、比較的一般的に限定された線形構造である。下図のように:
スタックの特徴は先進的な後進先出(LIFO:last in first out)です。
プログラムのスタック構造:
関数コールスタック:A(B(C(D()))))):すなわちA関数でBを呼び出し、BはCを呼び出し、CはDを呼び出す。A実行中にAをスタックに押し込み、その後B実行時にBもスタックに押し込まれ、関数CとD実行時にスタックに押し込まれます。したがって、現在のスタックの順序は、A−B−C−D(スタックトップ)である。関数Dが実行された後、イジェクトスタックは解放され、イジェクトスタックの順序はD->C->B->Aである。
再帰:なぜ停止条件の再帰がないとスタックオーバーフローを引き起こすのですか?例えば関数Aは再帰関数として、絶えず自分を呼び出します。(関数はまだ実行されていないので、関数をスタックから飛び出さないです。)
3.練習:
タイトル:
6つの要素があります。6、5、4、3、2、1は順番にスタックに入ります。次のどれが合法的な出庫順ではないですか?
A:5 4 3 6 1 2(√)B:4 3 2 1 6(√)C:3 4 6 5 2 2 1(√)×)D:2 3 4 1 5(√)
タイトルの順にスタックに入るというのは一回に全部入るのではなくて、入る順が6->>5->4->3->2->1ということです。
解析:
コードの実装:
//
function Stack(){
//
this.items =[]
//
// 1.push():
// ( ): ,
// this.push = () => {
// }
// ( ): Stack ,
Stack.prototype.push = function(element) {
// item push Stack pop
this.items.push(element)
}
// 2.pop():
Stack.prototype.pop = () => {
// item pop Stack pop
return this.items.pop()
}
// 3.peek():
Stack.prototype.peek = () => {
return this.items[this.items.length - 1]
}
// 4.isEmpty():
Stack.prototype.isEmpty = () => {
// this.length( Stack length,Stack length ), Stack items length
return this.items.length == 0
}
// 5.size():
Stack.prototype.size = () => {
return this.items.length
}
// 6.toString():
Stack.prototype.toString = () => {
// :20 10 12 8 7
let resultString = ''
for (let i of this.items){
resultString += i + ' '
}
return resultString
}
}
テストコード:
//
let s = new Stack()
s.push(20)
s.push(10)
s.push(100)
s.push(77)
console.log(s) //65
console.log(s.pop()); //68
console.log(s.pop()); //69
console.log(s.peek()); //71
console.log(s.isEmpty()); //72
console.log(s.size()); //74
console.log(s.toString()); //75
テスト結果:スタック構造の簡単な応用:
スタック構造の特性を利用して10進をカプセル化し、2進至の関数に変換する。
// :
// : ( ' ')
let dec2bin = decNumber => {
//1. ,
var stack = new Stack()
// 2.
while(decNumber > 0){
// 2.1.
stack.push(decNumber % 2)
// 2.2. (floor: )
decNumber = Math.floor(decNumber / 2)
}
// 3. 0 1
let binaryString = '';
let a = stack.items.length
while(stack.items.length != 0){
binaryString += stack.pop();
}
return binaryString;
}
//
console.log(dec2bin(10)); //103
console.log(dec2bin(100)); //104
console.log(dec2bin(1000)); //105
テスト結果:以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。