下から上へデータを積み上げ、上にあるデータから順に取り出すデータ構造(以下、スタックという)がある。
これを用いて、図に示すような、右側から入力されたデータの順番を変化させて、左側に出力する装置を考える。
このそうちに対する操作は次の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をスタックから取り出して出力) |
【キーワード】
・スタック