基礎理論｜平成28年度 秋期 ITパスポート試験（特別措置試験） 問92
後に入れたデータが先に取り出されるデータ構造（以下，スタックという）がある。これを用いて，図に示すような，右側から入力されたデータの順番を変化させて，左側に出力する装置を考える。この装置に対する操作は次の3通りである。
- ① 右側から入力されたデータをそのまま左側に出力する。
- ② 右側から入力されたデータをスタックの1番上に積み上げる。
- ③ スタックの1番上にあるデータを取り出して左側に出力する。
この装置の右側から順番にデータA，B，C，Dを入力した場合に，この①〜③の操作を組み合わせても，左側に出力できない順番はどれか。
〔図〕（原典は枠と矢印で描いた装置図。流れの記述に書き起こしたもの）
```
入力 A, B, C, D ──→ 装置 ──→ 出力
装置の中身: ① 素通り（入力→出力）
② 積む（入力→スタック）
③ 取り出す（スタック→出力）
```
- B，A，D，C
- B，D，C，A
- C，B，D，A
- ✓ これが正解C，D，A，B
解説
二つためたら、入れた順の逆でしか取り出せなくなります。
後から入れたものが先に出る入れ物なので、二つ以上ためた時点で、出る順は入れた順の逆に固定されます。ここが手がかりです。素通りさせる道もあるので、ためずに出すこともできますが、いったんためた二つの前後を入れ替えることはできません。だから、出力の並びを見て、先に入るはずのものが後ろに来ている組を探し、その二つが同時に入れ物の中にいるかどうかを確かめます。同時にいるなら、その並びは作れません。作れる三つについては、ためる、素通りする、取り出すの三つを順に当てていけば、実際に手が動きます。できないほうを訊かれているので、三つ作れた時点で残りが答です。後入れ先出しのこの入れ物をスタックと呼び、先入れ先出しのものはキューと呼びます。シラバスはリストや木構造と並べて、データ構造の用語例に挙げています。
ほかの選択肢はなぜ違うのか
- ためて、素通りさせて、取り出す。この繰り返しで作れます。二つを同時にためる場面がないので、順を入れ替える必要も起きません。素通りの道があることが、この問いを解ける鍵になっています。装置図の矢印を一本ずつ指で追います。
- 一つためたまま二つを素通りさせ、あとから順に取り出せば作れます。取り出す順が入れた順の逆になっているので、無理がありません。作れることを示すには、実際の手順を一つ書けば足ります。できないほうを訊く問いでは、これを三つ分やります。
- 二つためてから素通りさせ、逆順に取り出せば作れます。ためた二つが逆順で出ているので、入れ物の決まりと合っています。三つまで作れた時点で、残る一つが自動的に答だと決まります。四つ全部を最後まで試してみる必要はありません。
この問題に関係する言葉
- スタック
- キュー
- データ構造
出典：平成28年度 秋期 ITパスポート試験（特別措置試験） 問92
同じ単元をまとめて解くなら基礎理論へ。
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）