アルゴリズムとプログラミング
基本情報技術者試験｜値スタック valStk と最大値スタック maxStk の 2 本を使い、push…
値スタック 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 で最大が更新される点を見落とした誤りである。
アルゴリズムとプログラミングの他の問題
空のスタックに対し、文字 'P' は次の数を push する操作、文字 'o' は pop…印刷ジョブを先着順（FIFO）で処理するキュー q がある。各ジョブは (id, ページ数) を持ち、deq…次の擬似言語は、文字列 s を左から走査し、スタック頂上と同じ文字が来たら頂上を pop して両者を消し、異なれば…容量 4 の循環キュー（リングバッファ）を配列 buf[1..4] で実装する。head は次に取り出す位置、tail…同じ入力列 1, 2, 3, 4 を、(A) スタック（push 後にすべて pop）と (B) キュー（enqueue…スタックに対する push（積む）と…キューに対する enqueue（末尾に追加）と…次の擬似言語は、スタックを用いて文字列中の丸括弧の対応が正しいかを調べ、正しければ "OK"、誤っていれば "NG"…
この問題の「深掘り・誤答の完全解説・覚え方」は、登録すると読めます。
基本情報技術者試験は全4,036問。公開しているのはその一部で、登録すると残りも一問ごとにAI解説つきで解けます。SRS暗記カード・全真模試・弱点診断まで。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
作成・校閲：ukamiru編集部 · 基本情報技術者試験 過去問 · fe-b-algo-0103