目的

スタックとキューを前提にデータを取り扱えるようになる。

結論

スタック、キューとは、データの取扱い処理方法のひとつである。
データの集合を系統立てて管理、検索するために前提となる考え方。

つまり、アプリケーションなどの処理順序、処理効率と、検索のアルゴリズムに利用

※調査時、C言語で説明するサイトがとても多かったのでC言語の本が出てきます。
でも、C、わかりません。世界にこんにちはしたこともないです。
コンピューターサイエンスの基礎の勉強として役に立つ感触があるので概念だけでもそのうちやろうと思います。

背景

クロージャーや再帰などの処理をするにあたって、
スタック、キューという言葉を比較的頻繁に見かけるので
そろそろ理解しておかねばいけないと感じた。

スタック、キューとは

端的で、とてもわかりやすい説明を見つけました。

スタックは、例えば超忙しいときに新しい課題がぶっこまれたときとかにとりあえずそれを先に片付けるような感じ
キューは、人気ラーメン屋に並ぶ人々の待ち行列のように先に並んだ人が先にお店に入る感じ

参考）https://qiita.com/drken/items/6a95b57d2e374a3d3292

上記のままでも十二分にわかりやすいが同世代的には
スタック = お菓子のペッツ
キュー＝ロケット鉛筆のイメージをもった。

実用例

世の中における様々な問題は、探索によって、考えられる場合を調べ尽くすことによって原理的には解決できるものが多いです。例えば、現在地から目的地まで最速でたどり着く方法を求める問題は、原理的には、現在地から目的地へ到達する経路をすべて列挙することで解決できます1。将棋やオセロの必勝法を求める問題は、原理的には、考えられる局面と局面遷移をすべて調べ上げることで求めることができます

参考）https://qiita.com/drken/items/4a7869c5e304883f539b

データ構造が違うことでどんなメリットが享受されるのか？
使い分け方は？どんな人に関係があるの？と思いましたw

そこで、スタック、キューがあることで何が実現できるか、調査しました。

スタックで実現できること
- さまざまなソフトウェアの[元に戻す]ボタンに使用される。変更がスタックにプッシュされる。ブラウザーの戻るボタンでは、最近アクセスしたすべてのWebページがスタックにプッシュされるスタックの助けを借りて機能する。
- 深さ検索:とにかく行けるとこまで行ってそれ以上進めなくなったら1歩戻ってまた探索する（親子検索）
キューで実現できること
- プリンターの印刷順
- 画像のアップロード順
- 幅検索:出発点に近い点から順に探索する（兄弟検索）

配列では理解がしやすいですが、
グラフなど多元的な構造をもつデータの場合理解に苦しみました。

そこで、本から問題を読んでみて理解することにしました。

練習問題

例題：スタックというデータ構造がある。スタックは配列のようにデータを蓄積するが、積み上げ（push）と、一番最後にpushされたデータの積み下ろし（pop）の2種類しか操作が存在しない。Stackクラスを実装せよ。また、Stackクラスを実際に使用してみよ。

回答

class Stack {
  constructor() {
    this._data = [];
  }

  push(data) {
    this._data.push(data);
  }

  pop() {
    return this._data.pop();
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);

console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());

例題：ソート済みの配列があるとする。このとき、配列の中からある値を探しだす方法として、二分探索（バイナリサーチ）という手法が使える。

1 : 配列の真ん中の値を見て、同じならtrueを返し終了する。真ん中より小さければ左半分を二分探索し、真ん中より大きければ右半分を二分探索する。
2 : 最後まで見つからなければfalseを返すこれを実装し、動作を確かめよ。

回答

function binarySearch(array, target, start, end) {
  // startとendが逆転したら終わる
  if(start > end) {
    return false;
  }

  // 真ん中のインデックスを計算する
  const center = Math.floor((start + end) / 2);

  // 半分ずつ探す
  if(array[center] > target) {
    return binarySearch(array, target, start, center - 1);
  } else if(array[center] < target) {
    return binarySearch(array, target, center + 1, end);
  } else {
    return true;
  }
}

const sortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const arrayIncludes2 = binarySearch(sortedArray, 2, 0, sortedArray.length - 1);
console.log(arrayIncludes2);

その他参考資料(special Thanks!)

https://ja.wikipedia.org/wiki/深さ優先探索
 https://www.iwass.co.jp/column/column-01.html

遅延評価学習　候補

グラフ理論
ソート関係（バブルソートはOK)

遅延評価学習について

本の最初のページから読み始めることは、ひとつのよい勉強法だ。
ただ、そのような先行評価的な勉強は、初学者か、感情的な不安解消のためのものだ。
何かあったときの先行投資、だというが、何かあったときはまずその学習だけじゃ足りないこと。
そして本を最初からよんで網羅的に学んでも忘れている。

それよりは、緊急度や知識欲が高い問題から本気で解く中で、周辺知識としてつけた方が、結果的に良い気がする。
まずは極め横展開する。深さ優先検索的学習法

初心者なりにスタックとキューの実用例、検索アルゴリズム （深さ検索優先アルゴリズム 、幅検索優先アルゴリズム）についてまとめてみた

目的

結論

背景