基本情報 科目B スタックとキューのトレース練習
基本情報技術者試験の科目Bでは、探索・ソート・再帰といったアルゴリズムと並んで、データ構造そのものの操作もよく問われます。なかでも定番が スタック と キュー です。どちらも「データを順番にためて、順番に取り出す」入れ物ですが、取り出す順番のルールが正反対なので、ここを取り違えると設問の空欄がまるごと外れます。本記事は、スタックとキューの操作を変数の値を表に書きながら 1 つずつ追う トレース で攻略する練習帳です。合計・最大値・線形探索のトレース練習・二分探索のトレース練習・ソート（整列）のトレース練習・再帰のトレース練習 の続編にあたります。
本記事は 過去問AI が学習用に作成したオリジナルの例題です。掲載している擬似言語は IPA の過去問・公式サンプルの転載ではなく、説明用に書き起こしたものです。擬似言語の正式な記述形式は必ず IPA 公式ページ で確認してください。記法そのものの読み方は 基本情報 科目Bの擬似言語 記法早見表 にまとめています。
スタックとキューは「出し方」が正反対
- スタック（stack）：後入れ先出し（LIFO：Last In, First Out）。あとから入れたものが先に出る。本を机に積み上げて、上から取るイメージ
- キュー（queue）：先入れ先出し（FIFO：First In, First Out）。先に入れたものが先に出る。レジに並んだ行列で、先頭から順にさばかれるイメージ
操作の名前も決まっています。
- スタック：上に積むのが プッシュ（push）、一番上を取り出すのが ポップ（pop）
- キュー：後ろに追加するのが エンキュー（enqueue）、先頭から取り出すのが デキュー（dequeue）
この記事の例題は、次の約束ごとで進めます（科目Bの標準的なルールです）。
- 代入は ←（右の値を左の変数に入れる）
- 配列の添字は 1 始まり（最初の要素が 1 番目）
- 関数定義の先頭の ○ は「ここから関数の中身」を表します
記法そのものが不安なら、先に 記法早見表 で ← や配列の添字の扱いを確認してから戻ってくるとスムーズです。
スタックの例題コード
配列 スタック と、一番上の位置を指す変数 頂点（最初は 0 ＝空）でスタックを表します。
○プッシュ(整数型: 値)
頂点 ← 頂点 + 1
スタック[頂点] ← 値
○整数型: ポップ()
値 ← スタック[頂点]
頂点 ← 頂点 - 1
return 値
プッシュは「頂点を 1 つ上げてから、その位置に値を置く」。ポップは「頂点の位置の値を読んでから、頂点を 1 つ下げて返す」。頂点が常に「一番上の要素の位置」を指しているのがポイントです。
スタックをトレースする
プッシュ(3) → プッシュ(7) → プッシュ(1) → ポップ() → プッシュ(9) → ポップ() → ポップ() の順に操作します。中身は左を底、右を上（頂点側）として並べます。
| 操作 | 頂点（操作後） | スタックの中身（底→上） | 戻り値 |
|---|---|---|---|
| プッシュ(3) | 1 | 3 | — |
| プッシュ(7) | 2 | 3, 7 | — |
| プッシュ(1) | 3 | 3, 7, 1 | — |
| ポップ() | 2 | 3, 7 | 1 |
| プッシュ(9) | 3 | 3, 7, 9 | — |
| ポップ() | 2 | 3, 7 | 9 |
| ポップ() | 1 | 3 | 7 |
取り出された順番は 1 → 9 → 7。最後に積んだものから先に出ていく、これが LIFO（後入れ先出し） です。3 つ目のポップで残るのは、最初に積んだ 3 だけになります。
キューの例題コード
配列 キュー と、取り出す先頭位置 先頭（最初は 1）・最後に入れた位置 末尾（最初は 0 ＝空）でキューを表します。
○エンキュー(整数型: 値)
末尾 ← 末尾 + 1
キュー[末尾] ← 値
○整数型: デキュー()
値 ← キュー[先頭]
先頭 ← 先頭 + 1
return 値
エンキューは「末尾を 1 つ進めて、その位置に値を置く」。デキューは「先頭の位置の値を読んでから、先頭を 1 つ進めて返す」。先頭と末尾という 2 つのポインタが、どちらも増える方向に動くのが特徴です。
キューをトレースする
スタックと比べやすいよう、まったく同じ入力で操作します。エンキュー(3) → エンキュー(7) → エンキュー(1) → デキュー() → エンキュー(9) → デキュー() → デキュー()。残っている要素は「先頭から末尾まで」を並べます。
| 操作 | 先頭 | 末尾 | 残っている要素（先頭→末尾） | 戻り値 |
|---|---|---|---|---|
| エンキュー(3) | 1 | 1 | 3 | — |
| エンキュー(7) | 1 | 2 | 3, 7 | — |
| エンキュー(1) | 1 | 3 | 3, 7, 1 | — |
| デキュー() | 2 | 3 | 7, 1 | 3 |
| エンキュー(9) | 2 | 4 | 7, 1, 9 | — |
| デキュー() | 3 | 4 | 1, 9 | 7 |
| デキュー() | 4 | 4 | 9 | 1 |
取り出された順番は 3 → 7 → 1。先に入れたものから先に出ていく、これが FIFO（先入れ先出し） です。
同じ入力なのに取り出す順が逆になる
ここが本記事の山場です。スタックもキューも、入れた値は 3 → 7 → 1 → 9 とまったく同じでした。それでも取り出した順番は、
- スタック：1 → 9 → 7（後入れ先出し）
- キュー：3 → 7 → 1（先入れ先出し）
と正反対になります。設問は「この操作列のあと、最初に取り出される値はどれか」「3 回取り出すと何が残るか」といった形で、この順序の違いを突いてきます。入れた順だけ見て答えず、必ずスタックかキューかを確認するのが鉄則です。
つまずきやすい3つのポイント
- 出し入れする場所を取り違える。スタックは出すのも入れるのも 上（頂点）の 1 か所。キューは 末尾に入れて先頭から出すと、入口と出口が別です。「キューなのに後ろから取り出す」と勘違いすると順序が丸ごと逆になります。
- 読む順と、ポインタを動かす順。ポップもデキューも「先に値を読んでから、ポインタを動かす」順序です。先に 頂点 ← 頂点 - 1 をしてしまうと、1 つずれた要素を読んでしまいます。トレースでは「値 ← …」の行を必ず先に処理してください。
- 配列に古い値は残る。配列で実装すると、ポップしても
スタック[3]の中身（さっきの例なら 1）は物理的には残っています。論理的な中身は「頂点が指す範囲」で決まるので、頂点より上の値は無視します。キューも同じで、デキュー済みのキュー[1]は残っていても、先頭より前は存在しない扱いです。
もう一つの定番：循環バッファ（リングバッファ）
キューを配列で素直に作ると、エンキュー／デキューを繰り返すうちに 末尾 がどんどん右へ進み、配列の右端を使い切ってしまいます。そこで実務や応用問題では、配列の端まで来たら先頭（添字 1）へ折り返して空いた場所を再利用する 循環バッファ（リングバッファ） がよく登場します。先頭・末尾を「配列サイズで割った余り」で進めるのがコツですが、まずは本記事のように まっすぐ伸びる素朴なキュー で先頭・末尾の動きを体に入れてから、折り返しに進むのがおすすめです。
トレースで詰まらないためのコツ
スタックは 頂点 1 本、キューは 先頭・末尾の 2 本のポインタを、操作のたびに表へ書き出すのが最大のコツです。中身を毎回ぜんぶ書き直すより、「ポインタがいくつになったか」と「その範囲に何が並ぶか」をセットで追うと、要素数が増えても迷子になりません。そして操作の前に必ず「これはスタック？キュー？」と一言確認してから取り出す向きを決めてください。
次のステップ
スタックとキューまで追えれば、あとは要素が参照でつながる 連結リスト（単方向リスト）のトレース練習 に進むと、科目Bで問われるデータ構造の基本がそろいます。アルゴリズムのトレースがまだなら、基礎の 合計・最大値・線形探索のトレース練習、半分ずつ絞り込む 二分探索のトレース練習、二重ループの ソート（整列）のトレース練習、コールスタックを追う 再帰のトレース練習 を先にどうぞ。読む速度を上げる訓練法は 基本情報科目B｜擬似言語アルゴリズム読解の3ステップ訓練法 で扱っています。つまずきが記法なのかトレースなのか切り分けたいときは 科目Bがわからない人へ、科目B 全体の進め方は 基本情報技術者 科目B完全対策 が地図になります。
手を動かす練習台としては、過去問AI の 基本情報 アルゴリズムとプログラミング分野の過去問 が使えます（こちらは科目A 相当の選択式で、科目B そのものの形式ではない点だけ意識してください）。各問題ページの AI コパイロットに「このスタックの操作を、頂点の値と中身を表にして 1 つずつトレースして」と頼めば、本記事と同じ追い方を対話でその場で再現できます。
よくある質問
Q. スタックとキューはどう違いますか？ 取り出す順番のルールが正反対です。スタックは後入れ先出し（LIFO）で、あとから入れたものが先に出ます。キューは先入れ先出し（FIFO）で、先に入れたものが先に出ます。同じ順番でデータを入れても、取り出す順番は逆になります。設問では入れた順だけで判断せず、まずスタックかキューかを確認してください。
Q. プッシュ・ポップ・エンキュー・デキューとは何ですか？ スタックの操作が、上に積むプッシュと一番上を取り出すポップです。キューの操作が、後ろに追加するエンキューと先頭から取り出すデキューです。スタックは上の 1 か所だけで出し入れし、キューは末尾に入れて先頭から出す、と入口と出口の場所が違う点が区別のかなめです。
Q. ポップやデキューでトレースが合わなくなります。何が原因ですか？ 多くは処理する順番の取り違えです。ポップもデキューも、先に値を読んでから、そのあとでポインタ（頂点や先頭）を動かします。先にポインタを動かしてしまうと、1 つずれた要素を読んでしまい戻り値が変わります。トレースのときは値を読む行を必ず先に処理し、ポインタの更新は後に書いてください。
Q. 配列でスタックを作ると、ポップした値は消えますか？ 物理的には配列に残ります。ポップは頂点を 1 つ下げるだけなので、古い値はその場所に残っていますが、頂点より上は「無い」ものとして扱います。論理的な中身は常に頂点が指す範囲で決まる、と考えるとトレースが安定します。キューも同様で、デキュー済みの先頭より前の要素は残っていても存在しない扱いです。
まとめ
- スタックは 後入れ先出し（LIFO）、キューは 先入れ先出し（FIFO）。取り出す順番のルールが正反対
- スタックは 頂点 1 本のポインタで上だけを出し入れ。キューは 先頭・末尾 の 2 本で末尾に入れて先頭から出す
- 同じ入力 3→7→1→9 でも、スタックは 1→9→7、キューは 3→7→1 と取り出し順が逆になる
- ポップ・デキューは 先に値を読んでからポインタを動かす。配列実装では古い値が残るので ポインタが指す範囲で中身を判断する
- トレースは ポインタの値とその範囲の並びをセットで表に書き、操作の前に「スタック？キュー？」を確認する
線形探索・二分探索・ソート・再帰に、データ構造のスタック・キューを加えれば、科目Bのアルゴリズム設問で読めない問題はほぼ無くなります。