スタックとキューの操作とデータ構造：LIFO・FIFOと逆ポーランド記法の実戦トレース術

A、B、Cの順に入れたデータは、どの順に取り出されるでしょうか？

スタックならC、B、A。キューならA、B、Cです。出し入れの順番を起点に、リングバッファと逆ポーランド記法を追ってみましょう。

スタックとキューの決定的な違い：LIFO vs FIFO

スタックとキューは、「データの出し入れのルール（順序）」が正反対です。

スタック（LIFO）の仕組みと操作トレース

スタックは、片側（Top: 頂上）からしかデータの出入りができない筒のような構造です。

1. Push（プッシュ）

   スタックの頂上に新しいデータを1つ追加する。

2. Pop（ポップ）

   スタックの頂上にある最新のデータを1つ取り出して削除する。

3. Top（または Peek）

   頂上にあるデータを削除せずに参照する。

このスタックは添字1から開始し、topは要素数も表します。top＝0が空、要素の格納範囲はS[1]〜S[容量]です。Push前に満杯、Pop前に空を確認します。

// Push 操作（データ x を格納）
top ← top + 1
S[top] ← x

// Pop 操作（頂上のデータを取り出し）
val ← S[top]
top ← top - 1
return val

【注意すべき境界エラー】：スタックの容量上限を超えて Push しようとすると「スタックオーバーフロー（Stack Overflow）」、空のスタックから Pop しようとすると「スタックアンダーフロー（Stack Underflow）」が発生します。

キュー（FIFO）と配列によるリングバッファ実装

キューは、一方の端（Rear / Tail: 末尾）からデータを追加し、もう一方の端（Front / Head: 先頭）からデータを取り出す構造です。

配列でキューを作るときの「移動コスト問題」と「リングバッファ」

配列の先頭を取り出すたびに残りの要素を前へ詰める実装では、1回のDequeueがO(n)になります。リングバッファでは位置を表す添字を動かし、要素の移動を避けます。

リングバッファでは、配列のサイズを MAX_SIZE としたとき、ポインタの移動に「剰余演算（% または mod）」を使用します。

// 添字は0始まり。front=rear=count=0、容量をMAX_SIZEとする
// Enqueue：count < MAX_SIZE を確認して実行
Q[rear] ← data
rear ← (rear + 1) mod MAX_SIZE
count ← count + 1

// Dequeue：count > 0 を確認して実行
data ← Q[front]
front ← (front + 1) mod MAX_SIZE
count ← count - 1
return data

このように (pointer + 1) % MAX_SIZE とすることで、ポインタが配列の末尾（インデックス MAX_SIZE - 1）に達したとき、次の値が自動的に 0 にループし、配列の要素を一切動かさずに O(1) で高速にキューを運用できます。

スタックの実戦応用：逆ポーランド記法の計算トレース

試験でスタックの活用例として最もよく出題されるのが「逆ポーランド記法（後置表記法：Reverse Polish Notation / RPN）」です。

私たちが普段使う中置記法 (3 + 4) × 2 では括弧が必要ですが、逆ポーランド記法では 3 4 + 2 × のように演算子を数字の後ろに置くことで、括弧を一切使わずに計算順序を一意に表現できます。

逆ポーランド記法をスタックで解く黄金ルール

1. 左から順にトークン（数値または演算子）を1つずつ読む。

2. 「数値」が来たら、スタックに Push する。

3. 「演算子（+ - * /）」が来たら、スタックから数値を 2 つ Pop し、計算した結果を再びスタックに Push する。（※引き算や割り算では、先に取り出した値が右辺、後から取り出した値が左辺になる点に注意！）

4. 式の末尾まで読み終えたとき、スタックに唯一残っている値が最終計算結果となる。

実戦トレース式「5 3 2 + * 4 -」の計算過程

手元にスタックの箱を書き、数値を積んで演算子で畳み込んでいくだけで、どんなに長い式でも迷わず解くことができます。

実戦演習：リングバッファの擬似言語穴埋め問題

以下のプログラムは、要素数 5 の配列 Q（添字は 0 から 4）を用いてリングバッファ形式のキューを実装したものです。要素を追加する関数 Enqueue の空欄に入る適切な式を考えてみましょう。

○定数: MAX_SIZE ← 5
○整数型の配列: Q[MAX_SIZE]
○整数型: front ← 0, rear ← 0, count ← 0

○論理型: Enqueue(整数型: item)
  if (count = MAX_SIZE) then
    return false  // キューが満杯
  endif

  Q[rear] ← item
  rear ← 【   a   】
  count ← count + 1
  return true

○整数型: Dequeue()
  整数型: item
  if (count = 0) then
    return -1     // キューが空
  endif

  item ← Q[front]
  front ← 【   b   】
  count ← count - 1
  return item

空欄aの選択肢（空欄bは式を考える）

1. ア

   rear + 1

2. イ

   (rear + 1) % MAX_SIZE

3. ウ

   (rear + 1) / MAX_SIZE

4. エ

   rear - 1

解説と解答

正解：空欄 a ＝ イ（(rear + 1) % MAX_SIZE）、空欄 b ＝ (front + 1) % MAX_SIZE

• 着眼点：配列のサイズが MAX_SIZE (5) であるため、インデックスは 0, 1, 2, 3, 4 です。インデックスが 4 のときに単に +1 すると 5 となり配列外参照エラーが発生します。

• (4＋1) mod 5＝0で先頭へ戻ります。aはイ、bは(front＋1) mod MAX_SIZEです。bはfrontを更新するため、rearを使う選択肢イをそのまま入れてはいけません。

空と満杯、戻り値の区別

frontとrearが同じ位置になるのは、空のときだけではありません。この実装ではcount＝0を空、count＝容量を満杯と判定します。

演習のDequeueは空なら−1を返します。格納値を0以上に限定する前提なら区別できます。−1も格納する場合は、成功・失敗の状態と取り出した値を別々に返す必要があります。

スタック例は1始まり、リングバッファ例は0始まりです。記事内でも、コードごとの添字規約を確認して追います。

まとめ：スタックとキューの試験対策チェックシート

スタックとキューの問題が出題されたら、以下のポイントを即座に確認しましょう。

1. 問題が「スタック（LIFO）」か「キュー（FIFO）」かを確認する。

2. 配列のインデックス管理（リングバッファの剰余計算 % やスタックポインタの増減）を把握する。

3. 逆ポーランド記法が出たら、即座にメモ用紙にスタックの縦枠を書き、数値を下から積み上げる。

4. 空（Underflow）や満杯（Overflow）の判定条件を見落とさない。

データ構造の特性を理解して手元でトレースできるようになれば、科目Bアルゴリズム問題の得点力は一気に跳ね上がります！

出典と仕様を確認する

IPA：FEシラバス Ver.9.2

IPA：試験で使用する用語・プログラム言語 Ver.5.1

Open Data Structures：配列によるスタック・キュー