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