「スタックとキューって、何が違うの?」
「配列と連結リストの違いは?」
データは、しまい方で扱いやすさが変わります。入れ物になぜ種類があるのか、それを解くのがデータ構造です。
データ構造とは、データをどう並べてしまうかの決まりで、処理のしやすさを左右するものです。同じ中身でも、並べ方を変えると「速く取れる/遅くなる」が入れ替わります。だから目的に合った入れ物を選ぶ力が問われます。
この記事では、スタックとキューの出し入れを図で追いながら、配列・連結リスト・木構造・ハッシュ表までの特徴を対応表で押さえます。最後に、目的から入れ物を選ぶ考え方と、次に学ぶ順を示します。基本情報技術者の科目B（アルゴリズムとプログラミング）対策に効きます。
1. データの「しまい方」で処理のしやすさが変わる
あなたが最初に押さえたいのは、データ構造が扱うのは「中身」ではなく「並べ方」だという点です。同じ数字の集まりでも、一列にきっちり並べるのか、順につないでいくのか、枝分かれさせるのかで、後の処理の速さが変わります。データ構造とは、その並べ方のルールのことです。
だから、データ構造に「万能の一番」はありません。あなたが選ぶべきは、やりたい処理をいちばん速くしてくれる入れ物です。以降で代表的な形を、出し入れの動きから見ていきます。
2. 積み重ねるスタック、並んで待つキュー
まず対にして覚えたいのが、スタックとキューです。どちらも「出し入れの順番が決まった入れ物」で、その順番がちょうど逆になります。動きを図で追いましょう。
スタックは、後から入れたものを先に取り出すLIFO（Last In, First Out）の入れ物です。上に積んでいく操作がpush、上から取り出す操作がpop。机に積んだ紙束を上から取る動きが、そのままスタックです。一方のキューは、先に入れたものから取り出すFIFO（First In, First Out）。後ろから入れるenqueue、前から取り出すdequeueで、レジ待ちの列と同じ順番です。あなたが「戻る」操作を思い浮かべればスタック、「届いた順の処理」を思い浮かべればキュー、と結びつけられます。
3. 一列に並ぶ配列と連結リストの違い
次に押さえたいのが、データを一列に持つ配列と連結リストの違いです。どちらも「並べて持つ」点は同じですが、内側の仕組みが分かれます。
配列は、連続した場所に同じ型を並べる入れ物です。何番目かを指定すれば一発で取り出せるのが強みですが、途中に差し込むと後ろをずらす手間がかかります。連結リストは、各要素が「次はどこか」の道しるべ（ポインタ）を持って数珠つなぎになる形です。途中の挿入・削除は道しるべをつなぎ替えるだけで軽い一方、N番目を取り出すには先頭からたどる必要があります。あなたが「よく参照するか、よく差し替えるか」で選び分けると、迷いが減ります。
4. 探しやすさを生む木構造とハッシュ表
スタック・キュー・配列の先で出会うのが、木構造とハッシュ表です。どちらも「目的のデータを速く見つける」工夫を持ちます。ここまでの5つを対応表にまとめました。
| データ構造 | アクセスの速さ | 挿入・削除 | 代表用途 |
|---|---|---|---|
| 配列 | 速い（番号指定） | 途中は遅い | 一覧・表の保持 |
| 連結リスト | 遅い（先頭からたどる） | 速い | 頻繁な差し替え |
| スタック | 先頭のみ | 先頭で出し入れ | 戻る操作・履歴 |
| キュー | 先頭のみ | 前後で出し入れ | 順番待ち処理 |
| 木構造・ハッシュ表 | とても速い | 構造しだい | 探索・キー引き |
木構造は、データを親子関係で枝分かれさせる形です。代表の二分木は、探す値が左右どちらの枝にあるかを判断しながら、候補を半分ずつ絞れます。ハッシュ表は、キーを計算式（ハッシュ関数）に通して置き場所を決め、キーから値をほぼ一発で引ける入れ物です。名簿の索引で「ア行は3ページ目」と分かっている感覚が近い例です。あなたが「順序を保って絞りたいか、順序を捨てて一発で引きたいか」で、この二つを選び分けられます。
5. 目的から入れ物を選ぶ考え方
ここまで来たあなたが持ち帰る軸は、一つです。「何の操作を、いちばん速くしたいか」から逆算して入れ物を選ぶ。「一つ前に戻す」ならスタック、「届いた順に処理する」ならキュー、「IDから社員情報を引く」ならハッシュ表、という具合です。当社のSE歴15年以上のエンジニアも、コードを書くときは速くしたい操作から構造を決めます。構造は、その後の処理速度をそのまま左右するからです。
試験では、データ構造は科目Bのトレース問題として頻出です。擬似言語で書かれた処理を一手ずつ追い、「今どの構造に、何が入っているか」を紙の上でたどる。だからこそ、push/popやenqueue/dequeueの動きを、図のように頭の中で再生できるかが得点を分けます。実務でも、どの構造を選ぶかは計算量（処理にかかる手間の増え方）で判断します。データが増えたときに手間が急に膨らむ選び方を避ける——この感覚は、試験の先の現場でも生きます。
次に学ぶ順としては、構造とセットで動くアルゴリズムへ進むのが自然です。入れ物（データ構造）と手順（アルゴリズム）は一組で効くので、アルゴリズム基礎とは で手順側を押さえると、両輪がそろいます。擬似言語そのものの読み方に不安があれば、擬似コードの基礎とは を先に通しておくと、トレース問題がぐっと読みやすくなります。
次のステップ
データ構造が試験のどこで問われるかを知りたいときは、基本情報技術者試験の試験範囲と勉強法ガイド で出題範囲を先に把握しておくと、学ぶ順番の見当がつきます。
読み解く感覚は問題で身につきます。基本情報 アルゴリズムの問題集 で、構造をたどる設問を実際に手で追ってみましょう。