スタックの後入れ先出しで取り出せない順番は？
ITパスポート試験 令和元年度秋期 問62 ／ アルゴリズムとプログラミング › データ構造
過去問にチャレンジ
下から上へ品物を積み上げて，上にある品物から順に取り出す装置がある。この装置に対する操作は，次の二つに限られる。 PUSH x：品物xを1個積み上げる。 POP：一番上の品物を1個取り出す。 最初は何も積まれていない状態から開始して，a，b，cの順で三つの品物が到着する。一つの装置だけを使った場合，POP操作で取り出される品物の順番としてあり得ないものはどれか。
- ア
a，b，c
- イ
b，a，c
- ウ
c，a，b
- エ
c，b，a
会話形式の解説
講師この問題では、スタックの「後入れ先出し」に注目します。POPで取り出せるのは、その時点で一番上にある品物だけです。
受験者全部積んでから取り出すと逆順ですが、途中でPOPすれば別の順番にもできそうです。
講師その通りです。aを積んですぐ取り出し、bとcも同じように扱えば、a、b、cの順になります。
受験者b、a、cなら、aとbを積んでから2回取り出し、最後にcを積んで取り出せますね。
講師はい。最初の2回のPOPでb、aの順に取り出せるので、その順番も実現できます。
受験者cを最初に取り出すには、a、b、cを順に積む必要があります。
講師そうです。cを取り出した直後は、bがaの上に残っています。次にaを取り出すことはできません。
受験者bを飛ばしてaを取り出せないので、c、a、bの順は不可能なのですね。
講師はい。一方、三つとも積んでから続けてPOPすれば、c、b、aの順に取り出せます。
受験者到着順と逆順の両方が可能でも、途中の並びがすべて可能とは限らないのですね。
講師順番に迷ったら、PUSHとPOPを一つずつ追い、次に取り出したい品物が一番上にあるか確かめます。
まとめ
スタックは、最後に積んだ品物から取り出す後入れ先出しの装置です。到着順に一つずつ積んで取り出すことも、途中でPOPを挟むこともできます。cを最初に取り出した直後はbがaの上に残るため、次にaは取り出せません。したがって、あり得ない順番は「c、a、b」です。
解答・解説
正解はウです
この問題のテーマ
品物を積んで、上から取りり出すスタックの動きを問う問題です。
解き方の考え方
スタックでは、最後に積んだ品物から取り出します。各選択肢について、到着順を守ってPUSHとPOPを行えるかを確かめます。特にcを最初に取り出す場合、その下に何が残るかが決め手です。
選択肢ごとの解説
- ×ア a，b，caを積んですぐ取り出し、次にb、最後にcも同じように扱えば、a、b、cの順になります。品物を積みっぱなしにする必要はありません。
- ×イ b，a，ca、bを順に積んでから2回取り出すと、b、aの順になります。その後、到着したcを積んで取り出せば、b、a、cになります。
- ○ウ c，a，bcを最初に取り出すには、a、b、cを順に積む必要があります。cを取り出した直後はbがaの上に残るため、次にaを取り出すことはできません。
- ×エ c，b，aa、b、cを順に積んでから3回取り出せば、上からc、b、aの順になります。これはスタックの後入れ先出しの動きそのものです。
補足
取り出す順番が到着順とも逆順とも限らない点に注意します。PUSHとPOPを交互に行えば到着順に、すべて積んでからPOPすれば逆順に取り出せます。
POINT
- スタックは、最後に積んだものを最初に取り出す「後入れ先出し」です。
- POPで取り出せるのは、その時点で一番上にある品物だけです。
- 到着した品物は順にPUSHしますが、途中でPOPを挟めます。
- cを最初にPOPした直後はbが最上段なので、次はaにできません。