📅 公開日：2026年3月20日

【基本情報技術者試験】アルゴリズムとデータ構造入門｜スタック・キュー・ソートを完全解説

基本情報技術者試験において、アルゴリズムとデータ構造は科目Bの中心テーマです。スタック・キュー・連結リスト・ソートアルゴリズムの理解は合格への必須項目です。本記事では、試験頻出のデータ構造とアルゴリズムを具体的な例とともに解説します。

1. データ構造とは

データ構造とは、データをコンピュータ上で効率よく管理・操作するための「データの入れ物の形」のことです。

本棚の整理に例えると、「背の順に並べる（配列）」「読んだ本を積み重ねる（スタック）」「順番待ちの列（キュー）」のように、目的に応じて整理の方法が異なります。適切なデータ構造を選ぶことで、プログラムの効率が大きく変わります。

2. 配列（Array）

配列は最も基本的なデータ構造で、同じ型のデータを連続したメモリ領域に並べたものです。

特徴： - インデックス（番号）で任意の要素に O(1) でアクセス可能 - 要素の追加・削除には O(n) かかる（要素をずらす必要があるため） - サイズが固定（静的配列の場合）

3. スタック（Stack）

スタックは LIFO（Last In First Out：後入れ先出し） のデータ構造です。

食器の積み重ねをイメージしてください。一番最後に置いたお皿が、一番最初に取り出されます。追加操作を プッシュ（Push）、取り出し操作を ポップ（Pop） と呼びます。

用途： - 関数の呼び出し管理（コールスタック） - ブラウザの「戻る」機能 - 数式の評価

4. キュー（Queue）

キューは FIFO（First In First Out：先入れ先出し） のデータ構造です。

銀行の窓口の順番待ちをイメージしてください。最初に並んだ人が最初にサービスを受けます。追加操作を エンキュー（Enqueue）、取り出し操作を デキュー（Dequeue） と呼びます。

用途： - プリンタの印刷待ちキュー - タスクのスケジューリング - BFS（幅優先探索）

5. 連結リスト（Linked List）

連結リストは、各要素（ノード）がデータと次のノードへの ポインタ（アドレス） を持つデータ構造です。

配列との比較：

※対象ノードのポインタが分かっている場合

6. 主なソートアルゴリズム

バブルソート

隣接する要素を比較・交換する最もシンプルなソートです。大きな値が泡（バブル）のように端へ浮き上がっていくことからこの名前がついています。

• 計算量：O(n²)
• 特徴：実装が簡単だが大規模データには非効率

選択ソート

未整列部分から最小値を選んで先頭と交換する操作を繰り返します。

• 計算量：O(n²)

挿入ソート

整列済みの部分に新しい要素を適切な位置に挿入していく手法です。

• 計算量：平均 O(n²)、ほぼ整列済みなら O(n)

クイックソート

基準値（ピボット）を選び、小さいグループと大きいグループに分割する操作を再帰的に繰り返します。

• 計算量：平均 O(n log n)、最悪 O(n²)
• 特徴：実用的に最も高速なソートの一つ

マージソート

リストを半分に分割し、ソートしてからマージする分割統治法によるソートです。

• 計算量：常に O(n log n)
• 特徴：安定ソート、追加メモリが必要

7. 探索アルゴリズム

線形探索（リニアサーチ）

先頭から順番に全要素を比較する最もシンプルな探索法です。 - 計算量：O(n) - 整列不要で使える

二分探索（バイナリサーチ）

整列済みデータに対して中央値と比較しながら探索範囲を半分ずつ絞る手法です。 - 計算量：O(log n) - 整列されていることが前提条件

まとめ

試験では「スタックとキューの違い」「各ソートの計算量」が頻出です。LIFO／FIFO と O(n²)／O(n log n) の区別を確実に押さえましょう。