スタック とは

2019
スポンサーリンク

スタック とは

基本情報技術者 過去問 2019年(平成31年) 春 午前 問6 を参考に考えてみます。

<問題>

三つのスタックA,B,Cのいずれの初期状態も[1,2,3]であるとき,再帰的に定義された関数f()を呼び出して終了した後のBの状態はどれか。ここで,スタックが,[a1 a2,…,an-1]の状態のときにanをpushした後のスタックの状態は[a1 a2,…,an-1,an]で表す。

f(){
 Aが空ならば{
  何もしない。
 }
 そうでない場合{
  Aからpopした値をCにpushする。
  f()を呼び出す。
  Cからpopした値をBに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]

スポンサーリンク

三つのスタックA,B,Cのいずれの初期状態も[1,2,3]であるとき,再帰的に定義された関数f()を呼び出して終了した後のBの状態はどれか。ここで,スタックが,[a1 a2,…,an-1]の状態のときにanをpushした後のスタックの状態は[a1 a2,…,an-1,an]で表す。

ここから私の思考です↓

ちなみに青字は文章を読んだ際の私の頭の中です。

三つのスタックA,B,Cのいずれの初期状態も[1,2,3]であるとき,再帰的に定義された関数f()を呼び出して終了した後のBの状態はどれか。ここで,スタックが,[a1 a2,…,an-1]の状態のときにanをpushした後のスタックの状態は[a1 a2,…,an-1,an]で表す。

スタックってのは確か、入れ物の中に順番に入れていって、

入れ物から出す場合は最後に入れたものから出すってやつで、

キューってのも入れ物の中に順番に入れていって、

入れ物から出す場合は先に入れたものから出すってやつだったと思う。

最初はこういうことか。

後は順番に進めるしかないな。

Aは空ではないから飛ばす。

Aの3をCに移す。

また関数を呼び出せってことなので、関数を持ってきます。

わかりやすいように色分けしておきます。

Aは空じゃないので飛ばします。

Aの2をCに渡します。そんでまた関数を呼び出します。

ややこしいことしないでいただきたい。

また呼び出しました。こんにちは。

Aは空ではないのでとばします。

Aの1をCに渡します。そしてまたまた関数を呼び出します。

小さくて見にくくなってきましたねっっ緑色部分が今回呼び出した部分です。

Aは空っぽなのでなにもしません。緑部分終了!緑部分消します。

Cから一番上の1をBに渡します。朱色?部分終了です!朱色?部分消します。

Cの2をBに渡します。青色部分終了です。青色部分消します。

ようやく最後ですね。Cの3をBに渡します。終わったー!

Bは下から順に1,2,3,1,2,3,ですね。ここまで丁寧に解説して

間違ってたらすごい恥ずかしいんですけど。

ってことで選択肢から探します。

<選択肢>

(ア)  [1,2,3,1,2,3]

(イ)  [1,2,3,3,2,1]

(ウ)  [3,2,1,1,2,3]

(エ)   [3,2,1,3,2,1]

ほらあった!正解は(ア)!!絶対!!

正解は(ア)です。

ほら!ほらほら!今回は完璧やね。

スタックとは、コップみたいなものです。何か出すときは最後に入れたものを出します。

ここから私の思考です↓

完璧です。さすが俺!

また1つ賢くなりました。よかったよかった。

コメント

  1. 文系女子 より:

    「Aが空ならば、Cからpopした値をBにpushする」に行くというところが、図を見てようやく理解できました。
    ありがとうございます!

    • じーよ より:

      理解してもらえてよかったです。

      勉強頑張ってくださいね。陰ながら応援しています。

  2. […] 一覧へ 次の問題 […]

  3. […] 前の問題 一覧へ 次の問題 気分転換 […]

タイトルとURLをコピーしました