令和3年度 春期 ITストラテジスト試験 システムアーキテクト試験 ネットワークスペシャリスト試験 ITサービスマネージャ試験 情報処理安全確保支援士試験 午前Ⅰ 問題【共通】 問2

スタックは LIFO (Last-In First-Out: 後入れ先出し) のデータ構造です。図表 bb_3_2 に示されるように、上部の一方向からしかデータの出し入れができず、最後に挿入したデータから順に取り出されます。
入力データ A, B, C がこの順序で与えられるとき、「スタックへの挿入（プッシュ）」と「スタックからの取出し（ポップ）」のタイミングの組み合わせによって、出力されるデータの順序が変わります。

挿入と取出しをそれぞれ1回ずつ行う場合、可能な出力順序は以下の 5通り です。

1. A, B, C の順に出力
   • Aを挿入 → Aを取出し(出力:A) → Bを挿入 → Bを取出し(出力:B) → Cを挿入 → Cを取出し(出力:C)
2. A, C, B の順に出力
   • Aを挿入 → Aを取出し(出力:A) → Bを挿入 → Cを挿入 → Cを取出し(出力:C) → Bを取出し(出力:B)
3. B, A, C の順に出力
   • Aを挿入 → Bを挿入 → Bを取出し(出力:B) → Aを取出し(出力:A) → Cを挿入 → Cを取出し(出力:C)
4. B, C, A の順に出力
   • Aを挿入 → Bを挿入 → Bを取出し(出力:B) → Cを挿入 → Cを取出し(出力:C) → Aを取出し(出力:A)
5. C, B, A の順に出力
   • Aを挿入 → Bを挿入 → Cを挿入 → Cを取出し(出力:C) → Bを取出し(出力:B) → Aを取出し(出力:A)

残る1つの並び方である C, A, B の順での出力は、スタックの性質上不可能です。なぜなら、最初に C を取り出すためには、その前に A と B をスタックに挿入しておく必要があり、その時点でのスタック内の状態は上から順に B, A となります。そのため、C を取り出した直後に取り出せるデータは必ずスタックの先頭にある B となり、A を先に取り出すことはできないからです。

したがって、可能な出力順序は5通りとなります。

各選択肢の解説

• ア: 誤り。可能な出力順序は3通りよりも多く存在します。
• イ: 誤り。可能な出力順序は4通りよりも多く存在します。
• ウ: 正解。可能な出力順序は全部で5通りです。
• エ: 誤り。3つのデータの順列は $3! = 6$ 通りですが、上記の通り「C, A, B」の順序での出力が不可能なため、6通りすべてを出力することはできません。