「データ構造」って、データの形のことですか？
そう、データをどんな順番・どんなつながりでしまっておくかという「しまい方のルール」のことだよ。お皿の積み方とレジの並び方を思い浮かべると、いちばん大事なスタックとキューがすぐわかるよ。
データ構造は「しまい方のルール」
本棚に本を並べるとき、「番号順に並べる」「最近読んだものを手前に置く」など、しまい方によって 取り出しやすさ が変わります。プログラムでも同じで、目的に合ったしまい方を選ぶことで処理が速く、わかりやすくなります。この「しまい方」を データ構造 といいます。
配列：番号付きの箱が並んだもの
配列 は、同じ種類のデータを入れる箱を 一列に並べ、番号（要素番号、添字）を付けたもの です。ロッカーのように、番号を指定すれば どの箱にもすぐアクセスできる のが長所です。
一方、途中にデータを割り込ませると、後ろのデータを1つずつずらす必要があり、手間がかかります。
リスト：ポインタで数珠つなぎ
リスト（連結リスト） は、各データが 「次のデータの場所」を示す情報（ポインタ） を持ち、数珠つなぎになった構造です。宝探しの「次のヒントは○○にある」というメモをたどるイメージです。
途中に追加・削除するときは ポインタを付け替えるだけ で済み、データをずらす必要がありません。ただし、目的のデータにたどり着くには先頭から順にたどる必要があります。
スタック：後から入れたものが先に出る
スタック は、データを 上に積み重ね、上から取り出す 構造です。食器棚に積んだお皿を思い浮かべてください。最後に置いたお皿を最初に取りますよね。
- 入れる操作：プッシュ（push）
- 取り出す操作：ポップ（pop）
- 性質：後入れ先出し（LIFO：Last In First Out）
キュー：先に入れたものが先に出る
キュー は、データを 後ろに並ばせ、前から取り出す 構造です。レジの行列と同じで、先に並んだ人から会計します。
- 入れる操作：エンキュー（enqueue）
- 取り出す操作：デキュー（dequeue）
- 性質：先入れ先出し（FIFO：First In First Out）
- スタック＝お皿の山（stack は英語で「積み重ね」の意味）→ 最後に置いた皿から使う
- キュー＝行列（queue は英語で「行列に並ぶ」の意味）→ 先に並んだ人から
操作をたどってみよう
試験では、「この順に操作したら何が出てくるか」がよく問われます。中身を図に描きながら1手ずつ 進めるのが確実です。
木構造：枝分かれするつながり
木構造 は、1つのデータ（根）から枝分かれしてデータがつながる構造です。パソコンのフォルダ（フォルダの中にフォルダ）や会社の組織図が身近な例です。
特に、各データから出る枝が最大2本 のものを 2分木 といいます。「左の枝には小さい値、右の枝には大きい値」というルールで並べた2分木を 2分探索木 といい、探索を効率よく行えます。
データ構造の比較
| データ構造 | しまい方 | 得意なこと | 身近な例・使われ方 |
|---|---|---|---|
| 配列 | 番号付きの箱を一列に並べる | 番号を指定してすぐ読み書き | ロッカー、成績表 |
| リスト | ポインタで次をたどる | 途中への挿入・削除 | 宝探しのヒントのメモ |
| スタック | 上に積んで上から取る（LIFO） | 直前の状態に戻る | 「戻る」ボタン、元に戻す（Undo） |
| キュー | 後ろに並んで前から出る（FIFO） | 来た順に処理する | 印刷の順番待ち、レジの行列 |
| 木構造 | 根から枝分かれ | 階層の表現、効率的な探索 | フォルダ、組織図 |
スタックとキューの 取り出し口を逆に覚える ミスが多い。「スタック＝最後に入れたものが出る」「キュー＝最初に入れたものが出る」を、図を描いて確かめよう。
試験に出るポイント
- スタック：後入れ先出し（LIFO）。push で積み、pop で上から取り出す
- キュー：先入れ先出し（FIFO）。enqueue で後ろに並べ、dequeue で先頭から取り出す
- 操作の問題は、中身を図に描きながら1手ずつたどる
- 配列は番号で直接アクセスが得意、リストはポインタの付け替えで挿入・削除が得意
- 木構造は階層を表す。枝が最大2本のものが2分木