後に入れたデータが先に取り出されるデータ構造(以下、スタックという)がある。
これを用いて、図に示すような、右側から入力されたデータの順番を変化させて、左側に出力する装置を考える。
この装置に対する操作は次の3通りである。
@ |
右側から入力されたデータをそのまま左側に出力する。 |
A |
右側から入力されたデータをスタックの1番上に積み上げる。 |
B |
スタックの1番上にあるデータを取り出して左側に出力する。 |
この装置の右側から順番にデータA、B、C、Dを入力した場合に、この@〜Bの操作を組み合わせても、左側に出力できない順番はどれか。
ア |
B, A, D, C |
|
イ |
B, D, C, A |
ウ |
C, B, D, A |
|
エ |
C, D, A, B |
答え エ
【解説】
ア |
B, A, D, Cは、A→@→B→A→@→Bで可能です。 |
イ |
B, D, C, Aは、A→@→A→@→B→Bで可能です。 |
ウ |
C, B, D, Aは、A→A→@→B→@→Bで可能です。 |
エ |
C, D, A, Bは、Cを先に出すためにAとBをスタックに積む必要がありますが、このときA→Bの順に取り出すことができません。 |
【キーワード】
・スタック
【キーワードの解説】
- スタック
データを一時的に記憶するためにメモリに割り当てる領域のことです。
データの取り出しを行うとき、取り出されるデータは最後に挿入されたデータになるので、後入れ先出し方式(Last-In First-Out、LIFO)とも呼ばれます。
もっと、「スタック」について調べてみよう。
戻る
一覧へ
次へ
|