平成29年 秋期 基本情報技術者 午前 問5

A、B、C、Dの順に到着するデータに対して、一つのスタックだけを用いて出力可能なデータ列はどれか。

　ア 　A、D、B、C 　イ 　B、D、A、C
　ウ 　C、B、D、A 　エ 　D、C、A、B

答え　ウ

【解説】
それぞれの出力を考えてみる。(“[ ]”はスタックの状態、“{ }”は出力の結果)

　ア
  1. Aをスタックに入れる。　[A], { }
  2. Aをスタックから出す。　[ ], {A}
  3. Bをスタックに入れる。　[B], {A}
  4. Cをスタックに入れる。　[C, B], {A}
  5. Dをスタックに入れる。　[D, C, B], {A}
  6. Dをスタックから出す。　[C, B], {A, D}
ここで次にスタックから出せるのはCなので選択肢の出力はできない。
　イ
  1. Aをスタックに入れる。　[A], { }
  2. Bをスタックに入れる。　[B, A], { }
  3. Bをスタックから出す。　[A], {B}
  4. Cをスタックに入れる。　[C, A], {B}
  5. Dをスタックに入れる。　[D, C, A], {B}
  6. Dをスタックから出す。　[C, A], {B, D}
ここで次にスタックから出せるのはCなので選択肢の出力はできない。
　ウ
  1. Aをスタックに入れる。　[A], { }
  2. Bをスタックに入れる。　[B, A], { }
  3. Cをスタックに入れる。　[C, B, A], { }
  4. Cをスタックから出す。　[B, A], {C}
  5. Bをスタックから出す。　[A], {C, B}
  6. Dをスタックに入れる。　[D, A], {C, B}
  7. Dをスタックから出す。　[A], {C, B, D}
  8. Aをスタックから出す。　[ ], {C, B, D, A}
　エ
  1. Aをスタックに入れる。　[A], { }
  2. Bをスタックに入れる。　[B, A], { }
  3. Cをスタックに入れる。　[C, B, A], { }
  4. Dをスタックに入れる。　[D, C, B, A], { }
  5. Dをスタックから出す。　[C, B, A], {D}
  6. Cをスタックから出す。　[B, A], {D, C}
ここで次にスタックから出せるのはBなので選択肢の出力はできない。

【キーワード】
・スタック

【キーワードの解説】
  • スタック
    データを一時的に記憶するためにメモリに割り当てる領域のことです。
    データの取り出しを行うとき、取り出されるデータは最後に挿入されたデータになるので、後入れ先出し方式(Last-In First-Out、LIFO)とも呼ばれます。

もっと、「スタック」について調べてみよう。

戻る 一覧へ 次へ