データ構造 (スタック・キュー・木)

いい勘ね。
スタック?
は、机に本を積み上げていくイメージよ。
新しい本は一番上に置くし、取るときも一番上から。
だから後から入れたものが先に出る、LIFO?
(後入れ先出し)になるの。

あるわよ。
それがキュー?
。
スーパーのレジに並ぶ行列を思い浮かべて。
先に並んだ人から順に会計するでしょう?
だから先入れ先出し、FIFO?
よ。

スタックは『元に戻す(Undo)』や、関数を呼び出して元の場所へ戻る処理に使われるわ。
直前の状態に戻りたいときは、後入れ先出しが便利なのよ。
一方キューは、印刷の順番待ちや受け付けた順に処理する仕事に向いているの。

ふふ、うまい例えね。
さて次は枝分かれする構造、木構造?
(ツリー)よ。
一番上の起点をルート?
(根)、枝分かれの先で子を持たない末端を葉?
(リーフ)と呼ぶの。

木の中でも試験で頻出なのが、各ノードの子が最大2つの二分木?
。
さらに『左の子<自分<右の子』という大小ルールで並べたものが二分探索木?
(BST)よ。

もっと速いのもあるのよ。
ハッシュ表?
は、ハッシュ関数?
で鍵を保管場所の番号に直接変換するの。
だから探す手間がほとんどなく、平均O(1)?
で取り出せるわ。

関係を押さえておくと混乱しないわ。
じつは木はグラフの特別な形で、ぐるっと一周する経路、つまり閉路を持たないものなの。
グラフはもっと自由で、閉路があったり、矢印のような向きを持つこともあるのよ。

そのとおり。
最後に整理するわね。
出し入れの順番ならスタック(後入れ先出し)とキュー(先入れ先出し)、一列に並べるならリスト、階層なら木、速さ重視ならBSTやハッシュ表、つながり全体を見るならグラフ。
用途と速さをセットで覚えれば、もう迷わないわ。