問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 三个全部堆叠起来 (从下往上依次为 a→b→c)，然后再 POP 出 c。此时剩下的从下往上是 a、b，所以接下来只能取出最上面的 b。但选项 ウ 要求在 c 之后取出 a，而无法越过位于 a 上方的 b 直接取出 a。因此选项 ウ 的顺序无法实现，这就是「不可能出现」的正确答案。
错误エ
「c、b、a」是可以实现的。先按 PUSH a→PUSH b→PUSH c 把三个全部堆叠起来，再按 POP c→POP b→POP a 从上往下依次取出，就得到与到达顺序相反的顺序。因为可以实现，所以是错误选项。
ここがポイント
- 栈是后进先出 (LIFO) 的，任何时候能取出的都只有最上面的那个元素。
- 把 a、b、c 三个物品通过一个栈时，能生成的取出顺序按卡塔兰数共有 5 种，只有包含逆序在内的一部分顺序是可能的。要把先放入的物品比堆在它上面的物品更早取出，这样的顺序无法实现。
用語