この問題の解説と、これまでの解答の記録です。
後に入れたデータが先に取り出されるデータ構造 (以下, スタックという) がある。これを用いて, 図に示すような, 右側から入力されたデータの順番を変化させて, 左側に出力する装置を考える。この装置に対する操作は次の3通りである。 ① 右側から入力されたデータをそのまま左側に出力する。 ② 右側から入力されたデータをスタックの1番上に積み上げる。 ③ スタックの1番上にあるデータを取り出して左側に出力する。 この装置の右側から順番にデータ A, B, C, D を入力した場合に, この①～③の操作を組み合わせても, 左側に出力できない順番はどれか。
「B, A, D, C」は作れる。A を積み B を積んで B→A の順に取り出し (B, A)、次に C を積み D を積んで D→C の順に取り出せば (D, C)、B, A, D, C が得られる。出力できるのでこれは正解ではない。
「B, D, C, A」は作れる。A を積み B を積んで B を取り出し (B)、C を積み D を積んで D→C の順に取り出し (D, C)、最後に残った A を取り出せば (A)、B, D, C, A が得られる。出力できるのでこれは正解ではない。
「C, B, D, A」は作れる。A・B・C を順に積んで C→B の順に取り出し (C, B)、次に D を積んで取り出し (D)、最後に残った A を取り出せば (A)、C, B, D, A が得られる。出力できるのでこれは正解ではない。
正解 スタックは「後入れ先出し (LIFO)」で、後から積んだデータほど先に取り出される。データは右から A→B→C→D の順に届き、各データについて『そのまま出力 (①)』『積む (②)』『取り出して出力 (③)』を選べる。選択肢エ「C, D, A, B」を作ろうとすると、まず C を出すために A・B を積んでから C を積んで取り出す必要があり、この時点でスタックには下から A・B が残り、B が一番上になる。次に D を積んで取り出し D を出力できるが、続いて A を出そうとしても A は B の下に埋まっており、B を取り出さない限り A は取り出せない。つまり A より先に必ず B が出てしまうため、A が B より先に来る「A, B」で終わる順番は作れない。よってエは出力できない順番であり、これが正解。