問題6
A,B,Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合、データの出力順序は何通りあるか。
| ア | 3 |
| イ | 4 |
| ウ | 5 |
| エ | 6 |
解答・解説を見る
解答：ウ
スタックとは、ある場所に格納したデータを、新しく格納した順に取り出すようにする方式。一番古く格納されたデータが一番最後に取り出される、LIFO（Last In, First Out：後入れ先出し）型のバッファのことである。
出力順序を考えると次の6つの組み合わせがある。
| ○ | A→B→C | AをPush→AをPop→BをPusu→BをPop→CをPop→CをPop |
| ○ | A→C→B | AをPush→AをPop→BをPusu→CをPush→CをPop→BをPop |
| ○ | B→A→C | AをPush→BをPush→BをPop→AをPop→CをPush→CをPop |
| ○ | B→C→A | AをPush→BをPush→BをPop→CをPush→CをPop→AをPop |
| × | C→A→B | AをPush→BをPush→CをPusu→CをPop ※Bを取出さずにその下のAを取り出すことができない。 |
| ○ | C→B→A | AをPush→BをPush→CをPusu→CをPop→BをPop→AをPop |
よって、C→A→Bを除く5通りの出力が存在する。