スタックとキューとは？LIFO・FIFO・PUSH・POPを基礎から理解しよう

はじめに

前回の記事では、複数のデータを管理するリストについて学びました。

データ構造には、ほかにも重要なものがあります。

その代表が、

スタック（Stack）とキュー（Queue）

です。

どちらも複数のデータを一時的に保持するためのデータ構造ですが、データを取り出す順番が大きく異なります。

スタック
→ 後から入れたものを先に取り出す

キュー
→ 先に入れたものを先に取り出す

応用情報技術者試験では、

LIFO
FIFO
PUSH
POP
ENQUEUE
DEQUEUE
スタックポインタ
循環キュー

などを理解しておくことが重要です。

1. スタックとは

**スタック（Stack）**とは、

最後に入れたデータを最初に取り出すデータ構造

です。

例えば、机の上に本を積み重ねる場面を考えてみましょう。

最初

┌───┐
│ A │
└───┘

その上にBを置きます。

┌───┐
│ B │ ← 最後に入れた
├───┤
│ A │
└───┘

さらにCを置きます。

┌───┐
│ C │ ← 最後に入れた
├───┤
│ B │
├───┤
│ A │
└───┘

ここから本を取り出す場合、一番上にあるCから取り出します。

C → B → A

つまり、

入れた順番
A → B → C

取り出す順番
C → B → A

となります。

2. LIFOとは

スタックの特徴を表す言葉がLIFOです。

正式名称は、

Last In, First Out

です。

日本語では、

後入れ先出し

と呼ばれます。

Last In
最後に入れた

↓

First Out
最初に出る

例えば、

A
↓
B
↓
C

という順番でスタックへ入れた場合、

C
↓
B
↓
A

という順番で取り出します。

🍯 スタック = LIFO = 後入れ先出し

この3つはセットで覚えておきましょう。

3. PUSHとは

スタックへデータを追加する操作を**PUSH（プッシュ）**と呼びます。

例えば、

┌───┐
│ B │
├───┤
│ A │
└───┘

というスタックへCをPUSHすると、

   PUSH C
      ↓

┌───┐
│ C │
├───┤
│ B │
├───┤
│ A │
└───┘

となります。

つまり、

PUSH = スタックへデータを入れる

です。

4. POPとは

スタックからデータを取り出す操作を**POP（ポップ）**と呼びます。

例えば、

┌───┐
│ C │ ← 取り出す
├───┤
│ B │
├───┤
│ A │
└───┘

に対してPOPすると、

POP
↓
Cを取り出す

残ったスタックは、

┌───┐
│ B │
├───┤
│ A │
└───┘

となります。

つまり、

POP = スタックの一番上からデータを取り出す

操作です。

5. PUSHとPOP

整理すると、

操作	意味
PUSH	スタックへデータを追加
POP	スタックからデータを取り出す

例えば、

PUSH A
PUSH B
PUSH C
POP

と操作すると、

まず、

┌───┐
│ C │
├───┤
│ B │
├───┤
│ A │
└───┘

となり、POPによってCが取り出されます。

結果、

取り出された値 = C

となります。

6. スタックの先頭

スタックでデータを追加・削除する側を、

トップ（Top）

などと呼びます。

      TOP
       ↓
┌─────────┐
│    C    │
├─────────┤
│    B    │
├─────────┤
│    A    │
└─────────┘

PUSHもPOPも基本的にはこのTOP側で行います。

これがスタックの特徴です。

7. スタックポインタとは

スタックを配列などで実装する場合、

現在のスタックの先頭位置

を管理する必要があります。

そのために利用されるのが**スタックポインタ（Stack Pointer）**です。

例えば、

位置
0   A
1   B
2   C ← SP
3
4

のように、スタックポインタが現在のTOPの位置を示します。

新しいデータをPUSHすると、

0   A
1   B
2   C
3   D ← SP
4

のように位置が変化します。

8. スタックポインタとPUSH・POP

考え方を単純化すると、

PUSHでは、

スタックポインタを更新
↓
データを格納

POPでは、

データを取り出す
↓
スタックポインタを更新

というように、スタックポインタを使って現在位置を管理します。

ただし、実際に「SPが次の空き領域を指すのか」「現在の最上位要素を指すのか」は実装によって異なります。

そのため試験問題では、問題文で定義されたスタックポインタの意味を確認することが重要です。

9. スタックオーバーフロー

スタックに格納できる容量には限界がある場合があります。

例えば、

最大4個

┌───┐
│ D │
├───┤
│ C │
├───┤
│ B │
├───┤
│ A │
└───┘

すでに満杯なのに、

PUSH E

しようとすると、それ以上データを格納できません。

このようにスタックの容量を超えてデータを追加しようとする状態を、スタックオーバーフローと呼びます。

10. スタックアンダーフロー

逆に、スタックが空なのにPOPしようとすると、

空のスタック

┌───┐
│   │
└───┘

POP
↓
取り出すものがない

となります。

このような状態をスタックアンダーフローと呼びます。

整理すると、

オーバーフロー
→ 入れすぎ

アンダーフロー
→ 取り出そうとしたが空

です。

11. スタックはどこで使われる？

スタックはコンピュータ内部のさまざまな場所で利用されます。

代表例が関数やサブルーチンの呼出しです。

例えば、

main
↓
関数A
↓
関数B

と呼び出したとします。

関数Bが終了したら、

関数B
↓
関数A
↓
main

と、呼び出した順番とは逆方向に戻ります。

これは、

main
A
B

と積み重ねて、

B
A
main

の順番で戻るため、スタックと非常に相性がよい処理です。

12. 再帰処理とスタック

**再帰（Recursion）**でもスタックが重要です。

再帰とは、関数が自分自身を呼び出す処理です。

例えば、

function(3)
↓
function(2)
↓
function(1)

と呼び出された場合、それぞれの呼出し情報がスタックへ積まれていきます。

処理が終了すると、

function(1)
↓
function(2)
↓
function(3)

と戻っていきます。

そのため、再帰処理が深くなりすぎるとスタック領域を大量に使用し、スタックオーバーフローにつながることがあります。

13. 逆ポーランド記法とスタック

応用情報では、**逆ポーランド記法（後置記法）**とスタックの組合せも重要です。

例えば、

3 + 4

を逆ポーランド記法で表すと、

3 4 +

となります。

計算するときは、

3をPUSH
4をPUSH
+
↓
4と3をPOP
↓
3 + 4
↓
7をPUSH

というようにスタックを利用できます。

複雑な式でも、演算対象をスタックへ積みながら計算できます。

14. キューとは

続いて**キュー（Queue）**です。

キューとは、

最初に入れたデータを最初に取り出すデータ構造

です。

英語のQueueには「待ち行列」という意味があります。

例えば、お店のレジを想像すると分かりやすいです。

レジ ← A ← B ← C

Aさんが最初に並び、次にBさん、その次にCさんが並びました。

当然、最初に会計するのはAさんです。

入った順番
A → B → C

出る順番
A → B → C

となります。

15. FIFOとは

キューの特徴を表す言葉がFIFOです。

正式名称は、

First In, First Out

です。

日本語では、

先入れ先出し

と呼ばれます。

First In
最初に入れた

↓

First Out
最初に出る

つまり、

🍯 キュー = FIFO = 先入れ先出し

です。

スタックのLIFOとセットで覚えましょう。

16. スタックとキューの違い

ここは非常に重要です。

スタック

入れる
 ↓
[A][B][C]
       ↑
     取り出す

最後に入れたCから取り出します。

一方、キューは、

取り出す              入れる
   ↓                    ↓
[A] → [B] → [C] → [D]

最初に入れたAから取り出します。

整理すると、

データ構造	方式	日本語
スタック	LIFO	後入れ先出し
キュー	FIFO	先入れ先出し

17. ENQUEUEとは

キューへデータを追加する操作を**ENQUEUE（エンキュー）**と呼びます。

例えば、

A → B → C

というキューへDを追加すると、

A → B → C → D

となります。

つまり、

ENQUEUE = キューの末尾へデータを追加する

操作です。

18. DEQUEUEとは

キューからデータを取り出す操作を**DEQUEUE（デキュー）**と呼びます。

例えば、

A → B → C → D

からDEQUEUEすると、

Aを取り出す

ので、

B → C → D

が残ります。

つまり、

DEQUEUE = キューの先頭からデータを取り出す

操作です。

19. キューの先頭と末尾

キューでは、データを取り出す側と追加する側が異なります。

取り出す                        追加
   ↓                             ↓
 FRONT                         REAR
   ↓                             ↓
 [A] → [B] → [C] → [D]

一般的に、

FRONT

はデータを取り出す側、

REAR

はデータを追加する側を表します。

FRONT
→ DEQUEUE

REAR
→ ENQUEUE

と考えると分かりやすいです。

20. ENQUEUEとDEQUEUE

例えば空のキューに、

ENQUEUE A
ENQUEUE B
ENQUEUE C

を行うと、

FRONT           REAR
 ↓               ↓
[A] → [B] → [C]

となります。

ここで、

DEQUEUE

するとAが取り出され、

FRONT      REAR
 ↓          ↓
[B] → [C]

となります。

21. 配列でキューを作るとどうなる？

配列を使ってキューを実装することもできます。

例えば、

0   1   2   3   4
┌───┬───┬───┬───┬───┐
│ A │ B │ C │   │   │
└───┴───┴───┴───┴───┘
  ↑       ↑
FRONT    REAR

とします。

AをDEQUEUEすると、

0   1   2   3   4
┌───┬───┬───┬───┬───┐
│   │ B │ C │   │   │
└───┴───┴───┴───┴───┘
      ↑   ↑
   FRONT REAR

となります。

22. 配列の先頭が余ってしまう

その後、

ENQUEUE D
ENQUEUE E

すると、

0   1   2   3   4
┌───┬───┬───┬───┬───┐
│   │ B │ C │ D │ E │
└───┴───┴───┴───┴───┘
      ↑           ↑
   FRONT         REAR

となります。

ここで問題があります。

配列の最後まで使っていますが、

位置0

は空いています。

このまま一方向にだけ進めると、空いている領域をうまく再利用できません。

そこで登場するのが循環キューです。

23. 循環キューとは

**循環キュー（Circular Queue）**とは、

配列の最後と最初がつながっているものとして扱うキュー

です。

イメージとしては、

0 → 1 → 2 → 3 → 4
↑               ↓
└───────────────┘

となります。

最後の位置まで進んだら、

4
↓
0

へ戻ります。

これによって、DEQUEUEによって空いた領域を再利用できます。

24. 循環キューの動き

例えば、

0   1   2   3   4
┌───┬───┬───┬───┬───┐
│   │ B │ C │ D │ E │
└───┴───┴───┴───┴───┘

という状態で位置0が空いているとします。

次にFを追加すると、

0   1   2   3   4
┌───┬───┬───┬───┬───┐
│ F │ B │ C │ D │ E │
└───┴───┴───┴───┴───┘

のように先頭へ戻って格納できます。

見た目は配列ですが、論理的には、

B → C → D → E → F

というキューです。

25. 剰余を使った循環

循環キューでは、配列の最後から最初へ戻すために**剰余（mod）**を利用することがあります。

配列サイズを5とすると、

次の位置
=
(現在位置 + 1) mod 5

とできます。

例えば現在位置が4なら、

(4 + 1) mod 5
=
5 mod 5
=
0

なので、

4 → 0

と先頭へ戻れます。

これは循環バッファなどでも利用される重要な考え方です。

26. キューはどこで使われる？

キューは、

先に来た処理から順番に処理する

ような場面で利用されます。

例えば、

印刷要求A
↓
印刷要求B
↓
印刷要求C

という印刷要求が来た場合、

A
↓
B
↓
C

の順番で処理することができます。

このような待ち行列を管理する場面でキューが利用されます。

27. バッファとキュー

データを一時的に保存するバッファでも、キューの考え方が利用されることがあります。

例えば、

送信側
↓
[A][B][C]
↓
受信側

というデータがあれば、

A
↓
B
↓
C

と到着した順番に処理できます。

特に循環キューは、一定サイズの領域を繰り返し利用するリングバッファなどと相性がよい構造です。

28. スタックとキューをリストで実装する

前回学んだ連結リストを利用して、スタックやキューを実装することもできます。

例えばスタックなら、

TOP
 ↓
[C] → [B] → [A] → NULL

として、先頭へデータを追加・削除すれば、

PUSH
POP

を実現できます。

キューなら、

FRONT                 REAR
 ↓                      ↓
[A] → [B] → [C] → [D] → NULL

のように管理できます。

つまり、

リスト・スタック・キューは別々の知識ではなく、組み合わせて実装できる

ということです。

29. スタックとキューの操作問題

応用情報では、操作の順番から「何が取り出されるか」を考える問題があります。

例えばスタックに、

PUSH A
PUSH B
POP
PUSH C
POP

を行います。

順番に追うと、

PUSH A
[A]

PUSH B
[B]
[A]

POP
→ B

PUSH C
[C]
[A]

POP
→ C

したがって、取り出される順番は、

B → C

です。

30. キューの場合

同じように、

ENQUEUE A
ENQUEUE B
DEQUEUE
ENQUEUE C
DEQUEUE

とします。

順番に追うと、

ENQUEUE A
[A]

ENQUEUE B
[A][B]

DEQUEUE
→ A

ENQUEUE C
[B][C]

DEQUEUE
→ B

となります。

取り出される順番は、

A → B

です。

31. スタックとキューを見分ける

問題文で、

最後に格納したデータから取り出す

とあれば、

スタック

です。

最初に格納したデータから取り出す

とあれば、

キュー

です。

また、

LIFO
PUSH
POP

が出てきたらスタック、

FIFO
ENQUEUE
DEQUEUE
FRONT
REAR

が出てきたらキュー、

と関連付けて覚えておくと判断しやすくなります。

32. 全体を整理しよう

ここまでの関係を整理します。

データ構造
│
├─ リスト
│
├─ スタック
│   ├─ LIFO
│   ├─ PUSH
│   └─ POP
│
└─ キュー
    ├─ FIFO
    ├─ ENQUEUE
    ├─ DEQUEUE
    └─ 循環キュー

スタックとキューは、

データをどの順番で追加し、どの順番で取り出すか

というルールを持ったデータ構造です。

33. 応用情報で押さえたいポイント

まず絶対に混同しないようにしたいのが、

スタック
=
LIFO
=
後入れ先出し

と、

キュー
=
FIFO
=
先入れ先出し

です。

さらに操作名は、

スタック
PUSH → 入れる
POP  → 取り出す

キュー
ENQUEUE → 入れる
DEQUEUE → 取り出す

です。

循環キューでは、

配列の最後
↓
配列の先頭

へ戻ることで領域を再利用します。

そして実際のプログラムでは、

スタック
→ 関数呼出し
→ 再帰
→ 式の評価

キュー
→ 待ち行列
→ バッファ
→ 順番待ち処理

などに利用されます。

34. まとめ

スタックとキューは、どちらも複数のデータを管理するためのデータ構造です。

しかし、取り出す順番が異なります。

項目	スタック	キュー
方式	LIFO	FIFO
日本語	後入れ先出し	先入れ先出し
追加	PUSH	ENQUEUE
取出し	POP	DEQUEUE
主な位置	TOP	FRONT / REAR
用途例	関数呼出し・再帰	待ち行列・バッファ

この記事で覚えること

スタックはLIFO（後入れ先出し）
キューはFIFO（先入れ先出し）
PUSHはスタックへの追加
POPはスタックからの取出し
ENQUEUEはキューへの追加
DEQUEUEはキューからの取出し
スタックポインタはスタックの位置管理に使われる
空のスタックから取り出そうとするとアンダーフローになる
容量を超えて追加するとオーバーフローになる
循環キューでは配列の最後から先頭へ戻って領域を再利用する
スタックは関数呼出しや再帰処理などで利用される
キューは待ち行列やバッファなどで利用される
連結リストを使ってスタックやキューを実装することもできる

🍯 はちみつメモ

スタックは「積み重ねた本」なので最後に置いた本から取る。キューは「レジの行列」なので最初に並んだ人から進む。LIFOとFIFOをこのイメージで分ければ迷いにくい。