平成22年度 春期 問85
基礎理論
スタックに関する問題
下から上へデータを積み上げ，上にあるデータから順に取り出すデータ構造（以下，スタックという）がある。これを用いて，図に示すような，右側から入力されたデータの順番を変化させて，左側に出力する装置を考える。この装置に対する操作は次の 3 通りである。この装置の右側から順番に X，Y，Z を入力した場合に，この ① 〜 ③ の操作を組み合わせても，左側に出力できない順番はどれか。
① 右側から入力されたデータをそのまま左側に出力する。 ② 右側から入力されたデータをスタックに積み上げる。 ③ スタックの 1 番上にあるデータを取り出して左側に出力する。
〔図〕装置の構造（字に書き起こしたもの）
右側から X，Y，Z が入ってくる。 装置の中には「スタック」があり、 ①…入ってきたデータを素通りさせて左へ出す ②…入ってきたデータをスタックへ落とす ③…スタックの一番上を取り出して左へ出す 左側へ出た順番が「出力の順番」になる。
- アX，Z，Y
- イY，Z，X
- ウZ，X，Y
- エZ，Y，X
答えと解説を見る
✓ これが正解ウZ，X，Y
解説
積んだ二つは、必ず後から積んだほうが先に出てきます。
装置には、下から積み上げる置き場が付いています。取り出せるのは、いちばん上の一つだけでした。つまり後から積んだものが、先に出てくる並びです。入ってくるのは、三つの文字がこの順でした。作れる並びを一つずつ試し、残ったものを選びます。一つ目を素通りさせ、残る二つを積めば一通りできました。一つ目を積んでおき、後の二つを素通りさせる形も作れます。二つを積んでから三つ目をそのまま流す形も作れました。ところが三つ目を先に出すには、前の二つを積むしかありません。そのとき置き場は、下から一つ目、上に二つ目と並びます。次に出てくるのは、必ず上の二つ目でした。だから一つ目を二つ目より先に出せません。この並びを挙げた肢が当たり、スタックの決まりが効きます。シラバスも、この置き場を基礎の用語として挙げています。
ほかの選択肢はなぜ違うのか
- アX，Z，Y：一つ目を先に出す並びが、こちらのほうです。素通りさせれば、そのまま左のほうへ出ていきます。残る二つを積んでから、上のほうから取り出します。三つ目、二つ目の順で出てきました。だから作れる並びです。答えにはなりませんでした。
- イY，Z，X：二つ目を先に出す並びが、こちらに当たります。一つ目だけを先に積んでおく形になります。後の二つは、そのまま素通りさせていきました。最後に積んだ一つを取り出せば、そろいます。これも作れる並びでした。残る肢ではありません。
- エZ，Y，X：逆から順に出る並びが、こちらのほうに当たります。一つ目と二つ目を、続けて積んでおきました。三つ目のほうはそのまま素通りさせます。あとは上から取り出していけば、そろいました。これも作れる並びです。積んだ順の逆に出ました。
出典：平成22年度 春期 ITパスポート試験 問85（改変：原典の図表をテキストに書き起こした）
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）