問62
頻出度★☆☆
下から上へ品物を積み上げて, 上にある品物から順に取り出す装置がある。この装置に対する操作は, 次の二つに限られる。 PUSH x : 品物 x を1個積み上げる。 POP : 一番上の品物を1個取り出す。 最初は何も積まれていない状態から開始して, a, b, c の順で三つの品物が到着する。一つの装置だけを使った場合, POP 操作で取り出される品物の順番としてあり得ないものはどれか。
令和元年度 秋期 ITパスポート試験 問62
テクノロジ系アルゴリズムとプログラミング › データ構造
この問題の解説と、これまでの解答の記録です。
解説
問 62
不正解ア
「a, b, c」は実現できます。PUSH a→POP a→PUSH b→POP b→PUSH c→POP c と、到着するたびに積んですぐ取り出せば、到着順そのままに取り出せます。実現可能なので「あり得ないもの」ではありません。
不正解イ
「b, a, c」は実現できます。PUSH a→PUSH b→POP b→POP a→PUSH c→POP c とすれば、先に a と b を積んで上の b を取り、続いて a を取り、最後に c を取り出せます。実現可能なので誤りです。
- ウ
正解 この装置は「後入れ先出し (LIFO)」のスタックで、常に一番上の品物しか取り出せません。品物は a, b, c の順に到着します。ウの「c, a, b」を最初に c から取り出すには、a, b, c の3個をすべて積み上げた状態 (下から a→b→c) にしてから c を POP する必要があります。その時点で残りは下から a, b なので、次に取り出せるのは一番上の b だけです。しかしウでは c の次に a を取り出す順番になっており、a より上にある b を飛ばして a を取ることはできません。したがってウの順番は実現不可能で、これが「あり得ないもの」の正解です。
不正解エ
「c, b, a」は実現できます。PUSH a→PUSH b→PUSH c と3個すべて積み上げてから、POP c→POP b→POP a と上から順に取り出せば到着順の逆順になります。実現可能なので誤りです。
ここがポイント
- スタックは後入れ先出し (LIFO) で、取り出せるのは常に一番上の要素だけである。
- a, b, c の3個を1つのスタックに通したときに作れる取り出し順はカタラン数より5通りで、逆順を含む一部だけが可能。先に入れた品物を、その上に積まれた品物より先に取り出す順番は実現できない。
用語