スタックで出力できる順序を到着順から確かめる
基本情報技術者試験 平成29年度秋期 午前 問5 ／ アルゴリズムとプログラミング › データ構造
過去問にチャレンジ
A，B，C，Dの順に到着するデータに対して，一つのスタックだけを用いて出力可能なデータ列はどれか。
- ア
A，D，B，C
- イ
B，D，A，C
- ウ
C，B，D，A
- エ
D，C，A，B
会話形式の解説
講師今回はスタックの問題です。データは決まった順にしか届かず、取り出せるのはいつも一番上だけです。この二つの制約で、どの出力順なら作れるかを考えます。
受験者スタックは後入れ先出し、つまり最後に入れたものから出るという性質ですよね。ただ、途中で出したり入れたりできるので、組合せが多くて頭の中で追い切れません。
講師頭の中だけで追わずに、手順を決めて試すと確実です。到着順に積む操作をPUSH、一番上を取り出す操作をPOPといいます。出したいデータが一番上に来るまで到着順にPUSHし、一番上に来たらPOPする。これを出力の先頭から順に繰り返します。
受験者では「A，D，B，C」から試します。Aは届いてすぐ出せます。次のDを出すにはB、C、Dを積んでDを出します。そうすると残りは上からC、Bです。
講師そこで次に出したいデータは何で、一番上にありますか。
受験者次はBですが、一番上はCです。BはCの下に埋もれているので出せません。この順は作れないということですね。
講師そのとおりです。出したいデータが一番上になく、スタックの途中にあると分かった時点で、もうその順は作れないと判断できます。「B，D，A，C」はどうでしょう。
受験者A、Bを積んでBを出し、C、Dを積んでDを出します。残りは上からC、Aなので、次に出せるのはCです。Aを先に出したいのにできないので、これも誤りです。
講師「D，C，A，B」も同じ形でつまずきます。Dを最初に出すにはA〜Dを全部積む必要があり、D、Cを出すと残りは上からB、Aです。Aを先に出せないので作れません。
受験者残った「C，B，D，A」を確かめます。A、B、Cを積んでC、Bの順に出し、届いたDを積んですぐ出して、最後に残ったAを出します。どの段階でも出したいデータが一番上にあるので、出力できます。
講師正しいです。誤りの三つには共通点があります。スタックに残ったデータは、積んだ順と逆の順でしか出せません。誤りの選択肢はどれも、残ったデータを積んだ順のまま出そうとしているところで行き詰まっています。
受験者なるほど。スタックの中に下からA、Bと残っていたら、出せる順はB、Aしかないということですね。
講師そうです。同じ形式の問題は過去にも何度か出ています。選択肢ごとに「積む・出す」を先頭から試し、出したいデータが埋もれていないかを見れば、計算に時間をかけずに判定できます。
まとめ
A、B、C、Dの順に届くデータを一つのスタックだけで出力するとき、作れる出力順を選ぶ問題で、正解は「C，B，D，A」です。スタックは後入れ先出し（LIFO）で、取り出せるのは一番上のデータだけです。到着順にPUSHし、出したいデータが一番上に来たらPOPする操作を先頭から試すと、正しい選択肢ではどの段階でも出したいデータが一番上にあります。ほかの選択肢では、出したいデータがスタックの途中に埋もれていて出せません。スタックに残ったデータは積んだ順と逆の順でしか出せない、という点が判定の決め手です。
解答・解説
正解はウです
この問題のテーマ
データがA、B、C、Dの順に届くとき、スタックを一つだけ使って作れる出力順を選ぶ問題です。スタックの後入れ先出し（LIFO）を理解しているかを問うています。
解き方の考え方
データは到着順にしかスタックへ積めず（PUSH）、取り出せるのはいつも一番上のデータだけです（POP）。そこで選択肢ごとに、出力したいデータが一番上に来るまで到着順に積み、来たら取り出す、という操作を先頭から順に試します。出したいデータがスタックの途中に埋もれていて一番上にない場合は、その時点で出力できないと判断できます。
選択肢ごとの解説
- ×ア A，D，B，C「A，D，B，C」は、届いたAをそのまま出したあと、Dを出すためにB、C、Dを積んでDを取り出します。このとき一番上にあるのはCで、Bはその下にあります。BをCより先に出すことはできないので、この順では出力できません。
- ×イ B，D，A，C「B，D，A，C」は、A、Bを積んでBを出し、続いてC、Dを積んでDを出します。この時点でスタックは上からC、Aの順なので、次に出せるのはCです。Aを先に出す必要があるため、この順は作れません。
- ○ウ C，B，D，A「C，B，D，A」は、A、B、Cを積んでC、Bの順に取り出し、届いたDを積んですぐ出して、最後に残ったAを出せば得られます。どの段階でも出したいデータが一番上にあるので、一つのスタックで出力できます。
- ×エ D，C，A，B「D，C，A，B」は、Dを最初に出すためにA〜Dをすべて積み、D、Cを取り出します。残りは上からB、Aの順なので、次に出せるのはBです。AをBより先に出すことはできないため、出力できません。
POINT
- スタックは後入れ先出し（LIFO）で、格納をPUSH、取り出しをPOPといいます。
- 取り出せるのは一番上のデータだけで、下にあるデータを出すには、上に積まれたデータを先にすべて取り出す必要があります。
- 出力順の判定では、到着順に積んで、出したいデータが一番上に来たら取り出す操作を先頭から試すと確実です。
- スタック内に残ったデータは、積んだ順と逆の順でしか出せません。