令和元年度 秋期 問62
スタックから取り出せない順番
出典: 令和元年度 秋期 ITパスポート試験 公開問題 問62 (IPA)
下から上へ品物を積み上げて，上にある品物から順に取り出す装置がある。この装置に対する操作は，次の二つに限られる。
PUSH x：品物 x を 1 個積み上げる。
POP：一番上の品物を 1 個取り出す。
最初は何も積まれていない状態から開始して，a，b，c の順で三つの品物が到着する。一つの装置だけを使った場合，POP 操作で取り出される品物の順番としてあり得ないものはどれか。
- ア a，b，c
- イ b，a，c
- ウ c，a，b
- エ c，b，a
正解と解説を見る
正解: ウ
- ア: PUSH と POP を交互に行えば、a、b、c の順に取り出せます。
- イ: a と b を積み、b、a の順に取り出した後で c を取り出せます。
- ウ: c を先に取り出すには a、b も積まれています。その後に取り出せるのは b で、a は取り出せないため、あり得ない順番です。正しい答えです。
- エ: 3 つを積んでから POP を 3 回行えば、c、b、a の順に取り出せます。
ポイント
この装置は、最後に積んだ物から取り出す スタック (後入れ先出し) です。a、b、c の順に到着します。
- ア a, b, c: PUSH a → POP、PUSH b → POP、PUSH c → POP で可能です。
- イ b, a, c: PUSH a、PUSH b → POP (b)、POP (a)、PUSH c → POP (c) で可能です。
- ウ c, a, b: c を最初に取り出すには、a、b、c を全部積む必要があります。すると下から a、b、c で、次に取り出せるのは b です。a は取り出せないので 不可能 です。
- エ c, b, a: 3 つ積んで順に POP すれば可能です。
この問題の用語: スタック
広告
「アルゴリズムとプログラミング」をこのサイトで解く (記録・間違えた問題の解き直し・AI教師への質問)
広告