令和3年度 春期 応用情報技術者試験 午前 問5

スタックは 後入れ先出し（LIFO: Last In First Out） のデータ構造です。図の模式図が示すように、データは上部の開口部から挿入され、最後に入れたものから順に取り出されます。
データは $A, B, C$ の順でスタックに挿入されます。スタックへの挿入と取出しのタイミングの組み合わせによって、以下のようなデータの出力順序が考えられます。

• 最初に $A$ を出力する場合（$A$ を挿入してすぐ取り出す）
  • $B$ を挿入・取出し、$C$ を挿入・取出し $\rightarrow A, B, C$
  • $B, C$ と続けて挿入し、スタックから順に取出し $\rightarrow A, C, B$
• 最初に $B$ を出力する場合（$A, B$ と挿入して $B$ を取り出す）
  • スタックに残った $A$ を取出し、$C$ を挿入・取出し $\rightarrow B, A, C$
  • $C$ を挿入・取出し、最後にスタックに残った $A$ を取出し $\rightarrow B, C, A$
• 最初に $C$ を出力する場合（$A, B, C$ をすべて挿入してから順に取り出す）
  • 取出しを続けると、後から入れた順に出力される $\rightarrow C, B, A$

3つのデータを並べる順列は $3! = 6$ 通りありますが、$C, A, B$ という出力順序だけは実現できません。なぜなら、最初に $C$ が出力された時点でスタック内には下から $A, B$ の順でデータが積まれており、次に出力されるのは必ず $B$ となるためです。

したがって、出力可能な順序は5通りとなるため、ウ が正解です。

各選択肢の解説

• ア（3）: 誤りです。出力順序は上記の通り5通り存在します。
• イ（4）: 誤りです。出力順序は上記の通り5通り存在します。
• ウ（5）: 正解です。
• エ（6）: 誤りです。3つのデータ $A, B, C$ のすべての順列（$3! = 6$ 通り）が出力できるわけではなく、$C, A, B$ の順序はスタックの構造上不可能なため6通りにはなりません。