スタック操作後に残る値を上からどう読む？
基本情報技術者試験 平成30年度春期 午前 問5 ／ アルゴリズムとプログラミング › データ構造
過去問にチャレンジ
次の二つのスタック操作を定義する。 PUSH n：スタックにデータ（整数値n）をプッシュする。 POP：スタックからデータをポップする。 空のスタックに対して，次の順序でスタック操作を行った結果はどれか。 PUSH 1 → PUSH 5 → POP → PUSH 7 → PUSH 6 → PUSH 4 → POP → POP → PUSH 3
- ア
- イ
- ウ
- エ
会話形式の解説
講師スタックは後入れ先出しです。POPで取り出すのは、最後に入れた値です。途中の状態を下から順に書いて追ってみましょう。
受験者最初に1、次に5を入れます。最初のPOPでは、上にある5を取り出すのですね。
講師はい。この時点で残るのは1です。その上に7、6、4を順に入れると、下から1、7、6、4になります。
受験者続くPOPは2回です。上にある4を取り出し、その次に6を取り出しますか。
講師そのとおりです。下から1、7が残り、最後に3を入れるので、下から1、7、3になります。
受験者求めるのは上からの順序なので、3、7、1です。1、7、3という選択肢は、下からの順序を読んでしまった結果ですね。
講師そうです。3、4、6という並びも違います。4と6は2回のPOPで取り出しており、残っていません。
受験者6、4、3という並びも、取り出した6と4が残っています。それに、最後に入れた3が一番上になっていません。
講師はい。残る値と順序の両方が合うのは、上から3、7、1のウです。
受験者途中は下から書いてPOPの対象を確かめ、最後に上から読み直せばよいのですね。
講師その確認が大切です。特に縦の図では、一番上の値を先頭として選択肢と照らし合わせます。
まとめ
スタックのPOPでは、最後に入れた値を取り出します。操作を順に追うと、最後に残る値は下から1、7、3です。問題で求められた上からの順序は3、7、1なので、正解はウです。
解答・解説
正解はウです
この問題のテーマ
スタックの後入れ先出しを使い、一連の操作後に残る値とその順序を求める問題です。
解き方の考え方
スタックは下から順に書き、PUSHでは末尾に値を加え、POPでは末尾の値を取り除きます。最初のPOPまでで「1，5」から5が除かれ、「1」になります。その後7，6，4を入れると「1，7，6，4」となり、続く2回のPOPで4，6が除かれます。最後に3を入れると下から「1，7，3」なので、上からは「3，7，1」です。
選択肢ごとの解説
- ×ア上から「1，7，3」という並びは、最初に入れた1を最上段に置いています。最後の操作で3をPUSHするため、最上段は3です。
- ×イ上から「3，4，6」では、4と6が残っています。両方とも最後のPUSHより前のPOPで取り出される値です。
- ○ウ上から「3，7，1」は、操作後に残る値と順序の両方が一致します。したがって、ウが正解です。
- ×エ上から「6，4，3」という並びでは、取り出したはずの6と4が残っています。また、最後に入れた3は、その後POPがないので最上段にあります。
POINT
- スタックのPOPは、最も新しく入れた値を取り出します。
- 途中の状態は下から順に書くと、次に取り出す値を末尾で確認できます。
- 図の縦方向を確認し、求められた「上から」の順序で選択肢と照合します。