JavaScriptのデータ構造とアルゴリズムスタックとキュー

JavaScriptのデータ構造とアルゴリズムスタックとキュー_基礎知識

WBOY

リリース： 2016-05-16 15:16:57

オリジナル

1072 人が閲覧しました

学習の原因

V2EX を閲覧しているときに、このような投稿を見つけたことがあります。
数学は完全に先生に任せています。おそらく高校レベルの数学の基礎を学びたいのですが、どのような本をお勧めしますか?
投稿者は大学で高度な数学の授業を受けておらず、社会に出たときはフロントエンドの仕事に従事していた。数学の知識が足りないと感じているので、数学の知識を取り戻したいと思っています。
この投稿を読んで、私の専攻は高度な数学を必要とせず、フロントエンドも勉強していたので、非常に似ていると感じました。数学の知識がないことによる難しさも感じました。同時に、私は数学的思考があまり得意ではないので、基礎的な数学とコンピューターの知識を一生懸命学ぶことにしました。
当時、「フロントエンドにはどのようなデータ構造やアルゴリズムが必要なのか？」という意見もありましたが、これについては私なりの考えがあります。
フロントエンドにアルゴリズムなどの知識は必要ないとは思いませんが、フロントエンドにはしっかりしたコンピューター基盤があり、それが自身の開発に非常に有益であると考えています。プログラマーになりたいです。生涯ジュニアのフロントエンド兼コーダーになるのではなく。
それは自分自身への励ましとも言えます。結局のところ、基礎が上限を決定します。私はコンピューターに非常に興味があるので、学ぶのは面倒ですが、とても幸せでもあります。そこで私はインターネットで「JavaScript データ構造とアルゴリズムの学習」という本を購入し、図書館で借りた「Dahua データ構造」と合わせてデータ構造とアルゴリズムの予備学習を開始しました。

JavaScipt での配列操作

次のステップは、データ構造の最初の部分であるスタックです。
スタックは、後入れ先出しの原則 (LIFO、Last In First Out の略) に従って順序付けられたコレクションです。スタックの最上位は常に最新の要素です。
例: スタックとは、箱の中に置かれた本の山のようなものです。下の本を取りたい場合は、最初に上の本を取り除かなければなりません。 (もちろん、以下の本を先に手に取ってもダメです。)

JavaScipt でのスタックの実装
まず、コンストラクターを作成します。

/**
 * 栈的构造函数
 */
function Stack() {

 // 用数组来模拟栈
 var item = [];
}

ログイン後にコピー

スタックには次のメソッドが必要です:
Push(element(s)): 複数の要素をスタックの先頭に追加します
Pop(): スタックの最上位要素を削除して返します
Peak(): スタックの最上位要素を返します
isAmpty: スタックが空かどうかを確認し、空の場合は true を返します
クリア: スタックからすべての要素を削除します
size: スタック内の要素の数を返します。
print: スタックのすべての内容を文字列として表示します
プッシュメソッドの実装
説明: 新しい要素をスタックに追加する必要がありますが、要素の位置はキューの最後にあります。つまり、配列のプッシュメソッドを使用して実装をシミュレートできます。

実装:

/**
 * 将元素送入栈，放置于数组的最后一位
 * @param {Any} element 接受的元素，不限制类型
 */
this.push = function(element) {
 items.push(element);
};

ログイン後にコピー

pop メソッドの実装

説明: スタックの最上位要素をポップし、同時にポップされた値を返す必要があります。配列の Pop メソッドを使用して実装をシミュレートできます。
実装:

/**
 * 弹出栈顶元素
 * @return {Any} 返回被弹出的值
 */
this.pop = function() {
 return items.pop();
};

ログイン後にコピー

peek メソッドの実装
注: スタックの最上位要素を表示するには、配列の長さを使用します。
実装:

/**
 * 查看栈顶元素
 * @return {Any} 返回栈顶元素
 */
this.peek = function() {
 return items[items.length - 1];
}

ログイン後にコピー

その他のメソッドの実装
注: 最初の 3 つはスタックメソッドの中核であり、残りのメソッドはここに一度にリストされています。以下で説明するキューがこの部分と大きく重なるためです。
実装:

/**
 * 确定栈是否为空
 * @return {Boolean} 若栈为空则返回true,不为空则返回false
 */
this.isAmpty = function() {
 return items.length === 0
};

/**
 * 清空栈中所有内容
 */
this.clear = function() {
 items = [];
};

/**
 * 返回栈的长度
 * @return {Number} 栈的长度
 */
this.size = function() {
 return items.length;
};

/**
 * 以字符串显示栈中所有内容
 */
this.print = function() {
 console.log(items.toString());
};

ログイン後にコピー

実用化

スタックの実際的な応用例がたくさんあります。この本には 10 進数を 2 進数に変換する関数があります。 (バイナリの計算方法がわからない場合は、Baidu を使用できます。) 以下は関数のソースコードです。
原則は、変換する数値を入力し、連続的に 2 で割って四捨五入することです。最後に while ループを使用して、スタック内のすべての数値を出力用の文字列に連結します。

/**
 * 将10进制数字转为2进制数字
 * @param {Number} decNumber 要转换的10进制数字
 * @return {Number}      转换后的2进制数字
 */
function divideBy2(decNumber) {

 var remStack = new Stack(),
  rem,
  binaryString = '';

 while (decNumber > 0) {
  rem = Math.floor(decNumber % 2);
  remStack.push(rem);
  decNumber = Math.floor(decNumber / 2);
 }

 while (!remStack.isAmpty()) {
  binaryString += remStack.pop().toString();
 }

 return binaryString;
};

ログイン後にコピー

この時点で、スタックの学習は終了します。ソースコード内にはコメントが多数あるため、ソースコードの内容はここでは掲載しません。

キュー

キューとスタックは非常によく似たデータ構造です。違いは、キューが先入れ先出し (FIFO: First In First Out) であることです。
例: 駅で切符を買うために並ぶときは、最初が先です。（列に並んだ人はカウントされません）分かりやすいですね～
。

JavaScipt でのキューの実装

キューの実装はスタックと非常によく似ています。最初は依然としてコンストラクターです:

/**
 * 队列构造函数
 */
function Queue() {
 var items = [];
}

ログイン後にコピー

キューには次のメソッドが必要です:
enqueue(element(s)): キューの最後にいくつかのアイテムを追加します
dequeue(): キューの最初の項目 (つまり、一番上の項目) を削除します
Front(): キューの最初の要素 (最後に追加された
) を返します。残りのメソッドは queue
と同じです

エンキューメソッドの実装

説明: キューの最後にいくつかの項目を追加します。
実装:

/**
 * 将元素推入队列尾部
 * @param {Any} ele 要推入队列的元素
 */
this.enqueue = function(ele) {
 items.push(ele);
};

ログイン後にコピー

デキューメソッドの実装

説明: キューから最初の項目を削除します。
実装:

/**
 * 将队列中第一个元素弹出
 * @return {Any} 返回被弹出的元素
 */
this.dequeue = function() {
 return items.shift()
};

ログイン後にコピー

フロントメソッドの実装

説明: キューの最初の要素 (最後に追加された要素) を返します。
実装:

/**
 * 查看队列的第一个元素
 * @return {Any} 返回队列中第一个元素
 */
this.front = function() {
 return items[0];
};

ログイン後にコピー

以上的三个方法，就是队列这种数据结构的核心方法了。其实很好理解的。

实际应用
书上的是个击鼓传花的小游戏。原理就是循环到相应位置时，队列弹出那个元素。最后留下的就是赢家。
源代码如下:

/**
 * 击鼓传花的小游戏
 * @param {Array} nameList 参与人员列表
 * @param {Number} num   在循环中要被弹出的位置
 * @return {String}     返回赢家(也就是最后活下来的那个)
 */
function hotPotato(nameList, num) {
 var queue = new Queue();

 for (var i = 0; i < nameList.length; i++) {
  queue.enqueue(nameList[i]);
 }

 var eliminated = '';

 while (queue.size() > 1) {
  for (var i = 0; i < num; i++) {
   queue.enqueue(queue.dequeue());
  }

  eliminated = queue.dequeue();
  console.log(eliminated + " Get out!")
 }

 return queue.dequeue()
}

ログイン後にコピー

队列的学习到此就告一段落了。下一期将讲述另外一种数据结构: 链表。

感想

很多时候看书，直接看算法导论或者一些数据结构的书，都是很迷糊的。后来才发现，看书从自己能看懂的开始，由浅入深才是适合自己的学习方式。