【初心者向け】スタックとキューの違いとは？「皿洗いとレジ待ち」で覚えるデータ構造の基本

応用情報技術者試験をはじめとする情報処理技術者試験の学習を進めていると、データ構造の基本として「スタック」と「キュー」が頻出します。
これらはデータを一時的に格納するための基本的な仕組みですが、そのデータの出し入れのルールが異なります。

「後入れ先出し？」「先入れ先出し？」…言葉は似ていますが、この違いが混乱のもとになりがちです。参考書の解説を読んでも、ピンとこない方もいるかもしれません。

この記事では、そんなスタックとキューの本質的な違いを、「積み上げたお皿（スタック）」と「レジ待ちの行列（キュー）」という、たった2つの身近な光景で解説します。このイメージさえ掴めば、もう二度と迷うことはありません。

キュー (Queue)：「レジ待ちの行列」をイメージしよう

まず、分かりやすいキューから見ていきましょう。 キューとは、シンプルに「レジ待ちの行列」そのものです。

• データを入れる (Enqueue): 新しい人が行列の一番後ろに並びます。
• データを取り出す (Dequeue): レジでの会計が終わった先頭の人が列から抜けます。

つまり、「最初に行列に並んだ人 (First-In) が、最初に列から出ていく (First-Out)」のです。これを専門用語でFIFO（First-In, First-Out）と呼びます。

もし、「Aさん」「Bさん」「Cさん」の順番で行列に並んだら、レジを通過する順番は必ず「Aさん」→「Bさん」→「Cさん」になります。BさんがAさんを追い越すことはできません。
キューの出力パターンは、入力された順番と同じ1通りしかありません。

スタック (Stack)：「積み上げたお皿」をイメージしよう

次に、今回の問題の主役であるスタックです。
スタックは、「洗い終わって積み上げたお皿」をイメージしてください。

• データを入れる (Push): 洗ったお皿を、すでに積んであるお皿の一番上に置きます。
• データを取り出す (Pop): お皿を使うときは、一番上のお皿から取っていきます。

つまり、「最後に置いたお皿 (Last-In) を、最初に取り出す (First-Out)」ことになります。
これを専門用語でLIFO（Last-In, First-Out）と呼びます。下の方にあるお皿を、上の皿をどかさずに取ることはできませんよね。

この「下のお皿は、上のお皿がなくなるまで取れない」という制約こそが、スタックの全てです。

過去問に挑戦！「ありえない順番」を見抜く簡単な方法

さて、この「お皿のたとえ」を使って、情報処理技術者試験の問題を解いてみましょう。

令和7年度 応用情報技術者試験 春期 午前 問5より

【問題】 A, B, C の順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合、データの出力順序は何通りあるか。

解答と解説

この問題は令和3年度春期の応用情報技術者試験にも出題されています。
頻出のテーマであるので、選択肢がなくても答えられるようにしましょう。

すべてのパターンを書き出す

この問題のパターンを一つひとつ書き出しています。

スタック（皿）の状態を [] で、出力された順番を右側に示します。

パターン1:

1. Push A [A]
2. Pop A [] → 出力: A
3. Push B [B]
4. Pop B [] → 出力: A, B
5. Push C [C]
6. Pop C [] → 出力: A, B, C
   (出力結果: A, B, C)

パターン2:

1. Push A [A]
2. Pop A [] → 出力: A
3. Push B [B]
4. Push C [B, C]
5. Pop C [B] → 出力: A, C
6. Pop B [] → 出力: A, C, B
   (出力結果: A, C, B)

パターン3:

1. Push A [A]
2. Push B [A, B]
3. Pop B [A] → 出力: B
4. Pop A [] → 出力: B, A
5. Push C [C]
6. Pop C [] → 出力: B, A, C
   (出力結果: B, A, C)

パターン4:

1. Push A [A]
2. Push B [A, B]
3. Pop B [A] → 出力: B
4. Push C [A, C]
5. Pop C [A] → 出力: B, C
6. Pop A [] → 出力: B, C, A
   (出力結果: B, C, A)

パターン5:

1. Push A [A]
2. Push B [A, B]
3. Push C [A, B, C]
4. Pop C [A, B] → 出力: C
5. Pop B [A] → 出力: C, B
6. Pop A [] → 出力: C, B, A
   (出力結果: C, B, A)

---

この後お話しするように、C, A, B という出力順は実現不可能なため、全 5 パターンとなります。)

順列を使った考え方

もし数学が得意で、高校数学に出てきた「順列」の問題を覚えているのであれば、もっと簡単な方法があります。

今回A,B,Cの3つの要素を並び替えるので、スタックであるということを考慮しなければ、並び替えのパターンは「3! = 3 x 2 x 1 = 6」、つまり6通りであることがわかります。

この中から、「ありえない出力順はどれか？」を考えます。

スタックのルールはただ一つ、「下のお皿は、上のお皿がなくなるまで取れない」でした。
これを入力順「A→B→C」に当てはめてみましょう。

Aを先に入れ、その上にBを重ね、さらにその上にCを重ねた場合、お皿の重なり順は下からA, B, Cとなります。

この状態で、Bを無視してAを先に取り出すことは可能でしょうか？
絶対に不可能ですよね。Aを取り出すためには、必ずBとCが先に取り出されていなければなりません。

この原則を一般化すると、以下の「ありえないパターン」が見つかります。
「入力順で後だったものが先に出力され、その後、入力順で先だったものが出力される」という動きは可能ですが（例：Cを出力した後にBを出力）、その間に「入力順でさらに先だったものが挟まる」ことはありえないのです。

具体的に見てみましょう。 入力順は A → B → C です。

もし、出力順が C → A → B になることはあるでしょうか？

したがって、C, A, B という出力順は絶対にありえないのです。

このように、すべての出力パターンを考えなくても、「お皿のルール」に反する「ありえない順番」を見つけるだけで、スタックの動作を深く理解することもできます。
このように、ありえないパターンを見抜く方法も有効ですが、基本は全てのパターンを書き出す練習もしておきましょう。

とはいえ、試験中にどうしても時間がなく、4つの選択肢から当てずっぽうで答えないといけない時もあります。
そんな時、順列を知っていれば「スタックを考えなくても全部で6通りなのだから、6以上の選択肢はないな」と、選択肢を絞ることができます。

まとめ

• キューは「レジ待ちの行列」。先に入ったものが先に出る (FIFO)。
• スタックは「積み上げたお皿」。後から入れたものが先に出る (LIFO)。
• スタックの問題は、「下のお皿を先に取ることはできない」というたった一つのルールで、ありえない出力パターンを簡単に見抜くことができます。

このイメージを掴んで、データ構造の問題を得点源にしていきましょう！