基本情報技術者試験令和元年度秋季午前問8 - A型システムエンジニアの勉強メモ

スタック（データ構造）についての問題。

--------------------------

令和元年度秋期午前問8

A, C, K, S, T の順に文字が入力される。スタックを利用して、S, T, A, C, K という順に文字を出力するために、最小限必要となるスタックは何個か。ここで、どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また、スタック間の文字の移動は行わない。

ア　1

イ　2

ウ　3

エ　4

--------------------------

解説

スタックについてはこちらの問題で（雑な）絵とともに説明している。

スタックは先に入れたデータほど後に取り出されるデータ構造である。

この方式は LIFO（Last In First Out）と呼ばれる。

Last In（最後に入れたもの）が First Out（最初に取り出される）。

なので、一つのスタックに連続して文字を入力（プッシュ）すると、取り出す（ポップ）ときは逆の順序になる。

スタックの数が少ない選択肢から考えてみる。

スタックが 1 個の場合（選択肢ア）

最初にポップ操作で出力したい文字は "S" なので、"S" が入力されるまでの "A, C, K" はスタックに溜めておく必要がある。ということで、"A, C, K" は全てプッシュして同じスタックに入力することになる。
次に "S" がプッシュされた後すぐにポップ、その次に "T" がプッシュされた後すぐにポップ、とすれば "S, T" までは欲しい順序で出力できる。
しかし、その後のポップ操作で出力されるのは "K, C, A" となってしまう（"A, C, K" の順で同じスタックに入力しているので、逆の順序でしか取り出せない）。

スタックが 2 個の場合（選択肢イ）

スタックが 1 個の場合を反省すると、"S" が入力されるまでの "A, C, K" は 3 文字とも別々のスタックに入力する必要があることが分かる。
上の理由は、"A, C, K" の 3 文字だけに着目すると、入力される順序も、欲しい出力の順序も同じであるためである。同じスタックに入力してしまうと順序が逆転して出力されてしまい、欲しい文字列の順序にならなくなってしまう。
ということで、スタックが 2 個の場合は "S" が入力されるまでの "A, C, K" を別のスタックに入力しておくことができないので不正解となる。

スタックが 3 個の場合（選択肢ウ）