第28話「先に来たのはどっち？」
テクノロジ系 ／ アルゴリズムとプログラミング ── テーマ：配列・スタック・キュー・木構造・流れ図・探索
▶ マンガで読む（無料・登録なし）この話で覚える用語（7語）
- 配列はいれつ
- 同じ種類のデータに番号（添字）をつけて並べて入れておく入れ物。値を1つ入れる箱が変数なら、配列は番号つきの箱が並んだロッカー。
- スタックすたっく
- 最後に入れたデータを最初に取り出すデータ構造。後入れ先出し（LIFO：Last In First Out）。入れることをプッシュ、取り出すことをポップという。
- キューきゅー
- 最初に入れたデータを最初に取り出すデータ構造。先入れ先出し（FIFO：First In First Out）。レジの行列や印刷の順番待ちと同じ。
- 木構造きこうぞう
- 1つの根から枝分かれしていく形のデータ構造。会社の組織図やフォルダの階層が代表例。子が最大2つのものを2分木という。
- 流れ図ながれず
- 処理の手順を記号と矢印で表した図。フローチャートともいう。どんな手順も「順次・選択・繰り返し」の3つの組み合わせで表せる。
- 2分探索にぶんたんさく
- 整列済みのデータの真ん中と比べ、探す範囲を半分ずつ絞りこむ方法。データが多いほど線形探索より速い。データが整列されていることが条件。
- 整列（ソート）せいれつ
- データを小さい順（昇順）や大きい順（降順）に並べかえること。バブルソート・選択ソートなどの方法がある。
試験に出るポイント
- スタック＝後入れ先出し（LIFO：Last In First Out）
- キュー＝先入れ先出し（FIFO：First In First Out）
- スタック＝お皿洗い。最後に積んだお皿から洗う
- キュー＝ラーメン屋の行列。並んだ順に入店、割りこみ禁止！
- ブラウザの「戻る」は、直前に見たページから戻る＝スタックの考え方
- スタック＝後入れ先出し（LIFO）／キュー＝先入れ先出し（FIFO）
- 「最後に格納したデータを最初に取り出す」と問われたら → スタック
- 2分探索は、データが整列済みであることが条件
- データが多いほど、線形探索より2分探索のほうが比べる回数がずっと少ない
- 流れ図の基本構造は順次・選択・繰り返しの3つ
- 木構造＝根から枝分かれ（組織図・フォルダの階層）
確認クイズ（ITパスポート試験の形式）
- A
- C
- B
- 何も残っていない
答えと解説を見る
正解：ア A
スタックは後入れ先出し。C、Bの順に取り出され、Aが残ります。Cが残ると考えたなら、先入れ先出しのキューと取り違えています。
- 最初に格納したデータを最初に取り出す
- 最後に格納したデータを最初に取り出す
- 1つの根から枝分かれした形でデータを管理する
- データに番号をつけて並べ、番号で取り出す
答えと解説を見る
正解：ア 最初に格納したデータを最初に取り出す
キューは先入れ先出し（FIFO）。後入れ先出しはスタック、枝分かれは木構造、番号をつけて並べるのは配列です。
- データが整列されている
- データの件数が偶数である
- データがスタックに格納されている
- データの件数が1,000件以下である
答えと解説を見る
正解：ア データが整列されている
2分探索は真ん中と比べて大小で半分を捨てるので、データが整列済みでないと使えません。件数が偶数か奇数か、何件あるかは関係ありません。
マンガのセリフ（文字版）
問い合わせメールの当番になったミライ
ミライ「新しいメールから返してたら、朝のお客さまがずっと待ちぼうけ…！」
ツカサ先輩「問い合わせは来た順に片づける。これがキューの考え方だ」
ミライ「レジの行列と同じですね」
ツカサ先輩「その逆がスタック。最後に入れたものから取り出す」
ミライ「スタック…雪道で車が動けなくなる、あれですか？」
ツカサ先輩「それは「はまって動けない」のほうだ！こっちは積み重ね。お皿の山だ！」
- スタック＝後入れ先出し（LIFO：Last In First Out）
- キュー＝先入れ先出し（FIFO：First In First Out）
- スタック＝お皿洗い。最後に積んだお皿から洗う
- キュー＝ラーメン屋の行列。並んだ順に入店、割りこみ禁止！
- ブラウザの「戻る」は、直前に見たページから戻る＝スタックの考え方
ツカサ先輩「値を1つ入れる箱が変数。番号つきの箱をずらっと並べたのが配列だ」
ミライ「番号つきのロッカーみたい！」
ミライ「フォルダの中にフォルダがあるのは？」
ツカサ先輩「根っこから枝分かれする木構造だ。会社の組織図も同じ形だな」
翌日
部長「お客さま番号5821番の記録、1万件の中からすぐ出せ！」
ミライ「い、1件ずつ見ていきます…！」
ツカサ先輩「先頭から順に1件ずつ比べるのが線形探索。最悪1万回かかる」
ミライ「それじゃ日が暮れます…」
ツカサ先輩「番号順に並んでいれば2分探索が使える。真ん中と比べて、半分ずつ捨てるんだ」
ミライ「バラバラに並んでいたら？」
ツカサ先輩「まず整列（ソート）で番号順に並べかえる。2分探索はそのあとだ」
ツカサ先輩「こういう手順は流れ図で描く。基本の形は3つだけだ」
ミライ「番号順に並べ替えたら、2分探索ですぐ見つかりました！」
部長「はやっ！」
- スタック＝後入れ先出し（LIFO）／キュー＝先入れ先出し（FIFO）
- 「最後に格納したデータを最初に取り出す」と問われたら → スタック
- 2分探索は、データが整列済みであることが条件
- データが多いほど、線形探索より2分探索のほうが比べる回数がずっと少ない
- 流れ図の基本構造は順次・選択・繰り返しの3つ
- 木構造＝根から枝分かれ（組織図・フォルダの階層）
オチ
部長「わしの机の書類の山もスタックだ！一番下の去年の書類は永遠に出てこん！」
ミライ「それはただの片づけ不足です！」