データ構造入門 — 配列・連結リスト・スタック・キュー
同じデータでも「置き方」を変えるだけで、ある操作は一瞬になり、別の操作は大仕事になる。データ構造とは、この置き方の設計のこと。4つの基本構造を動かして、トレードオフの感覚をつかみます。
1. 置き方が速さを決める — 配列 vs 連結リスト
配列は、データを連続した部屋に隙間なく並べる置き方。部屋の番地は計算で求まるので、「i番目を読む」のは何個あっても一発です。
連結リストは、データをバラバラの箱に入れ、「次はここ」というポインタ（鎖）でつなぐ置き方。i番目を読むには先頭から鎖を辿るしかありませんが、先頭に割り込むのは鎖を2本つなぎ替えるだけ。
下のデモで2つの操作を実行して、同じ操作のコストがどれだけ違うかを見比べてください。
配列 vs 連結リスト — 同じ操作、ちがうコスト
「i番目を読む」— 配列は番地計算で直行（1歩）、リストは先頭から1つずつ辿る（i+1歩）。「先頭に挿入」— 配列は全員を1つずつ右へずらす、リストは鎖のつなぎ替え2本だけ。操作すると下の表の該当行が光ります。
| 操作 | 配列 | 連結リスト |
|---|---|---|
| i番目を読む | O(1) — 番地計算で一発 | O(n) — 先頭から辿る |
| 先頭に挿入 | O(n) — 全部を1つずらす | O(1) — つなぎ替え2本 |
| 値を探す（未整列） | O(n) — 端から順に見る | O(n) — 端から順に見る |
配列の「一発読み」のからくりは、たった1行の番地計算です。
i 番目の番地 = 先頭の番地 + i × 1要素の大きさ
掛け算1回と足し算1回だけ — データが10個でも100万個でも手間は同じ（これが O(1) の正体）
POINT — 万能のデータ構造は存在しない
読むのが得意な配列は割り込みが苦手、割り込みが得意なリストは読むのが苦手。得意を伸ばせば、どこかに苦手ができる。だから「このプログラムで一番多い操作は何か？」を考えて置き方を選ぶ — これがデータ構造設計の基本姿勢。
2. 取り出す順番をデザインする — スタックとキュー
次は「置き方」に加えて「取り出す順番」にルールを付けた構造です。
- スタック（stack）：箱を上に積み、取るときも上から。あとに入れた物が先に出る = LIFO（Last-In, First-Out）。
- キュー（queue）：行列の最後尾に並び、先頭から出ていく。先に入れた物が先に出る = FIFO（First-In, First-Out）。
ボタンで箱を出し入れして、取り出した順（下のトレイ）が2つでどう違うかを確認しましょう。
スタックとキュー — 取り出す順番が違う2つの入れ物
箱には入れた順に番号（#1, #2, …）と色が付きます。#1〜#4 を入れてから全部取り出すと、スタックのトレイは #4 → #1（逆順）、キューのトレイは #1 → #4（入れた順） に並びます。ブラウザの「戻る」はスタック、印刷の待ち行列はキューそのものです。
注意 — O(1) が常に「実測で速い」とは限らない
連結リストの先頭挿入は理論上 O(1) だが、現代のCPUは連続したメモリ（＝配列）を読むのが桁違いに得意（キャッシュのしくみによる）。そのため実測では、O(n) のはずの配列がリストに勝つ場面も多い。O記法は「nが大きくなったときの伸び方」の物差しであって、ストップウォッチではない — 迷ったら測ろう。
3. どれを使う？ — 選び方クイズ
仕上げに、現実のシナリオで最適な構造を選んでみましょう。カギは「一番よく行う操作は何か」です。回答すると4構造のコスト比較が発表されます。
どれを使う? データ構造選びクイズ（全4問）
4問すべてに答えると正解数が発表されます。間違えても、なぜその構造では損なのかのコスト比較が表示されるので、そこが一番の学びどころです。
4. まとめ — 次章への地図
- データ構造 = データの置き方。置き方で各操作のコスト（O(1) か O(n) か）が決まる。
- 配列は読み出しO(1)・割り込みO(n)、連結リストはその逆。得意と苦手は表裏一体。
- スタック（LIFO）とキュー（FIFO）は「取り出す順番」をルール化した構造。undo・関数呼び出し・待ち行列など、順番が意味を持つ場面の定番。
- 選び方の質問はいつも同じ — 「このプログラムで一番多い操作は何？」
一歩先へ — 「探す」をもっと速く
今日の4構造はどれも「値を探す」のが O(n)。ここを突破するのが次章以降の主役 — 第6章のハッシュテーブルは番地を計算で当ててほぼ O(1) で探し、第7章の木構造は枝分かれで絞り込んで O(log n) を実現しつつ順序も保つ。データ構造の地図はここから一気に広がる。