問62
頻出度★☆☆
下から上へ品物を積み上げて, 上にある品物から順に取り出す装置がある。この装置に対する操作は, 次の二つに限られる。 PUSH x : 品物 x を1個積み上げる。 POP : 一番上の品物を1個取り出す。 最初は何も積まれていない状態から開始して, a, b, c の順で三つの品物が到着する。一つの装置だけを使った場合, POP 操作で取り出される品物の順番としてあり得ないものはどれか。
令和元年度 秋期 ITパスポート試験 問62
テクノロジ系アルゴリズムとプログラミング › データ構造
This question's explanation and your answers so far.
解説
問 62
Incorrectア
'a, b, c' is achievable. With PUSH a → POP a → PUSH b → POP b → PUSH c → POP c, if you stack each item and remove it immediately as it arrives, you can remove them in exactly their arrival order. Since it is achievable, it is not the impossible one.
Incorrectイ
'b, a, c' is achievable. With PUSH a → PUSH b → POP b → POP a → PUSH c → POP c, you first stack a and b, remove the b on top, then remove a, and finally remove c. Since it is achievable, it is a wrong choice.
- ウ
正解 This device is a last-in first-out (LIFO) stack, and only the item on top can ever be removed. The items arrive in the order a, b, c. For choice ウ, 'c, a, b', to remove c first you must first stack all three items a, b, c (from bottom to top: a → b → c) and then POP c. At that point the remaining items, from bottom to top, are a, b, so the only item you can remove next is the b on top. However, choice ウ calls for removing a right after c, and you cannot skip over the b that sits above a to take a. Therefore the order in choice ウ cannot be achieved, which is why it is the correct answer for the order that is NOT possible.
Incorrectエ
'c, b, a' is achievable. After stacking all three items with PUSH a → PUSH b → PUSH c, if you remove them from the top in order with POP c → POP b → POP a, you get the reverse of the arrival order. Since it is achievable, it is a wrong choice.
ここがポイント
- A stack is last-in first-out (LIFO), and the only element that can ever be removed is the one on top.
- When three items a, b, c are passed through a single stack, the number of removal orders that can be produced is 5 (from the Catalan number), and only some of them — including the reverse order — are possible. An order that removes an item placed earlier before an item stacked on top of it cannot be achieved.
用語