平成22年春期試験問題 問85
問85解説へ
下から上へデータを積み上げ，上にあるデータから順に取り出すデータ構造（以下，スタックという）がある。これを用いて，図に示すような，右側から入力されたデータの順番を変化させて，左側に出力する装置を考える。この装置に対する操作は次の3通りである。
- 右側から入力されたデータをそのまま左側に出力する。
- 右側から入力されたデータをスタックに積み上げる。
- スタックの一番上にあるデータを取り出して左側に出力する。
- X，Z，Y
- Y，Z，X
- Z，X，Y
- Z，Y，X
正解 ウ問題へ
広告
解説
スタックは、LIFO(Last In First Out)、すなわち最後に格納したものから先に取り出すルールでデータを管理する構造です。スタック構造ではデータを格納する操作をpush、取り出す操作をpopと呼びます。
取り出すのは最後に格納したデータのみ、というルールに従って、一つずつ出力できるかどうか試していくと次のようになります。
取り出すのは最後に格納したデータのみ、というルールに従って、一つずつ出力できるかどうか試していくと次のようになります。
- push(X) → pop(X) → push(Y) → push(Z) → pop(Z) → pop(Y)
- push(X) → push(Y) → pop(Y) → push(Z) → pop(Z) → pop(X)
- 出力できません。Zを最初に取り出すためには、最初に push(X) → push(Y) → push(Z)で3つのデータを積み必要がありますが、Zの取り出し後、Xの上にはYがあるため、Yより先にXを取り出すことができません。
- push(X) → push(Y) → push(Z) → pop(Z) → pop(Y) → pop(X)
広告