平成24年度 秋期 午前 問5

✓ これが正解イ3

解説

最後尾を残し、前の三つだけをスタックへ移せば足ります。

キューは先に入れたものから出る入れ物で、スタックは後に入れたものから出る入れ物です。並びを逆さまにする働きをもつのはスタックのほうなので、この並べ替えはスタックが引き受けます。軸は一つで、何個を預ければ目的の並びに届くかを数えることです。もともと最後尾にいるものは、そのままキューに残しておけば新しい並びの先頭になります。ですから動かす必要があるのは、その前にいる三つだけです。実際に追うと、先頭から三つを順にスタックへ入れると、キューには最後の一つだけが残ります。この状態でスタックから三つを取り出してキューの末尾に加えると、残っていた一つを先頭にして、預けた三つが入れた順と逆に並びます。

ほかの選択肢はなぜ違うのか

• ア2：二つだけ預けると、キューには三つ目と四つ目が元の順のまま残ります。預けた分を戻しても先頭に来るのは三つ目なので、狙った並びには届きません。
• ウ4：四つとも預ければ並べ替えそのものは成り立ちますが、もともと最後尾にいるものは動かさなくてよいので、最小の回数を問う答えにはなりません。
• エ5：五回も動かす必要はありません。一度戻したものをもう一度預けることになり、手数が増えるだけです。三つ預けた時点で並べ替えは完成しています。