ガイドFE
スタック・キュー・木構造とアルゴリズム計算量完全攻略｜科目B必須データ構造徹底解説
公開: 2026-08-25更新: 2026-08-26
基本情報技術者試験（科目A・科目B）で最重要のスタック（LIFO）、キュー（FIFO）、二分探索木、ヒープ、整列アルゴリズムの計算量O(n log n)を徹底解説。
基本情報技術者試験の科目B（アルゴリズムと擬似言語）および科目Aで必須となる「データ構造（スタック・キュー・木構造）」と「計算量 」を整理します。
1. スタック（LIFO）vs キュー（FIFO）
データ構造 | 出し入れのルール | 主な操作 | 代表的な用途 |
|---|---|---|---|
スタック (Stack) | LIFO (Last In, First Out) 後入れ先出し | push (追加), pop (取出) | 関数呼び出しの戻り先管理、逆ポーランド記法、アンドゥ機能 |
キュー (Queue) | FIFO (First In, First Out) 先入れ先出し | enqueue (追加), dequeue (取出) | 印刷ジョブの待ち行列、メッセージキュー、イベント処理 |
2. 二分探索木（BST）と木の走査順序
各ノードにおいて「左の子 < 親ノード < 右の子」の大小関係が常に成り立つ木構造です。
- 先行順（Pre-order / 行きがけ順）: 親 → 左 → 右 の順で走査。
- 中間順（In-order / 通りがけ順）: 左 → 親 → 右 の順で走査。二分探索木を昇順で取得できる。
- 後続順（Post-order / 帰りがけ順）: 左 → 右 → 親 の順で走査。ノードの削除や構文木評価に適する。
3. 整列アルゴリズムと計算量比較
アルゴリズム | 平均計算量 | 最悪計算量 | 特徴 |
|---|---|---|---|
クイックソート | O(n log n) | O(n^2) | ピボットを基準に分割統治。平均的に最速。 |
マージソート | O(n log n) | O(n log n) | 分割して整列後に併合。安定ソートだが追加メモリが必要。 |
ヒープソート | O(n log n) | O(n log n) | ヒープ木を構築して最大値/最小値を順次取り出す。 |
バブルソート / 挿入ソート | O(n^2) | O(n^2) | 実装は単純だがデータ量が多いと低速。 |
この記事に関連する教科書用語
編集・検証について
編集・検証：IT資格ラボ編集部
IPAが公開する試験要綱・シラバス・過去問題と、各技術の公式資料を優先して内容を確認しています。制度変更や誤りを確認した場合は、記事を見直して更新します。
編集方針・情報源・訂正方針を見る