三つのスタックA，B，Cのいずれの初期状態も[1, 2, 3]であるとき，再帰的に定義された関数f( )を呼び出して終了した後のBの状態はどれか。
ここで，スタックが[a_1, a_2, …, a_(n-1)]の状態のときにa_nをpushした後のスタックの状態は[a_1, a_2, …, a_(n-1), a_n]で表す。
f(){
Aが空ならば{
何もしない。
}
そうでない場合{
Aからpopした値をCにpushする。
f()を呼び出す。
Cからpopした値をBにpushする。
}
}
正答1
解説
正解は1です。
再帰呼出しで、呼び出す前の処理と、戻ってからの処理の順序をたどる問題です。
f()は、Aからpopした値をCへpushし、自分自身を呼び出し、戻ってからCからpopした値をBへpushします。
スタックは、後に入れたものから先に取り出されます（LIFO：Last In First Out）。
【処理の流れ】
1回目の呼出しで、Aから3をpopしてCにpushし、Cは[1, 2, 3, 3]になります。
2回目の呼出しで、Aから2をpopしてCにpushし、Cは[1, 2, 3, 3, 2]になります。
3回目の呼出しで、Aから1をpopしてCにpushし、Cは[1, 2, 3, 3, 2, 1]になります。
4回目の呼出しでは、Aが空なので何もせずに戻ります。
3回目の処理に戻り、Cから1をpopしてBにpushし、Bは[1, 2, 3, 1]になります。
2回目の処理に戻り、Cから2をpopしてBにpushし、Bは[1, 2, 3, 1, 2]になります。
1回目の処理に戻り、Cから3をpopしてBにpushし、Bは[1, 2, 3, 1, 2, 3]になります。
【選択肢別解説】
1：○ 上のとおり、Bの末尾には1、2、3の順に追加され、[1, 2, 3, 1, 2, 3]になります。
2：× [1, 2, 3, 3, 2, 1]は、Aの値をすべてCに移し終えた時点のCの並びです。
Cから取り出す順序は逆になるため、Bはこの並びになりません。
3：× Bの初期状態の[1, 2, 3]は変わらず、追加分は末尾に積まれます。
先頭側が[3, 2, 1]に変わることはありません。
4：× 選択肢3と同じく先頭側が変わることはありません。
また、追加される順序も3、2、1ではなく1、2、3です。
【ポイント】
AからCへ移すと順序が逆になり、CからBへ移すと再び逆になって元の順序に戻ります。
スタックを2回経由すると順序が保存されると覚えておくと便利です。