スタックとキュー（LIFO と FIFO）
スタック（LIFO）とキュー（FIFO）の違いを言い分けられ、push/pop や enq/deq の操作を紙の上で追って、取り出される値を答えられるようになる。スタックで出力できる列の判定、必要なスタック数、並べ替えの回数を問う問題も解けるようになる。
スタックとキューは、関数の呼出しやブラウザの「戻る」、処理の順番待ちなど、プログラムの裏側で常に使われている基本のデータ構造です。過去問では、用語を問う問題と操作を追う問題の両方が繰り返し出題されています。
このレッスンで稽古する（用語チェック・過去問）結論：スタックは後入れ先出し、キューは先入れ先出し
スタックは、最後に入れたデータから取り出すデータ構造です。この性質をLIFO（Last In First Out：後入れ先出し）といいます。キュー（待ち行列）は最初に入れたデータから取り出す構造で、性質はFIFO（First In First Out：先入れ先出し）です。
- スタックは積み重ねたお皿：洗ったお皿は上に積み、使うときも上から取ります。
- キューはレジの行列：先に並んだ人から会計し、新しく来た人は列の後ろに並びます。
| 比べる点 | スタック | キュー（待ち行列） |
|---|---|---|
| 取り出す順 | LIFO（後入れ先出し） | FIFO（先入れ先出し） |
| 入れる操作 | push（プッシュ） | enqueue（エンキュー・ENQ・enq） |
| 取り出す操作 | pop（ポップ） | dequeue（デキュー・DEQ・deq） |
| 出入口 | 頂上の1か所だけ | 入口は末尾、出口は先頭の2か所 |
| 身近な例 | 積んだお皿、関数の呼出しと復帰 | レジの行列、印刷の順番待ち |
用語の見分け：選択肢に混ぜられる言葉
選択肢には、スタックとキュー以外のデータ構造や、つづりの似た略語が混ぜられます。それぞれ「何についての言葉か」が違うので、表で区別しておきましょう。
| 用語 | 意味 | スタック・キューとの関係 |
|---|---|---|
| LIFO | 後入れ先出し | スタックの性質 |
| FIFO | 先入れ先出し | キューの性質 |
| LILO | 後に入れたものが後に出る | 意味はFIFOと同じだが、一般的な呼び方ではない。スタックの答えにはならない |
| LRU | 最も長い間使われていないものを追い出す方式 | ページ置換えの方式で、データ構造の性質ではない |
| データ構造 | 特徴 | 見分けのキーワード |
|---|---|---|
| スタック | 頂上だけでデータを出し入れする | 後入れ先出し・push/pop |
| キュー | 末尾に入れて先頭から出す | 先入れ先出し・enq/deq |
| 配列 | 添字（要素の番号）で要素を直接参照する | 「添字を用いて参照」 |
| 木構造・リスト | ポインタで要素どうしをつなぐ | 「ポインタで階層関係を表現」 |
| ヒープ | 親の値が子の値より常に大きい（または小さい）木 | 最大値・最小値をすぐ取り出せる |
| ハッシュ | キーから計算した位置にデータを格納する | ハッシュ関数・衝突 |
操作を追うコツ：中身を1行ずつ書く
トレース問題（操作を順に追う問題）は、暗算せずに操作のたびにデータ構造の中身を1行で書くのがいちばん速くて確実です。書き方を先に決めておけば、上下や前後の取り違えがなくなります。
- スタック：左端を底、右端を頂上として書く。push は右端に足し、pop は右端を消す。
- キュー：左端を先頭、右端を末尾として書く。enq は右端に足し、deq は左端を消す。
- 取り出した値は、行の横に「→5」のようにメモしておく。
選択肢がスタックの図（上から順に並べたもの）なら、最後に自分のメモを右端から読んで照合します。スタックとキューの両方が出てくる問題では、2つの中身を横に並べて書きます。
コードからスタックを見抜く
変数 p で位置を管理する関数の問題では、入れる位置と取り出す位置が同じ p かどうかを見ます。f(x) は「p を1増やして A[p] に入れる」、g() は「A[p] を取り出してから p を1減らす」なので、最後に入れた位置から取り出しています。つまりスタックです。
キューなら、入れる位置（末尾）と取り出す位置（先頭）を別々の変数で管理する必要があります。位置を表す変数が p の1つだけなのは、出入口が1か所しかないスタックの特徴です。
再帰呼出しとスタック（前のレッスンの続き）
関数を呼び出すとき、コンピュータは局所変数（その関数の中だけで使う変数）、仮引数（関数の側で値を受け取る変数）、戻り番地（呼び出した関数の処理が終わった後に戻る命令の位置）をスタックに積みます。再帰で何段も呼び出すとこれらが積み重なり、復帰するときは最後に積んだものから順に取り出します。だから取り出し方はLIFOで、「FIFOで取り出す」と書かれていたらそこが誤りです。
応用：出力できる順番・必要なスタック数・並べ替えの回数
出力できる列かどうかの判定は、出力列を先頭から1つずつ、実際に push/pop して作れるか試します。判定のコツは、スタックに残っている値どうしは後から積んだものから順にしか出せないことです。例えば A, B, C, D の順に到着する場合、D を出した直後に B → C の順で出すことはできません（B は C の下にあるため）。
必要なスタック数は、「待たせておいて、入ってきた順のまま出したい値」は同じスタックに入れられない、という点から数えます。キューとスタックを使った並べ替えは、キューの先頭から取り出してスタックに積み、逆の順番でキューに戻す操作を追って回数を数えます。
スタックの操作を順に追う
ア [図] スタック（上から）1, 7, 3
イ [図] スタック（上から）3, 4, 6
ウ [図] スタック（上から）3, 7, 1
エ [図] スタック（上から）6, 4, 3
解き方と答えを見る
- 右端を頂上として、操作のたびにスタックの中身を書く。
- PUSH 1 → [1]、PUSH 5 → [1, 5]
- POP → 5を取り出す → [1]
- PUSH 7 → [1, 7]、PUSH 6 → [1, 7, 6]、PUSH 4 → [1, 7, 6, 4]
- POP → 4を取り出す → [1, 7, 6]、POP → 6を取り出す → [1, 7]
- PUSH 3 → [1, 7, 3]（左が底、右が頂上）
- 選択肢の図は上から並んでいるので、メモを右端から読むと 3, 7, 1。
答え：ウ（上から 3, 7, 1）
キューの操作を順に追う
ア 1
イ 2
ウ 5
エ 6
解き方と答えを見る
- 左端を先頭として、操作のたびにキューの中身を書く。
- ENQ 1, ENQ 2, ENQ 3 → [1, 2, 3]
- DEQ → 先頭の1を取り出す → [2, 3]
- ENQ 4, ENQ 5 → [2, 3, 4, 5]
- DEQ → 2を取り出す → [3, 4, 5]
- ENQ 6 → [3, 4, 5, 6]
- DEQ → 3を取り出す → [4, 5, 6]、DEQ → 4を取り出す → [5, 6]
- 次の DEQ では、先頭の5が取り出される。
答え：ウ（5）
スタックとキューを同時に追う
ア a
イ b
ウ c
エ d
解き方と答えを見る
- スタック（右端が頂上）とキュー（左端が先頭）を並べて書く。最初はどちらも空。
- push(a) → スタック[a]、push(b) → スタック[a, b]
- enq(pop())：pop で頂上の b を取り出し、キューに入れる → スタック[a]、キュー[b]
- enq(c) → キュー[b, c]
- push(d) → スタック[a, d]
- push(deq())：deq で先頭の b を取り出し、スタックに積む → キュー[c]、スタック[a, d, b]
- x ← pop()：頂上の b を取り出す → x = b
答え：イ（b）
1つのスタックで出力できる列を判定する
ア A，D，B，C
イ B，D，A，C
ウ C，B，D，A
エ D，C，A，B
解き方と答えを見る
- 到着順は A → B → C → D。選択肢ごとに、先頭から実際に push/pop して試す。
- ア A, D, B, C：A を積んですぐ出す。D を出すには B, C, D を積む → [B, C, D]。D を出すと頂上は C なので、次に B は出せない → 不可。
- イ B, D, A, C：A, B を積んで B を出す → [A]。C, D を積んで D を出す → [A, C]。頂上は C なので A は出せない → 不可。
- ウ C, B, D, A：A, B, C を積んで C を出す → [A, B]。B を出す → [A]。D を積んですぐ出す → [A]。A を出す。すべて出せる → 可能。
- エ D, C, A, B：A〜D を積んで D, C を出す → [A, B]。頂上は B なので A は出せない → 不可。
答え：ウ（C, B, D, A）
必要なスタックの数を数える
ア 1
イ 2
ウ 3
エ 4
解き方と答えを見る
- 入力順は A → C → K → S → T、出力したい順は S → T → A → C → K。
- S と T は、来たらすぐ push して pop すれば出せる。どのスタックの頂上に積んでもすぐ取り出すので、ほかの文字の邪魔にならない。
- A, C, K は S, T より先に来るので、S, T が出るまでスタックで待たせる必要がある。
- A, C, K は入ってきた順のまま（A → C → K）出したい。同じスタックに2つ入れると、後から入った方が先に出てしまう。
- したがって A, C, K はそれぞれ別のスタックに入れる必要があり、最小で3個。
答え：ウ（3個）
キューとスタックで並べ替える回数を数える
ア 2
イ 3
ウ 4
エ 5
解き方と答えを見る
- キューの中身は先頭から A, B, C, D。目標は D, C, B, A。使える操作は、キューの先頭をスタックに移す deq_push と、スタックの頂上をキューの末尾に移す pop_enq の2つだけ。
- D を先頭にするには、D より前にある A, B, C をキューから外す必要がある。外す手段は deq_push しかないので、deq_push は最低3回必要。
- deq_push を3回行う → キュー[D]、スタック[A, B, C]（右端が頂上）
- pop_enq を3回行う：C, B, A の順に取り出して末尾に入れる → キュー[D, C, B, A]
- 3回で実現でき、3回より少ない回数では不可能なので、最小は3回。
答え：イ（3回）
要点（試験直前に読む）
- スタック＝LIFO（後入れ先出し）・push/pop。キュー＝FIFO（先入れ先出し）・enq/deq。
- トレースは操作のたびに中身を1行で書く。スタックは右端が頂上、キューは左端が先頭。
- p を増やして入れ、同じ p から取り出して減らす関数はスタック。
- 再帰呼出しでは局所変数・仮引数・戻り番地をスタックに積み、LIFO で取り出す。
- スタックに残っている値は、後から積んだものから順にしか出せない。出力できる列やスタック数はこのルールで判定する。
ひっかけ
- FIFO と LIFO の入れ替え：「スタック＝FIFO」「再帰からの復帰は FIFO」は誤り。Last が先に出るのがスタック。
- LRU・LILO のダミー：LRU はページ置換えの方式で、LILO は一般的な呼び方ではない。スタックの性質を聞かれたら答えは LIFO だけ。
- 図の上下の読み違い：選択肢のスタックの図は上が頂上。自分のメモ（右端が頂上）を右から読んで照合する。
- スタックとキューを同時に追う問題で、deq を末尾から取ってしまう：deq は必ず先頭（いちばん古いデータ）から取り出す。
- キューの説明にほかの構造の説明が混ぜられる：「添字で参照」は配列、「ポインタで階層関係」は木構造、「後に入れたものが先に出る」はスタック。
用語（16）
最後に入れたデータから順に取り出すデータ構造。
⚠ キュー：最初に入れたデータから取り出す。「後入れ先出し」ならスタック。
最初に入れたデータから順に取り出すデータ構造。
⚠ スタック：最後に入れたデータから取り出す。「先入れ先出し」ならキュー。
後から入れたものが先に出る「後入れ先出し」のこと。スタックの性質。
⚠ FIFO と1文字違い。「Last が先（First）に出る」のがスタック。
先に入れたものが先に出る「先入れ先出し」のこと。キューの性質。
⚠ LIFO：スタックの性質。再帰呼出しの復帰は FIFO ではなく LIFO。
後に入れたものが後に出ること。意味は FIFO と同じで、試験ではダミーの選択肢として出る。
⚠ LIFO：スタックの性質。スタックを問われて LILO を選ばない。
スタックの頂上にデータを積む操作。
⚠ エンキュー：キューの末尾にデータを入れる操作。
スタックの頂上（最後に積んだもの）からデータを取り出す操作。
⚠ デキュー：キューの先頭（最も古いもの）から取り出す。
キューの末尾にデータを入れる操作。
⚠ プッシュ：スタックの頂上に積む操作。
キューの先頭からデータを取り出す操作。
⚠ ポップ：スタックの頂上（最後に入れたもの）から取り出す。
最も長い間使われていないものを追い出す、ページ置換えなどの方式。
⚠ LIFO・FIFO：データ構造の取り出し順を表す言葉。LRU はデータ構造の性質ではない。
親の値が子の値より常に大きい（または小さい）木構造で、最大値（最小値）をすぐ取り出せる。
⚠ スタック・キュー：入れた順番で取り出す。ヒープは値の大小で取り出す。
キーから計算した値でデータの格納位置を決める方式。
各要素が最大2つの子をもつ木構造。
呼び出した関数の処理が終わった後に戻る命令の位置。
その関数の中だけで使われる変数。
関数を定義する側で、渡された値を受け取る変数。
⚠ 実引数：関数を呼び出す側が実際に渡す値。
このレッスンの過去問
- スタックのLIFO特性(後入れ先出し)基本情報技術者試験 科目A免除 修了試験 20260125 実施分 問5
- スタックのpush/popトレース平成30年度 春期 基本情報技術者試験 午前 問5
- 待ち行列(キュー)のFIFO操作平成30年度 秋期 基本情報技術者試験 午前 問5
- キューとスタックの操作トレース基本情報技術者試験 科目A免除 修了試験 20230723 実施分 問5
- スタックで出力可能なデータ列の判定平成29年度 秋期 基本情報技術者試験 午前 問5
- スタックによる出力順序の実現に必要なスタック数令和元年度 秋期 基本情報技術者試験 午前 問8
- キューとスタックによる並べ替え操作回数平成24年度 秋期 基本情報技術者試験 午前 問5