基本情報技術者試験「スタック・キュー」の問題
値スタック valStk と最大値スタック maxStk の 2 本を使い、push 時に「これまでの最大値」も同時に積むことで、頂上の最大値を即座に参照できるスタックを作る。push(x) では valStk に x を積み、maxStk には「x と現在の maxStk.top のうち大きい方（maxStk が空なら x）」を積む。pop は両スタックの頂上を同時に取り出す。空の状態から次を実行したとき、最後に maxStk.top が返す値（現在の最大値）はどれか。
○手続: run() push(40) push(90) push(60) pop() push(20) getMax() // maxStk.top を返す
ア110（90と20の和とする誤り）
イ90（現在の最大値）
ウ60
エ40
正解
イ．90（現在の最大値）
maxStk は各時点の最大値を保持する。60 を pop すると maxStk も縮んで頂上は 90 になり、20 を push しても max(20,90)=90 が積まれる。最終 maxStk.top=90 となるため イが正しい。
?選択肢ごとの解説
ア ×最大値を求めるべきところを最後に積んだ 20 と頂上の 90 を加算して 110 とした、max を和と取り違えた誤りである。
イ ○maxStk は各時点の最大値を保持する。60 を pop すると maxStk も縮んで頂上は 90 になり、20 を push しても max(20,90)=90 が積まれる。最終 maxStk.top=90 となるため イが正しい。
ウ ×pop した値 60 がまだ最大として残っていると誤認した、pop で maxStk も同時に縮む点を見落とした誤りである。
エ ×最初に push した底の値 40 を最大値とした、後続の 90 で最大が更新される点を見落とした誤りである。
✎くわしく
最大値追跡スタックは、各 push 時点の『その時の最大値』を別スタックに同期して積むことで、pop しても 1 つ前の最大値へ正しく巻き戻せる。max を 1 変数で持つと pop 時に過去の最大へ戻せない点が、補助スタックを使う理由である。
✓本番での押さえどころ
試験のコツ
valStk と maxStk を 2 列で並べ、push/pop を必ず両方同時に更新して頂上を読む。
覚え方
『値の隣に、その時点の最大も置いておく』とペア記録を覚える。
よくある誤り
max を単一変数で保持し、最大値の要素を pop した後に過去の最大へ戻せないミスが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 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-0103