「スタックとキューって、何が違うの?」
「配列と連結リストは、どう使い分けるの?」
そんな疑問を抱える、基本情報技術者の科目B 対策を始めたあなたへ。
結論から言えば、
データ構造とは、データを効率よく扱うための「整理方法」のことです。配列・連結リスト・スタック・キュー・木構造・ハッシュテーブルの6つを押さえると、科目B の出題が読み取りやすくなります
と整理されるのが一般的です。
「データ構造」とは、同じデータでも整理方法を変えると扱いやすさが変わる仕組みを指す言葉とされています。
この記事では、配列・連結リスト・スタック(LIFO)・キュー(FIFO)・二分木・ハッシュテーブルの6つを、初心者のあなた向けにメタファーでやさしくまとめました。基本情報技術者の科目B 対策にも役立ちます。
1. 配列と連結リスト — 本棚と数珠つなぎのカード
あなたが「データ構造」という言葉に最初に出会うのは、配列と連結リストの対比という場面が一般的です。同じ「データを並べて持つ」目的でも、内側の仕組みが異なる構造として整理されることが多いと言われています。
配列は連続したメモリ領域に同じ型を並べる構造です。インデックスで一発参照できる一方、途中に差し込むと後ろをずらすコストが発生します。
連結リストは、各要素(ノード)が次への「ポインタ」を持って繋がる構造です。途中の挿入・削除はポインタを繋ぎ替えるだけで済みますが、N 番目を参照したい場合は先頭から順に辿ることになります。
2. スタック(LIFO)とキュー(FIFO)
あなたが次に押さえたいのが、スタックとキューです。どちらも配列や連結リストの上に作られる「出し入れの順番が決まった構造」と整理されることが多いと言われています。
スタックは、後から入れたデータを先に取り出す「LIFO(Last In, First Out)」の構造です。机に積み重ねた紙束をイメージすると近いとされています。一番上の紙を最初に取る動きが、スタックの「push」と「pop」に対応します。
一方のキューは、先に入れたデータから順に取り出す「FIFO(First In, First Out)」の構造です。皿洗いの待ちトレイが近いとされています。先に置いた皿から洗うのが、キューの「enqueue」と「dequeue」に対応します。
- スタックの典型用途: 関数呼び出し履歴(コールスタック)、ブラウザの「戻る」操作、式の評価
- キューの典型用途: 印刷ジョブの待ち行列、メッセージキュー、コンビニのレジ待ち
3. 木構造（二分木）とハッシュテーブル
あなたが配列・スタック・キューの先で出会うのが、木構造とハッシュテーブルです。どちらも「目的のデータを速く見つける」工夫が組み込まれた構造と言われています。
木構造は、データを親子関係で枝分かれさせて持つ構造です。代表が二分木で、各ノードが子を2つまで持つ形を指します。家系図のイメージが近いとされています。二分探索木の形にすると、探す値が左右どちらの枝にあるかを判断しながら、半分ずつ候補を絞れます。
ハッシュテーブルは、キーから値を直接引ける構造です。キーを「ハッシュ関数」に通してデータを置く位置(インデックス)を決める仕組みで、名簿の索引で「ア行は3ページ目」と分かっている感覚に近いとされています。
| 構造 | 平均参照速度 | イメージ |
|---|---|---|
| 二分木(平衡) | O(log n) | 家系図を枝で半分ずつ絞る |
| ハッシュテーブル | O(1) | 名簿の索引で一発引き |
4. 使い分けの考え方
あなたが構造を選ぶときの軸は、「何を速くしたいか」の一点に集約できると言われています。代表的な6構造を、用途別に整理すると次のようになります。
| 構造 | 得意 | 苦手 |
|---|---|---|
| 配列 | インデックス参照 | 途中の挿入・削除 |
| 連結リスト | 途中の挿入・削除 | N番目の参照 |
| スタック | 直近データの取り出し | 中間データの参照 |
| キュー | 到着順の処理 | 中間データの参照 |
| 二分木 | 順序を保った探索 | 偏ると速度低下 |
| ハッシュテーブル | キー指定の一発引き | 順序を持たない |
→ 各アルゴリズムの動きを押さえたい場合は、アルゴリズム基礎とは も合わせて読むと、構造とアルゴリズムの組み合わせが立体的に掴めます。
5. まとめ: 今日からできる、最初の一歩
ここまで読んだあなたは、データ構造の輪郭をしっかり押さえられたはずです。要点を3つに整理します。
- 配列(連続領域・参照が速い)と連結リスト(ポインタ連結・挿入が速い)は対の関係
- スタックは LIFO(後入れ先出し)、キューは FIFO(先入れ先出し)で出入り順を整える
- 二分木は順序を保った絞り込み、ハッシュテーブルはキー指定の一発引き
あなたが今日からできる、最初の一歩を3つ用意しました。
- 用語整理: 「配列・連結リスト・スタック・キュー・二分木・ハッシュ」をノートに1行ずつ書く(3分)
- 擬似言語: 擬似言語とは で読み方を押さえ、構造と操作のセットで理解する(7分)
- 問題演習: 科目B アルゴリズム問題集に進み、構造を読み取る感覚を試す(5分)
たった15分で、データ構造はあなたにとって扱える道具に変わります。完璧に覚えてから動くより、まず1問解いてみる。それが、いちばん速い学び方です。
次のステップ
- 擬似言語とは — 科目B 直結、構造と操作をセットで読み取る練習
- 2進数と論理回路とは — データ構造の中身を支える、2進数によるデータ表現
- 基本情報技術者 科目B アルゴリズム 問題集 — 紐付け T2、構造読み取りの実践
- 基本情報技術者 データ構造 問題集 — リスト・スタック・キューを中分類で演習し理解度を確認
- 基本情報技術者試験 全体概要 — 科目B での位置づけ
