アルゴリズムとプログラミング
平成22年度 秋期 基本情報技術者試験 午前 問5
A，B，C，D の順に到着するデータに対して，一つのスタックだけを用いて出力可能なデータ列はどれか。
答えを選ぶ
出典：平成22年度 秋期 基本情報技術者試験 午前 問5（問題文は IPA の公開問題。解説は当サイト作成）
答えと解説を見る
正解：ウ
覚える知識
スタックで出力可能なデータ列の判定
スタックは後入れ先出し(LIFO)のデータ構造で、入力順が決まっていても途中でpopを挟むことで出力順が変わるが、全ての順列が出せるわけではない。
この問題で必要なこと
スタックは後入れ先出しなので、A,B,C,Dの順に入れる条件下で、各選択肢の出力順をpush/popで再現できるかを検証する。C,B,D,AはA,B,Cをpush後にC,Bをpop、Dをpush・pop、最後にAをpopで可能。
ひっかけ
キューのようにFIFOで考えたり、取り出せない順列(A,D,B,Cなど)を可能と誤認させる。
この知識の出題：本試験系 2 回・免除試験 6 回（公開問題での観測値）