基本情報技術者 2014年 春期 午前（科目A） 問07
問題文
空の状態のキューとスタックの二つのデータ構造がある。次の手続きを順に実行した場合、変数xに代入されるデータはどれか。ここで、手続で引用している関数は、次のとおりとする。
〔関数の定義〕
push(y):データyをスタックに積む。
pop():データをスタックから取り出して、その値を返す。
enq(y):データyをキューに挿入する。
deq():データをキューから取り出して、その値を返す。
〔手続〕
push(a)
push(b)
enq(pop())
enq(c)
push(d)
push(deq())
x ← pop()
選択肢
ア：a
イ：b（正解）
ウ：c
エ：d
🔒 解説は解答すると表示されます
スタックとキューの操作順序【午前解説】
正解の理由
正解: イ（b）
手続きを順に実行すると、pop() やdeq() はその時点でのデータ構造から値を取り出してからenqまたはpushが行われます。具体的に操作を追うと、最終のpop() が取り出す値はbであることが明らかです。
手続きを順に実行すると、pop() やdeq() はその時点でのデータ構造から値を取り出してからenqまたはpushが行われます。具体的に操作を追うと、最終のpop() が取り出す値はbであることが明らかです。
解法ステップ
- 初期状態：スタックS = []、キューQ = []
- push(a) → S = [a]（aが下、上は右）
- push(b) → S = [a, b]（bが最上位）
- enq(pop()) → pop() でbを取り出し、S = [a]、enq(b) によりQ = [b]
- enq(c) → Q = [b, c]（bが先頭）
- push(d) → S = [a, d]（dが最上位）
- push(deq()) → deq() によりQの先頭bを取り出しQ = [c]、その値bをpushしてS = [a, d, b]（bが最上位）
- x ← pop() → S から最上位 b を取り出し x = b（これが答え）
選択肢別の誤答解説
- ア: a — 初期にpushされたaはその後にbやd、さらにpushされた値により下に残り、最終popでは取り出されません。
- イ: b — 正解。手順どおり評価すると最終のpopがbを取り出します。
- ウ: c — cはキューの後ろにenqされたまま残り、最後のpop（スタックから）は関係ありません。
- エ: d — dはスタックにpushされたが、その上にbがさらにpushされているため、最後のpopではdではなくbが取り出されます。
よくある誤解
- 「enq(pop()) はenqの後にpopを実行する」と誤解して順序を逆に考えてしまう。実際はpopが先に評価されます。
- スタックとキューの順序（LIFOとFIFO）を混同して、どの要素が先に出るかを取り違えやすい。
- push(deq()) を「deq() の結果はpushの直前に入るが、元のキュー順序を壊さない」と誤解して中間状態を見落とす。
補足コラム
- スタック（push/pop）はLIFO（後入れ先出し）、キュー（enq/deq）はFIFO（先入れ先出し）です。入れ子の呼び出し（例：enq(pop())）は内側の処理が先に行われるため、評価順を正しく把握することが重要です。
- 実務ではこのような構成を使って一時的なデータ移動や順序転換を行います。スタックは再帰や式評価、キューはジョブスケジューリングに多用されます。
FAQ
Q1: enq(pop()) と書かれているとき、popは本当に先に実行されますか？
A1: はい。関数呼び出しの引数評価として内側（pop）が先に評価され、その結果がenqの引数になります。
A1: はい。関数呼び出しの引数評価として内側（pop）が先に評価され、その結果がenqの引数になります。
Q2: push(deq()) の場合、deqが空だとどうなりますか？
A2: 問題文に明示がない場合は未定義動作またはエラー扱いですが、試験問題では空にならないような設問構成になっていることが多いです。
A2: 問題文に明示がない場合は未定義動作またはエラー扱いですが、試験問題では空にならないような設問構成になっていることが多いです。
Q3: 表記上スタックの上側はどちらに描けば分かりやすいですか？
A3: 左右どちらでも構いませんが、右端を「上」と決めておくと順序の追跡がしやすいです（本解説も右端を上としています）。
A3: 左右どちらでも構いませんが、右端を「上」と決めておくと順序の追跡がしやすいです（本解説も右端を上としています）。
関連キーワード: キュー、スタック、LIFO、FIFO、push、pop、enq、deq、データ構造、評価順序
\ せっかくなら /
基本情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！