スタックの出力順序｜科目A-1（応用情報技術者） 令和7年 春期午前試験 問5
出典：令和7年春期 午前 問5
分野：アルゴリズムとプログラミング ／ データ構造
A，B，Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合，データの出力順序は何通りあるか。
- ア：3
- イ：4
- ウ：5
- エ：6
TSUNAGARU-ADVICE
まず押さえたいこと
スタックは後入れ先出し（LIFO）なので、最後に挿入したデータから取り出されます。この種の問題では、A、B、Cを順に受け取りながら、「挿入する」「取り出す」の操作を組み合わせて、どの出力順序が実現できるかを調べます。
迷ったときの判断軸
入力順とは異なる順序でも出力できますが、スタック内にあるデータを飛び越えて取り出すことはできません。例えば、あるデータの上に後から入れたデータが残っていれば、上のデータを先に取り出さなければならないという制約を意識して、可能な並びを一つずつ確認しましょう。
科目Bにつなげるために
特にプロフェッショナルデジタルスキル（システム）試験合格を目指す方は、スタックを単なる用語ではなく、pushとpopの操作を時系列で追跡できるデータ構造として理解しましょう。式の評価・関数呼出し・再帰処理などのアルゴリズム問題にもつながります。
スタックは、最後に挿入したデータを最初に取り出すLIFO方式です。A・B・Cはこの順に入力されますが、各データを挿入した直後に取り出すか、後のデータを挿入してから取り出すかによって、出力順序が変わります。
可能な出力順序は、次の5通りです。
1．A・B・C
Aを挿入して取り出し、Bを挿入して取り出し、Cを挿入して取り出します。
2．A・C・B
Aを挿入して取り出した後、B・Cの順に挿入し、C・Bの順に取り出します。
3．B・A・C
A・Bの順に挿入し、B・Aの順に取り出した後、Cを挿入して取り出します。
4．B・C・A
A、Bの順に挿入してBを取り出し、Cを挿入して取り出した後、最後にAを取り出します。
5．C・B・A
A・B・Cの順に全て挿入し、C・B・Aの順に取り出します。
一方、C・A・Bという順序は実現できません。Cを最初に出力するにはA、B、Cを全てスタックへ挿入する必要がありますが、Cを取り出した後はBがAより上にあるため、AをBより先に取り出せないからです。
よって、出力順序は5通りです。
したがって、ウが適切です。