応用情報技術者試験 令和3年春 午前問5 解説付き過去問

この問題は、スタックの基本操作である「挿入（push）」と「取出し（pop）」を用いて、入力されたデータA、B、Cの出力順序が何通り可能かを問うものです。スタックは後入れ先出し（LIFO）の性質を持つため、その制約下で出力され得る順列を考察する必要があります。

1. スタックの基本動作
   スタックは「後から入れたデータを先に取り出す」という性質を持つデータ構造です。
   例えば、Aをpushした後にpopすればAが出力されますが、Aをpushした後にBをpushすると、先にBをpopしなければAは取り出せません。
   
   
2. 全出力順序の候補
   A、B、Cの入力順序に対して、出力の可能性としては3!（6通り）存在します。
   これらすべてがスタック操作で実現できるかどうかを、1通りずつ検証していきます。
   
   
3. 出力可能な順序の検証
   次の5通りはスタック操作で出力可能です：
   ・A B C（各データをpush→即pop）
   ・A C B（Aをpop後、BとCをpush、Cをpop、次にB）
   ・B A C（A→Bをpush、Bをpop、Aをpop、Cをpush→pop）
   ・B C A（A→Bをpush、Bをpop、Cをpush→pop、Aをpop）
   ・C B A（A→B→Cをpushして順にpop）
   一方、C A B の順序はスタックの構造上不可能です。Cを最初にpopするためにはA、Bをスタックに積んだ状態でCをpushし、Cをpopする必要がありますが、その後にAをBより先にpopすることができません。
   
   

以上より、スタック操作によって実現可能な出力順序は5通りです。スタックのLIFO構造を理解し、出力順をシミュレーションすることが解答の鍵となります。