ITパスポート試験 ITパスポート 2010年 (平成22年 春期) 問85: 下から上へデータを積み上げ,上にあるデータから順に取り出すデータ構造(以下,スタックという)がある。これを用いて,図に示すような,右側から入力されたデータの順番

問題本文

下から上へデータを積み上げ,上にあるデータから順に取り出すデータ構造(以下,スタックという)がある。これを用いて,図に示すような,右側から入力されたデータの順番を変化させて,左側に出力する装置を考える。この装置に対する操作は次の3通りである。 ① 右側から入力されたデータをそのまま左側に出力する。 ② 右側から入力されたデータをスタックに積み上げる。 ③ スタックの1番上にあるデータを取り出して左側に出力する。 この装置の右側から順にX,Y,Zを入力した場合に,この①~③の操作を組み合わせても,左側に出力できない順番はどれか。

選択肢

• ア.X,Z,Y
• イ.Y,Z,X
• ウ.Z,X,Y
• エ.Z,Y,X

正解

ウ. Z,X,Y

解説

スタックはLIFO (Last In First Out) 構造. X,Y,Zの順に入力された場合,Z,X,Yの順に出力するにはZを先に出した後XをYより先に出す手順が無く実現できない.

選択肢ごとの解説

• ア.誤り. X直出力,Yスタック,Zスタック,ZY取出しでX,Z,Y可能.
• イ.誤り. Xスタック,Y直,Zスタック,Z,X取出しでY,Z,X可能.
• ウ.正しい. Z,X,Yの順序はスタックでは実現できない出力順.
• エ.誤り. X,Y,Z全てスタックして上から取出すとZ,Y,X可能.