ITパスポート 2019年 秋期 問62

スタック操作の順序特性【ITパスポート解説】

正解の理由

解法ステップ

1. 装置の性質を確認する
   • スタック＝後入れ先出し（LIFO）。最後に入れたものが最初に出る。
2. 「cを最初に出す」場合を考える
   • cを最初に出すにはa, bを積んだ後にcを積み、POPでcを出す。
   • その後に残る順序は上からb → a。つまり次は必ずb、その後aになる。
3. 各選択肢が実現可能か、実際のPUSH/POP操作で確かめる
   • 実現できるものは操作例を書く（下に示します）。
   • 実現できないもの（ウ）は、上の理由で不可と判断する。

• ア: a, b, cを順に取り出す（a, b, c）
  操作例：PUSH a, POP (a), PUSH b, POP (b), PUSH c, POP (c)
• イ: b, a, c（b, a, c）
  操作例：PUSH a, PUSH b, POP (b), POP (a), PUSH c, POP (c)
• エ: c, b, a（c, b, a）
  操作例：PUSH a, PUSH b, PUSH c, POP (c), POP (b), POP (a)

選択肢別の誤答解説

• ア: a, b, c
  • 問題なし。到着順にそのままPOPする（各PUSHの直後にPOP）ことで可能です。
• イ: b, a, c
  • 可能。まずaを積んでからbを積み、bを先にPOP、次にaをPOP。その後cを扱えば実現します。
• ウ: c, a, b
  • 不可能。cを先に取り出すにはa, b, cをすべて積む必要があり、その直後に残るのは上からb → a。したがってcの次にaを取り出すことはできません。
• エ: c, b, a
  • 可能。a, b, cを順に積んでから順にPOPすれば得られます。

よくある誤解

1. 「どんな順番でもできる」と思う誤解
   • スタックでは最後に入れたものが先に出るため、すべての順列が可能なわけではありません。順序制約があります。
2. 「POPは任意の位置の品物を取り出せる」と考える誤解
   • POPは必ず“いま一番上”しか取り出せません。中身を取り出すには上のものを全部出す必要があります。
3. キュー（queue）と混同する誤解
   • キューは先入れ先出し（FIFO = First In, First Out）で、性質が逆です。問題の装置はスタックです。

補足コラム

• この問題は「スタックが作れる出力順（stack permutation）」の例です。n個の要素に対して、スタックで出力可能な順列の数はカタラン数（Catalan number）で表されます。式は $$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$$ です。例えばn=3のとき $C_3=5$ で、6通りの順列のうち5通りが可能、1通り（今回のc,a,b）が不可能になります。
• 実務的には、スタックの性質は「Webブラウザの戻るボタン」や「関数の呼び出しの戻り順」など、身近な場面で使われます。順序の制約を意識すると、アルゴリズムを考える力がつきます。

FAQ

def is_stack_permutation(input_seq, output_seq):
    stack = []
    i = 0  # index for input_seq
    for want in output_seq:
        # push until top of stack equals want or input exhausted
        while (not stack or stack[-1] != want) and i < len(input_seq):
            stack.append(input_seq[i])
            i += 1
        if stack and stack[-1] == want:
            stack.pop()
        else:
            return False
    return True

# 例
print(is_stack_permutation(['a','b','c'], ['c','a','b']))  # False
print(is_stack_permutation(['a','b','c'], ['c','b','a']))  # True