問５
Ａ、Ｂ、Ｃの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合、データの出力順序は何通りあるか。
←─┐ ┌──Ａ、Ｂ、Ｃ
│ ↓
│ │
│ ス │
│ タ │
│ ッ │
│ ク │
└──┘
ア 3 イ 4 ウ 5 エ 6
正解
ウ
解説
スタックに挿入することをプッシュ、取り出すことをポップという。プッシュをPU(x)、ポップをPO(x)で表すと、
PU(A),PO(A),PU(B),PO(B),PU(C),PO(C) ・・・ABCを出力
PU(A),PO(A),PU(B),PU(C),PO(C),PO(B) ・・・ACBを出力
PU(A),PU(B),PO(B),PO(A),PU(C),PO(C) ・・・BACを出力
PU(A),PU(B),PO(B),PU(C),PO(C),PO(A) ・・・BCAを出力
PU(A),PU(B),PU(C),PO(C),PO(B),PO(A) ・・・CBAを出力
以上、5通りの出力順序がある。
タグ：スタック
