基本情報技術者試験「スタック・キュー」の問題
1, 2, 3, 4 をこの順に push できるスタックがある。push と pop は任意の順序で混在してよいが、push は必ず 1→2→3→4 の順に行う。次の手続 canPop は、与えられた取り出し希望列 want が実際に pop で実現できるかを判定する。want = {3, 2, 4, 1}（要素数 4、添字は 1 から）を与えて実行したとき、戻り値はどれか。next は次に push すべき値（初期 1、push のたびに +1）を表す。
○論理型: canPop(整数型の配列: want)
スタック: stk // 空で開始
整数型: next ← 1
整数型: i
for (i を 1 から wantの要素数 まで 1 ずつ増やす)
while ((stk が空 または stk.top が want[i] と等しくない) and next ≦ 4)
stk.push(next)
next ← next + 1
endwhile
if (stk が空でない and stk.top が want[i] と等しい)
stk.pop()
else
return false
endif
endfor
return trueアtrue（実現可能な系列）
イfalse
ウtrue だが要素が残留する系列
エnext 超過でエラー停止する
正解
ア．true（実現可能な系列）
want[i] を取り出すために必要な値まで push し、頂上が一致したら pop する。3→2→4→1 は 1,2,3 を積んで 3,2 を出し、4 を積んで 4,1 を出す手順で完全に実現できるため true となり、アが正しい。
?選択肢ごとの解説
ア ○want[i] を取り出すために必要な値まで push し、頂上が一致したら pop する。3→2→4→1 は 1,2,3 を積んで 3,2 を出し、4 を積んで 4,1 を出す手順で完全に実現できるため true となり、アが正しい。
イ ×3,2,4,1 を実現不能と誤認した判定だが、上記手順で全要素が pop でき false にはならない。
ウ ×全要素を取り出すとスタックは空になり残留は生じないため、残留ありとするのは誤りである。
エ ×next は最大 4 まで push され 5 以上は積まないため、next 超過によるエラーは起きない。
✎くわしく
スタックで実現可能な順列は『先に出した大きい値の下に残した小さい値を、後から飛び越えて取り出すことはできない』という制約に従う。本列はその禁止パターンを含まないため実現可能である。
✓本番での押さえどころ
試験のコツ
希望値ごとに『そこまで push してから頂上一致を pop』を実際に試し、頂上不一致で詰まったら false と判断する。
覚え方
『あとから来た小さい数を、先に出した大きい数の下から救い出せない』とスタックの制約を覚える。
よくある誤り
FIFO（キュー）の感覚で先頭から順に取れると考え、実現可能性の制約を見落とすミスが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-b-algo-0099