データ構造

ねらい

データの並べ方の型を学びます。このレッスンを終えると、代表的なデータ構造を取り出す順序と得意な操作で見分けられるようになります。

並べ方を選ぶと、できることが変わります

同じデータでも、どう並べて持つかで、速くできる操作が変わります。用途に合った並べ方を選ぶことが、データ構造を学ぶ目的です。

配列とリスト

• 配列… 同じ種類のデータを順番に並べて置き、番号（添字）で場所を指します。何番目かを指定すれば、一発で取り出せます。その代わり、途中に割り込ませるのは大変です。後ろを全部ずらす必要があるためです。
• リスト… 各データが次のデータの場所を指し示す形で並びます。途中への追加や削除は、指し示す先を付け替えるだけで済みます。その代わり、5番目を取り出すには先頭から順にたどる必要があります。

配列は「探すのが速く、入れるのが遅い」、リストは「入れるのが速く、探すのが遅い」という関係です。どちらが優れているのではなく、どちらの操作が多いかで選びます。

スタックとキュー — 取り出す順序が違います

• スタック… 最後に入れたものを、最初に取り出します（後入れ先出し・LIFO）。机に積んだ書類と同じで、上から取ります。
• キュー… 最初に入れたものを、最初に取り出します（先入れ先出し・FIFO）。レジの行列と同じで、並んだ順です。

入れる操作と取り出す操作の呼び名も決まっています。スタックでは、入れる操作をプッシュ、取り出す操作をポップといいます。

動かして確かめる

「追加」は同じ1つの操作です。取り出す端だけがスタックとキューで違うことを、実際に操作して確かめてみましょう。

木構造

木構造は、1つの節から枝分かれして下へ広がる形です。会社の組織図やファイルのフォルダ構造がこの形です。

• 最上位を根、枝分かれの各点を節（ノード）、末端を葉といいます。
• 各節が最大2つに分かれるものを2分木といいます。

探すときに、たどる範囲を半分ずつ絞り込める性質があるため、大量のデータから目的のものを探す用途で使われます。

探す方法

データの中から目的のものを見つける方法にも型があります。

• 線形探索… 先頭から順に照合します。並んでいなくても使えますが、件数が多いと時間がかかります。
• 2分探索… あらかじめ順に並んでいるデータに対し、真ん中と比べて探す範囲を半分に絞ることを繰り返します。非常に速い代わりに、並んでいることが前提です。

2分探索は、1回の比較で候補が半分になります。1000件なら10回程度の比較で見つかります。ただし、そのために並べ替えておく手間がかかることは覚えておきます。

まとめ

データ構造は、どの操作を速くしたいかで選びます。配列は取り出しが速く挿入が遅い、リストはその逆です。スタックは後入れ先出し、キューは先入れ先出しで、順序が意味を持つ場面で使い分けます。探索では、線形探索は並んでいなくても使え、2分探索は並んでいれば非常に速くなります。

理解の確認

印刷の指示を受け付けて、順番に印刷していくしくみを作ります。スタックとキューのどちらを使うべきでしょうか。理由も述べてください。

答え: キューです。キューは最初に入れたものを最初に取り出す（先入れ先出し）ため、印刷を指示した順に処理されます。これは利用者の期待と一致します。仮にスタックを使うと最後に指示した人の印刷が先に出る（後入れ先出し）ことになり、先に指示した人がいつまでも印刷されないという事態が起こり得ます。順序に公平さが求められる待ち行列にはキューを使い、直前の操作を取り消す「元に戻す」のように新しいものから扱いたい場面ではスタックを使います。