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

問題文

下から上へ品物を積み上げて、上にある品物から順に取り出す装置がある。この装置に対する操作は、次の二つに限られる。

PUSH x：品物xを1個積み上げる。 POP：　一番上の品物を1個取り出す。

最初は何も積まれていない状態から開始して、a、b、cの順で三つの品物が到着する。一つの装置だけを使った場合、POP操作で取り出される品物の順番としてあり得ないものはどれか。

🖊️ 解答を隠して解いてみる

選択肢

ア：a, b, c

イ：b, a, c

ウ：c, a, b（正解）

エ：c, b, a

🔒 解説は解答すると表示されます

積み上げ装置（PUSH/POP）の取り出し順【ITパスポート解説】

正解の理由

この装置は「スタック（stack：後入れ先出し、LIFO = Last In, First Out）」です。PUSH x は品物 x を上に積む操作、POP は一番上の品物を取り出す操作です。a、b、c の到着順は固定（a → b → c）で、装置は一つだけ使えます。

まず c を最初に取り出すには、a, b を積んだ後に c を積み、POP して c を出すしかありません。ところがその時点で装置の中には（下から）a, b が残り、次に取り出せるのは上にある b です。つまり c の次に a を取り出す（c, a, b）のような順序は物理的に不可能です。したがって、取り出し順としてあり得ないのはウ（c, a, b）です。

解法ステップ

装置の性質を確認する
- スタック＝後入れ先出し（LIFO）。最後に入れたものが最初に出る。
「c を最初に出す」場合を考える
- c を最初に出すには a, b を積んだ後に c を積み、POP で c を出す。
- その後に残る順序は上から b → a。つまり次は必ず b、その後 a になる。
各選択肢が実現可能か、実際の 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 すれば得られます。

よくある誤解

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

補足コラム

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

FAQ

Q1. POP した品物をまた PUSH できる？
A1. 問題文が許すなら技術的には可能ですが、到着順が a→b→c と決まっているため、c を先に出した後に a を先に出すことは積み替えなしにはできません。問題は「装置1台だけでの操作」を問っています。

Q2. 装置を二つ使えばどうなる？
A2. スタックを2台使う（直列や並列）と、扱える順列の範囲が変わります。例えば2台直列にすると全順列が可能になる場合があります（具体的条件による）。

Q3. プログラムで確かめる方法は？
A3. 入力列と出力列をシミュレーションするのが簡単です。以下はその一例です。

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