平成22年度 秋期 基本情報技術者試験 午前 問5
テクノロジ／アルゴリズムA，B，C，Dの順に到着するデータに対して，一つのスタックだけを用いて出力可能なデータ列はどれか。
出典：平成22年度 秋期 基本情報技術者試験 午前 問5
- アA, D, B, C
- イB, D, A, C
- ウC, B, D, A
- エD, C, A, B
正解：ウ
解説
スタックは後入れ先出し（LIFO）の構造なので，到着順A，B，C，Dのデータをどこでpush（押込み）とpop（取出し）に区切るかによって，出力できる順序が決まります。C，B，D，Aの場合，A，B，Cの順にpushしてからC，Bの順にpopし，続けてDをpushしてすぐpopし，最後に残ったAをpopすれば実現できます。他の選択肢は，出力しようとした時点でスタックの先頭に別のデータが残っており，LIFOの規則に反してしまいます。
選択肢ごとの解説
- ア誤り。Aを最初に出力した後B，Cをpushすると，スタックの先頭はCになるため，次にBを出力することができません。
- イ誤り。Bを出力するにはAをpush済みである必要があり，その後Dを出力するにはCもpushしている必要がありますが，そうするとスタックの先頭はCとなり，次にAを出力できません。
- ウ正しい。A，B，Cの順にpushしてC，Bの順にpopし，続けてDをpushしてすぐpopし，最後に残ったAをpopすれば，この順序を実現できます。
- エ誤り。Dを最初に出力するにはA〜Dをすべてpushしている必要があり，その後Cを出力するとスタックの先頭はBになるため，次にAを出力できません。