データ構造(全8問中4問目)

後に入れたデータが先に取り出されるデータ構造(以下,スタックという)がある。これを用いて,図に示すような,右側から入力されたデータの順番を変化させて,左側に出力する装置を考える。この装置に対する操作は次の3通りである。
  1. 右側から入力されたデータをそのまま左側に出力する。
  2. 右側から入力されたデータをスタックの1番上に積み上げる。
  3. スタックの1番上にあるデータを取り出して左側に出力する。
 この装置の右側から順番にデータ A,B,C,D を入力した場合に,この①~③の操作を組み合わせても,左側に出力できない順番はどれか。
92.gif

出典:平成28年秋期 問92

  • B,A,D,C
  • B,D,C,A
  • C,B,D,A
  • C,D,A,B
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:データ構造
スタックは後入れ先出しのデータ構造で、データを積むプッシュ操作と、一番上のデータを取り出すポップ操作を用いて操作します。

A,B,C,Dの順で入力されるデータに対して、①入力されたデータをそのまま出力、②データをスタックに積む、③スタックからデータ取り出して出力、の3つを組み合わせることでデータの出力順序を変えることができます。この問題では、3つの操作を用いて各選択肢の順序で出力可能かどうかを検証します。
  • 以下の操作で出力可能です。
    92a.gif
  • 以下の操作で出力可能です。
    92i.gif
  • 以下の操作で出力可能です。
    92u.gif
  • 正しい。どのように操作しても"A"の出力が"B"の後になってしまうので出力できません。
    92e.gif

Pagetop