ITパスポート 平成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（改変：原典の図表をテキストに書き起こした）
解説は当サイト独自のもので、IPA（独立行政法人情報処理推進機構）とは関係ありません。
関連問題
- 平成30年度 秋期 （特別措置試験） 問76：
スタックからの データの 取出し方 （スタック） - 平成30年度 春期 （特別措置試験） 問96：
キューに 関する 問題 （スタック） - 平成28年度 秋期 （特別措置試験） 問92：
スタックに 関する 問題 （スタック） - 平成21年度 秋期 問54：
スタックに 関する 問題 （スタック）
同じ分野の問題
誤りを見つけたら報告する