平成22年度春期テクノロジ系

問85

下から上ヘデータを積み上げ，上にあるデータから順に取り出すデータ構造（以下，スタックという）がある。これを用いて，図に示すような，右側から入力されたデータの順番を変化させて，左側に出力する装置を考える。この装置に対する操作は次の3通りである。

①右側から入力されたデータをそのまま左側に出力する。
②右側から入力されたデータをスタックに積み上げる。
③スタックの1番上にあるデータを取り出して左側に出力する。

この装置の右側から順番にX, Y,Zを入力した場合に，この①～③の操作を組み合わせても，左側に出力できない順番はどれか。

ア

X, Z，Y

イ

Y， Z，X

ウ

Z，X，Y

エ

Z，Y，X

解答と解説

解答：ウ

X,Y,Zの入力順に対して、Z,X,Yで出力するということは、XとYをスタックに入れZをそのまま左側に出力する。このときスタックには以下のようにデータが積み上げられている。

したがって、Zを最初に出力する場合は、Z,Y,Xの順に出力できるが、Z,X,Yの順に出力できない。ほかも同じ考え方である。スタックは、後入れ先出し（Last In First Out：LIFO）なので、最後に入力されたデータが最初に取り出され、一番最初に入力されたデータは最後に取り出されるためである。