正解は ウ です。 A, B, C の順にしか入れられず、取り出せるのはスタックの一番上だけです。6通りの並び（3!）それぞれについて、push と pop の手順が作れるかを確かめます。 出力順 操作の手順（入＝push、出＝pop） 可否 A B C A入 A出 B入 B出 C入 C出 ○ A C B A入 A出 B入 C入 C出 B出 ○ B A C A入 B入 B出 A出 C入 C出 ○ B C A A入 B入 B出 C入 C出 A出 ○ C B A A入 B入 C入 C出 B出 A出 ○ C A B C を出す時点で A の上に B が積まれている × C を最初に出すには A, B を入れたままにする必要があり、そのとき一番上は B です。したがって C の次に A は出せず、CAB だけが作れません。6−1＝5通りです（n 個のときの数はカタラン数と呼ばれ、n＝3 で5）。 作れない並びを3通りと考えた値です。実際に作れないのは CAB だけです。 C で始まる並び（CBA, CAB）を両方不可と考えた値です。CBA は作れます。 3個の並べ方すべて（3!＝6）です。CAB はスタックでは作れません。