問６
三つのスタックＡ、Ｂ、Ｃのいずれの初期状態も [1、2、3] であるとき、再帰的に定義された関数 f()を呼び出して終了した後のＢの状態はどれか。ここで、スタックが
[ａ1、ａ2、...、ａn-1] の状態のときにａnをpushした後のスタックの状態は [ａ1、ａ2、...、ａn-1、ａn]で表す。
f(){
Ａが空ならば{
何もしない。
｝
そうでない場合{
Ａからpopした値をＣにpushする。
f()を呼び出す。
Cからpopした値をＢにpushする。
｝
｝
ア [1、2、3、1、2、3]
イ [1、2、3、3、2、1]
ウ [3、2、1、1、2、3]
エ [3、2、1、3、2、1]
正解
ア
解説
スタックはLIFO (後入れ先出し) により置換するアルゴリズムである。
popはスタックからデータを取り出す操作、pushはスタックにデータを入れる操作である。
三つのスタックは以下のように遷移していく。
０-0 初期状態
Ａ[1, 2, 3] Ｂ[1, 2, 3] Ｃ[1, 2, 3]
０-1 f()を呼び出す。
①-1 Ａからpopした値をＣにpushする。
Ａ[1, 2, 3] Ｂ[1, 2, 3] Ｃ[1, 2, 3, 3]
①-2 f()を呼び出す。
②-1 Ａからpopした値をＣにpushする。
Ａ[1, 2] Ｂ[1, 2, 3] Ｃ[1, 2, 3, 3, 2]
②-2 f()を呼び出す。
③-1 Ａからpopした値をＣにpushする。
Ａ[1] Ｂ[1, 2, 3] Ｃ[1, 2, 3, 3, 2, 1]
③-2 f()を呼び出す。
Ａが空なので何もしない
③-3 Cからpopした値をＢにpushする。
Ａ[] Ｂ[1, 2, 3, 1] Ｃ[1, 2, 3, 3, 2, 1]
②-3 Cからpopした値をＢにpushする。
Ａ[] Ｂ[1, 2, 3, 1, 2] Ｃ[1, 2, 3, 3, 2]
①-3 Cからpopした値をＢにpushする。
Ａ[] Ｂ[1, 2, 3, 1, 2, 3] Ｃ[1, 2, 3, 3]
よって、スタックＢの状態は、[1, 2, 3, 1, 2, 3] となる。
