基本情報技術者 2012年春期午前（科目A）問06

問題文

十分な大きさの配列Aと初期値が0の変数pに対して、関数f(x)とg()が次のとおり定義されている。配列Aと変数pは、関数f(x)とg()だけでアクセス可能である。これらの関数が操作するデータ構造はどれか。

function f(x) { 　　p = p+1; 　　A[p] = x; 　　return None; }

function g() { 　　x = A[p]; 　　p = p-1; 　　return x; }

🖊️ 解答を隠して解いてみる

選択肢

ア：キュー

イ：スタック（正解）

ウ：ハッシュ

エ：ヒープ

🔒 解説は解答すると表示されます

スタック操作の実装【午前解説】

正解の理由

与えられたコードの動作を命令語で表すと次の通りです。f は「位置を一つ進めて値を格納する（push）」、g は「現在位置の値を取り出して位置を一つ戻す（pop）」です。これはまさにスタックの基本操作である push と pop に対応します。したがってデータ構造はスタック（LIFO）です。選択肢の中でこれに該当するのはイです。

解法ステップ

f(x) の中身を見る：p = p+1; A[p] = x; → ポインタを進めてから格納している。
g() の中身を見る：x = A[p]; p = p-1; → 現在の位置から取り出し、ポインタを戻している。
上記は「最後に追加した要素を最初に取り出す」動作と一致するかを検討する。
「最後に追加した要素を最初に取り出す」＝ LIFO（スタック）であると判断する。
他の候補（キュー、ハッシュ、ヒープ）と比較し、操作の一致性で除外する。

選択肢別の誤答解説

ア: キュー
- 誤り。キューは FIFO（先に入れたものを先に出す）で、追加（enqueue）と取り出し（dequeue）が前後で分かれます。提示コードは直近の追加要素を取り出すため一致しません。
イ: スタック
- 正解。f が push、g が pop に対応し、LIFO の性質そのものです。
ウ: ハッシュ
- 誤り。ハッシュはキーと値の対応関係を保持しキーで直接参照する構造で、単純な順序付きの push/pop 操作とは無関係です。
エ: ヒープ
- 誤り。ヒープ（優先度付きキュー）は要素間の優先度比較に基づく取り出しを行い、単純に最後に追加したものを取り出す動作とは異なります。

よくある誤解

「追加と取り出しがあるからキューだ」と誤解する受験者が多いです。キューは先入れ先出し（FIFO）で、取り出す要素が追加順と異なります。
インクリメント／デクリメントの位置（前置か後置か）を見落として push/pop の順序を逆に考えてしまうことがあります。コードの順序に注意してください。
p の初期値や配列のインデックス基準（0-based/1-based）を無視して考えてしまい、実装上のオフバイワンで混乱することがあります。

補足コラム

配列 A とポインタ p でスタックを実装する典型的な方法がこのコードです。計算量は push/pop ともに O(1) で高速ですが、オーバーフロー（配列の上限）とアンダーフロー（空のスタックからの pop）に注意が必要です。p の初期値とインクリメントのタイミングにより配列の何番目を使うかが変わるため、実装規約（0 ベースか 1 ベースか）を統一すると安全です。

例：Python で同様な動作を示す簡単な実装

# 単純な配列ベースのスタック（p 初期値 0、最初の push は index 1）
A = [None] * 100
p = 0

def f(x):
    global p
    p = p + 1
    A[p] = x

def g():
    global p
    x = A[p]
    p = p - 1
    return x

# 使い方
f(10)
f(20)
print(g())  # 20
print(g())  # 10

FAQ

Q1: p の初期値が 0 なのに最初の格納が A[1] になるのはおかしくないですか？
A1: コードでは p を先にインクリメントしてから格納しているため最初の格納は A[1] になります。実装によっては p を -1 で初期化し、先にインクリメントする方法もあります。重要なのは操作の順序（increment → store, read → decrement）です。

Q2: g() が先に p をデクリメントしてから A[p] を参照していたらどうなりますか？
A2: もし g() が p = p-1 の後に x = A[p] であれば、それは pop のインデックス扱いが変わり、実装によっては p の初期値やオフバイワンの扱いを調整する必要があります。しかし基本的な LIFO の考え方（最後に入れたものを取り出す）は変わりません。

Q3: このコードは本当にスタック以外のどれにも当てはまりませんか？
A3: はい。キューやハッシュ、ヒープはいずれもここで定義された単純なインクリメント格納／読み出しパターンとは根本的に異なる振る舞いを持ちます。

関連キーワード: スタック、LIFO、push、pop、配列実装、ポインタ、オフバイワン、データ構造