A,C,K,S,Tの順に文字が入力される。スタックを利用して,S,T,A,C,Kという順に文字を出力するために,最小限必要となるスタックは何個か。ここで,どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また,スタック間の文字の移動は行わない。
- 1
- 2
- 3
- 4
解答
ウ
解説
スタックは、先入れ後出し(後入れ先出し)でデータを格納するものです。
スタックが1個の場合、次のような操作が考えられますが、Aがポップできません。
① | ② | ③ | ④ | |||
S | T | |||||
K | K | K | K | |||
C | C | C | C | |||
A | A | A | A |
スタックが2個の場合、次のような操作が考えられますが、Cがポップできません。
① | ② | ③ | ④ | ⑤ | |||||||||
S | K | K | T | K | K | K | |||||||
A | C | A | C | A | C | A | C | C |
スタックが3個の場合、次のように操作することで、全てを指定の順番通りにポップできます。
① | ② | ③ | ④ | ⑤ | ⑥ | |||||||||||||||||
S | T | T | ||||||||||||||||||||
A | C | K | A | C | K | A | C | K | C | K | K |
したがって、正解はウ(3)になります。
参考情報
分野・分類
分野 | テクノロジ系 |
大分類 | 基礎理論 |
中分類 | アルゴリズムとプログラミング |
小分類 | データ構造 |
出題歴
- FE 令和元年度秋期 問8