この問題の解説と、これまでの解答の記録です。
下から上へデータを積み上げ，上にあるデータから順に取り出すデータ構造（以下，スタックという）がある。これを用いて，図に示すような，右側から入力されたデータの順番を変化させて，左側に出力する装置を考える。この装置に対する操作は次の3通りである。 ① 右側から入力されたデータをそのまま左側に出力する。 ② 右側から入力されたデータをスタックに積み上げる。 ③ スタックの1番上にあるデータを取り出して左側に出力する。 この装置の右側から順番に X，Y，Z を入力した場合に，この①～③の操作を組み合わせても，左側に出力できない順番はどれか。
「X, Z, Y」は実現できるので、出力できない順番ではない。X を①でそのまま出力 → Y を②でスタックに積む → Z を①でそのまま出力 → ③でスタックの Y を取り出して出力、で X, Z, Y になる。
「Y, Z, X」は実現できるので、出力できない順番ではない。X を②でスタックに積む → Y を①でそのまま出力 → Z を①でそのまま出力 → ③で X を取り出して出力、で Y, Z, X になる。
正解 正解は ウ「Z, X, Y」。Z を最初に左へ出すには、先に入力された X と Y をどちらも②でスタックに積んでおくしかない。入力順は X→Y→Z なので、スタックは下から X、その上に Y の状態になる。ここで Z は入力された瞬間に①でそのまま左へ出せる。しかし残った X と Y は③でスタックの1番上から取り出すことしかできず、上にある Y が先、下にある X が後になる。つまり Z の次に出せるのは必ず Y であり、「Z の次に X」という順番は作れない。したがって①～③をどう組み合わせても出力できない順番は ウ。
「Z, Y, X」は実現できるので、出力できない順番ではない。X を②で積む → Y を②で積む（下から X, Y）→ Z を①でそのまま出力 → ③で Y → ③で X、で Z, Y, X になる。入力順をそのまま逆順にするのはスタックが最も得意な動きである。