基本情報技術者問題

質問

平成１６年度春問１２のスタックに関する問題で
A, B, C ,Dの順に到着するデータに対し１つのスタックだけ用いて出力可能なデータ列はどれか

ア、A,D,B,C
イ、B,D,A,C
ウ、C,B,D,A
エ、D,C,A,B

で答えはウでした。解答見ても何言ってるか意味不明なのですが
わかりやすく解説してくださる人いませんか？

回答No.3

codotjtp

『１つのスタックだけ』という箇所の意味が誤解を生みやすいでしょうね。

回答No.2

t-aka

実際にスタックを描いたほうが分かりやすいと思います。

push と pop を組み合わせて取り出すことが可能な組み合わせです。

ア：push A→pop A→push B→push C→push D→pop D→pop C→pop B(A、D、C、Bで取り出す)
イ：push A→push B→pop B→push C→push D→pop D→pop C→pop A(B、D、C、Aで取り出す)
ウ：push A→push B→push C→pop C→pop B→push D→pop D→pop A(C、B、D、Aで取り出す)
エ：push A→push B→push C→push D→pop D→pop C→pop B→pop A(D、C、B、Aで取り出す)

となりウの順番が一致しているのでウが正解です。

たとえば、アの場合だとAの次にDを取り出したいのでAをpopしたあとにDまでpushします。
そうするとDをpopしたあと、次に取り出せるデータはCとなるために、回答と一致しなくなります。
この考えをほかの選択肢にも適用して考えると、ウのみ回答と一致することがわかります。

こんなかんじでしょうか。

回答No.1

jjon-com

ウ のデータ列を取り出すには，
push(A), push(B), push(C), pop(), pop(), push(D), pop(), pop() と操作すればよい。

残りの解答群も試してみてください。

ア は A,D,[C,B]
イ は B,D,[C,A]
エ は D,C,[B,A]

の順でしかスタックからpop()できないのが分かると思います。