ポチップ
🎯 この記事を読み終わるころには、この問題が解けるようになります！
【例題】キューのデータ操作
空の待ち行列（キュー）に対し、ENQ 1、ENQ 2、ENQ 3、DEQ、ENQ 4、ENQ 5、DEQ、ENQ 6、DEQ、DEQの操作を行った。次にDEQ操作を行ったとき、取り出されるデータはどれか。
ア. 1 イ. 2 ウ. 5 エ. 6
※今は解けなくて大丈夫！この記事を最後まで読んでから、もう一度チャレンジしてみてください 💪
前回は論理演算を学びました。今回は「コンピュータがどうデータを処理するか」＝アルゴリズムとデータ構造を解説します。スタック・キュー・木構造・整列・探索・再帰など、試験最頻出テーマが満載！一緒に攻略しましょう！
目次
- データ構造とは？｜コンピュータのデータの並べ方
- スタック（LIFO）｜積み上げた本のイメージ
- キュー（FIFO）｜レジ待ちの列のイメージ
- 配列と連結リスト｜直接アクセス vs ポインタ
- 木構造と2分探索木
- アルゴリズムの表現方法｜流れ図（フローチャート）
- 整列アルゴリズム｜クイックソートが最重要！
- 探索アルゴリズム｜2分探索法・ハッシュ法
- 再帰的アルゴリズム｜自分自身を呼び出す処理
- 過去問チャレンジ！
- この章のまとめ
1. データ構造とは？｜コンピュータのデータの並べ方
コンピュータ内の「主記憶装置」にデータを保存する際、データの並べ方によって処理効率が大きく変わります。このデータの並べ方をデータ構造と呼びます。
データ構造には主に5種類（スタック、キュー、配列、連結リスト、木構造）があります。
▲ 5つのデータ構造の概観。それぞれの特徴を押さえましょう
2. スタック（LIFO）｜積み上げた本のイメージ
データを1列に並べ、「最後に格納したデータを最初に取り出す」データ構造です。
- イメージ：積み上げられた本（上から取る）
- LIFO (Last In First Out)：後入れ先出し
- 操作：
pushでデータを格納、popでデータを取り出す
例えば「push C」でスタックにCを格納し、「pop」で最上部のデータを取り出します。コンピュータが「処理の戻り先」を記憶するのに使われます（童話ヘンゼルとグレーテルのパンくずの比喩と同じです）。
📝 ポイント
スタックは「後入れ先出し（LIFO）」。push / pop を覚えよう！
3. キュー（FIFO）｜レジ待ちの列のイメージ
データを1列に並べ、「最初に格納したデータを最初に取り出す」データ構造です。「待ち行列」とも呼ばれます。
- イメージ：レジ待ちの列
- FIFO (First In First Out)：先入れ先出し
- 操作：
enqueueで格納、dequeueで取り出す
📝 ポイント
キューは「先入れ先出し（FIFO）」。enqueue / dequeue を覚えよう！
| スタック | キュー | |
|---|---|---|
| 取り出し順 | 後入れ先出し（LIFO） | 先入れ先出し（FIFO） |
| 格納操作 | push | enqueue |
| 取り出し操作 | pop | dequeue |
| イメージ | 本の山 | レジの列 |
4. 配列と連結リスト｜直接アクセス vs ポインタ
配列は、データを表の形に並べる構造です。
- 要素番号で直接アクセス可能。参照・更新が速いのが特徴です。
-
1次元配列（1列）と、2次元配列（行と列）があります。例えば
A[3]で3番目、A[2,4]で2行4列目を表します。
連結リストは、データを数珠つなぎにした構造です。
- 各要素に「ポインタ（次の要素のアドレス）」が付きます。
- ポインタを書き換えるだけで済むため、挿入・削除が速いのが特徴です。
| 特徴 | 配列 | 連結リスト |
|---|---|---|
| アクセス | 要素番号で直接 | 先頭からたどる |
| 参照・更新 | 速い ⭕ | 遅い |
| 挿入・削除 | 遅い（要素をずらす） | 速い ⭕（ポインタ変更のみ） |
📌 重要：試験頻出！
「配列は参照・更新が速い。連結リストは挿入・削除が速い」という対比を必ず覚えておきましょう。
5. 木構造と2分探索木
木構造は、階層構造を持つデータ構造で、植物の木を逆さにしたような形をしています。各部の名称として、根（ルート）、節（ノード）、葉（リーフ）、親・子などがあります。
各節が最大2つの子を持つ木構造を「2分木」と呼び、その中でも特定のルールを満たすものを2分探索木と呼びます。
▲ 2分探索木の例。すべての節で「左の子孫＜親＜右の子孫」が成り立っています
📝 ポイント
2分探索木の条件は「左の子孫 ＜ 親 ＜ 右の子孫」。試験ではこれだけ覚えればOKです！
6. アルゴリズムの表現方法｜流れ図（フローチャート）
アルゴリズム（問題を解決するための手順）の表現方法には、文章、流れ図（フローチャート）、数式、プログラム言語の4つがあります。試験で最も出題されるのは流れ図です。
▲ 流れ図（フローチャート）で使う記号一覧。形と役割を覚えましょう
| 記号名 | 形 | 役割 |
|---|---|---|
| 端子 | 楕円 | 開始・終了 |
| 処理 | 長方形 | 計算・代入 |
| 判断 | ひし形 | 条件分岐（Yes/No） |
| ループ端 | 六角形 | 繰り返し処理の開始・終了 |
| データ | 平行四辺形 | データの入出力 |
📝 ポイント：トレース表の活用
試験での流れ図問題は「トレース表」を活用しましょう！変数の値を1つずつ表に書き出して追っていくことで、確実に解くことができます。
プログラム言語での表現が出た場合は、「if（もし）/then（ならば）/else（それ以外）/return（返す）」の4語の意味を押さえるだけで読めるようになります。
7. 整列アルゴリズム｜クイックソートが最重要！
データを特定の順番（昇順や降順）に並べ替えるアルゴリズムを整列（ソート）アルゴリズムと呼びます。
▲ 4種類の整列アルゴリズムの違い。試験ではクイックソートが最頻出です
| アルゴリズム | 特徴 | 試験頻度 |
|---|---|---|
| バブルソート | 隣り合う要素を比較・交換を繰り返す | △ |
| 選択ソート | 最小値を選んで先頭と交換を繰り返す | △ |
| 挿入ソート | 整列済み部分の適切な位置に挿入する | △ |
| クイックソート | 基準値で「小グループ」「大グループ」に分割を繰り返す | ◎ 最重要 |
クイックソートの手順：
①基準値（ピボット）を決める → ②小さいグループ・大きいグループに分割 →
③各グループでも同じ操作を繰り返す
📌 重要：試験頻出！
クイックソートは「最も高速な整列アルゴリズム」として試験に頻出します！基準値で2グループに分けることを繰り返すイメージを持っておきましょう。
8. 探索アルゴリズム｜2分探索法・ハッシュ法
目的のデータを見つけ出すアルゴリズムです。主に3種類があります。
▲ 線形探索・2分探索・ハッシュ法の3種類を押さえよう
| アルゴリズム | 特徴 | 事前準備 |
|---|---|---|
| 線形探索法 | 先頭から1つずつ順番に照合 | 不要 |
| 2分探索法 | 範囲を半分に絞りながら探索 | ソート済みが必要 |
| ハッシュ法 | ハッシュ関数でアドレスを計算して一発アクセス | ハッシュ表の作成が必要 |
2分探索法は「①データをあらかじめ整列させておく必要あり」「②データを2つに分けながら探索」という特徴があります。
ハッシュ法は、mod（余り）などの計算（ハッシュ関数）でハッシュ値を求め、ハッシュ表で格納場所を直接特定します。一発でアクセスできるため非常に高速です。
📝 ポイント
ハッシュ法には、異なる値から同じハッシュ値が計算されてしまう「衝突（シノニム）が起こる可能性がある」というデメリットがあります。これが試験でよく問われます！
9. 再帰的アルゴリズム｜自分自身を呼び出す処理
再帰的アルゴリズムとは、処理の途中で「自分自身を呼び出す」アルゴリズムのことです（再帰呼び出し・再帰関数）。
主に「総和」「剰余（mod）」「階乗」の計算で使われます。
- 階乗の例： 3! = 3 × 2 × 1 = 6
- 剰余（mod）： 7 mod 3 = 1（7÷3の余りは1）
プログラム例：f(x): if x < 0 then return -x else return x
📝 ポイント
modは「わり算の余り」を意味します。f(775, 527)
のような再帰関数が出題されたら、慌てずに数値を1つずつ代入して処理を追っていきましょう。
10. 過去問チャレンジ！
🎯 記事冒頭の例題に、もう一度チャレンジ！
【例題・再掲】キューのデータ操作
空の待ち行列（キュー）に対し、ENQ 1、ENQ 2、ENQ 3、DEQ、ENQ 4、ENQ 5、DEQ、ENQ 6、DEQ、DEQの操作を行った。次にDEQ操作を行ったとき、取り出されるデータはどれか。
ア. 1 イ. 2 ウ. 5 エ. 6
※記事を読んだ今なら解けるはず！👇
✅ 解答・完全解説
正解：ウ（5）
解説：
キューは「先入れ先出し（FIFO）」です。
ENQ(1,2,3) → [1,2,3]
DEQ → 1を取り出す。残り[2,3]
ENQ(4,5) → [2,3,4,5]
DEQ → 2を取り出す。残り[3,4,5]
ENQ(6) → [3,4,5,6]
DEQ, DEQ → 3, 4を取り出す。残り[5,6]
次のDEQで取り出されるのは先頭にある「5」です。よって正解はウです。
【過去問 その2】スタックのデータ操作
A、B、C、Dの順に到着するデータに対して、一つのスタックだけを用いて出力可能なデータ列はどれか。
ア. A, D, B, C
イ. B, D, A, C
ウ. C, B, D, A
エ. D, C, A, B
💡 解答・解説
正解：ウ
実際に操作を試してみます。ウの出力結果を得るためには以下のように操作します：
① push A, push B, push C（スタック内：下からA, B, C）
② pop（Cが出力される）
③ pop（Bが出力される）
④ push D（スタック内：下からA, D）
⑤ pop（Dが出力される）
⑥ pop（Aが出力される）
結果として「C, B, D, A」の順に出力できるため、ウが正解です。
11. この章のまとめ
📌 アルゴリズムとプログラミングのまとめ
- スタック ＝ 後入れ先出し（LIFO）、push/pop
- キュー ＝ 先入れ先出し（FIFO）、enqueue/dequeue
- 配列 ＝ 参照・更新が速い、連結リスト ＝ 挿入・削除が速い
- 2分探索木の条件：左の子孫 ＜ 親 ＜ 右の子孫
- 試験での流れ図問題はトレース表を使って解く
- クイックソート ＝ 最高速の整列アルゴリズム（基準値で2グループに分割）
- ハッシュ法のデメリット ＝ 衝突が起こる可能性
- 2分探索法 ＝ 事前にソート済みが必要
modはわり算の余り
学習難易度：★★★★☆
アルゴリズムは暗記ではなく「処理を追う」ことが大切です。トレース表を使って丁寧に値を書き出せば、確実に得点源になります！
この記事について
基本情報技術者試験の合格を目指す方のために、参考書の内容を初心者向けにわかりやすく噛み砕いて解説しています。ITの基礎をしっかり固めて、一緒に合格を目指しましょう！
