· theory · 8 min read
スタック・キュー・木とは？基本情報技術者試験のデータ構造を図解で攻略
スタック・キュー・連結リスト・二分木——基本情報技術者試験の科目A・Bに必ず出るデータ構造4種を、動作原理と試験での出題パターンごとに解説する。
プログラムは「データをどこに・どう並べるか」で処理速度が大きく変わる。 その「データの並べ方のルール」がデータ構造だ。
基本情報技術者試験では、データ構造は科目A（知識問題）と科目B（擬似言語問題）の両方に登場する頻出分野だ。仕組みを理解しないまま「用語だけ覚える」アプローチでは、科目Bのトレース問題で手が止まる。
この記事では試験に出る4つのデータ構造を、動作原理 → 実用例 → 試験での出題パターンの順で解説する。
スタック — 後から入れたものを先に取り出す
スタックの原則はLIFO（Last In, First Out：後入れ先出し）だ。 本を積み上げた山を想像すると分かりやすい。一番上（最後に置いた本）から取り出すしかない。
操作の名前
- プッシュ（push）：データを先頭に追加する
- ポップ（pop）：先頭からデータを取り出す
実際に使われている場面
- テキストエディタの「元に戻す（Ctrl+Z）」機能
- Webブラウザの「戻る」ボタン
- 関数の呼び出し履歴（コールスタック）
試験での出題パターン
科目Bでは「スタックへのプッシュ・ポップ操作をトレースして、最終的にスタックの先頭にある値を答えよ」という形式が多い。 途中でプッシュとポップが混在するため、手動で状態を書き出しながら追う練習が必要だ。
キュー — 最初に入れたものを先に取り出す
キューの原則はFIFO（First In, First Out：先入れ先出し）だ。 コンビニのレジ待ち行列がそのまま例として使える。最初に並んだ人が最初に処理される。
操作の名前
- エンキュー（enqueue）：データを末尾に追加する
- デキュー（dequeue）：先頭からデータを取り出す
実際に使われている場面
- 印刷ジョブの待ち行列
- ネットワークパケットの送信待ち
- OSのタスクスケジューリング
スタックとの違いを図で整理
スタック（LIFO）: 追加→[3][2][1] 取り出し順: 3→2→1
キュー（FIFO）: 追加→[1][2][3] 取り出し順: 1→2→3試験では「スタックとキューの動作の違いを答えよ」という選択問題も出る。 LIFO / FIFO のキーワードを確実に紐づけておくこと。
連結リスト — ポインタで繋がったデータの列
連結リストは、各データが「次のデータへのポインタ（アドレス）」を持つ構造だ。 配列と違い、メモリ上に連続して並んでいる必要がない。
特徴
| 操作 | 配列 | 連結リスト |
|---|---|---|
| 末尾への追加 | 遅い（全コピー） | 速い |
| 先頭への挿入 | 遅い（全シフト） | 速い |
| ランダムアクセス | 速い（添字で直アクセス） | 遅い（先頭から辿る） |
双方向リスト
前後両方向へのポインタを持つ形式。前のノードへも辿れるため柔軟性が高いが、メモリ使用量が増える。
試験では「挿入・削除時のポインタの付け替え手順」をトレースする問題が出やすい。 処理ミスなくポインタを繋ぎ変える手順を、紙に書いて練習しておくこと。
木（ツリー）構造 — 階層を持つデータ表現
木構造は、親ノードから子ノードへと枝分かれする階層型データ構造だ。 ファイルシステムのフォルダ階層や、組織図がイメージしやすい。
基本用語
- 根（ルートノード）：最上位のノード。親を持たない
- 葉（リーフノード）：子を持たない末端ノード
- 深さ（高さ）：根からの階層数
二分木と二分探索木
二分木は、各ノードの子が最大2つに限定された木だ。 二分探索木（BST）はさらに「左の子 < 親 < 右の子」という順序制約を加えた特殊な二分木で、データの検索が高速になる。
探索のロジック：
- 探したい値を根ノードの値と比較する
- 小さければ左の子へ、大きければ右の子へ移動する
- 一致するまで繰り返す
最悪でも木の深さ分の比較回数で探せるため、バランスの取れた二分探索木では O(log n) の計算量になる。
木の巡回（走査）
試験では「前順・中順・後順のいずれかで木を走査した結果を答えよ」という問題が頻出だ。
- 前順（前置記法）：自分 → 左の子 → 右の子
- 中順（中置記法）：左の子 → 自分 → 右の子
- 後順（後置記法）：左の子 → 右の子 → 自分
中順で走査すると二分探索木の要素が昇順に並ぶ。この性質は覚えておいて損はない。
AIで覚える実践テクニック
データ構造は「文字で読む」より「動作をトレースする」方が理解が速い。以下のプロンプトをChatGPTやGeminiに投げれば、動きを対話形式で確認できる。
スタックに [5, 3, 8, 1] の順でプッシュした後、
ポップを2回行った状態を教えてください。
さらに 9 をプッシュして、残っているデータを答えてください。以下の二分探索木に対して、前順・中順・後順で走査した結果をそれぞれ答えてください。
4
/ \
2 6
/ \ / \
1 3 5 7自分で問題を作ってAIに答えさせ、次に答えを隠して自分で解く——この往復が最も速い習得法だ。
まとめ
| データ構造 | 原則 | 代表的な用途 | 試験ポイント |
|---|---|---|---|
| スタック | LIFO | Undo機能 | プッシュ/ポップのトレース |
| キュー | FIFO | 印刷待ち行列 | エンキュー/デキューの順序 |
| 連結リスト | ポインタで連結 | 動的なデータ管理 | ポインタの付け替え手順 |
| 二分探索木 | 左 < 親 < 右 | 高速検索 | 前順/中順/後順の走査 |
4つのデータ構造はそれぞれ「いつ使うと速いか」で選ばれている。用語だけでなく動作原理を理解してしまえば、科目Bのトレース問題を解く際に迷わなくなる。
