平成１６年度の春の問題なんですが

質問

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

回答を見てもどういうことかさっぱりわかりません。
スタックは最後に格納したものから先にとりだせるので
DCBAの順で取り出せると思ったんですが・・CBDAの順のようです。
教えて下さい

回答No.3

edomin7777 · ベストアンサー

この問題は、スタックの深さが規定されていません。
なので、いくらでも入ると考えます。
また、下記の「スルー」はスタックを使用せずそのまま到着、「ポップ」はスタックから取り出し到着するものとします。

データがABCDの順番で到着するとき、
(1)ADBCは
A：スルー
B：プッシュ
C：プッシュ
D：スルー
の順番になりますが、その後でBCの順に取り出せないので×
※取り出すときはCBの順になります。
(2)BDACは
A：プッシュ
B：スルー
C：プッシュ
D：スルー
の順番になりますが、その後でACの順に取り出せないので×
※取り出すときはCAの順になります。
(3)CBDAは
A：プッシュ
B：プッシュ
C：ポップ
B：ポップ
D：スルー
A：ポップ
の順番で取り出せるので○。
(4)DCABは
A：プッシュ
B：プッシュ
C：プッシュ
D：スルー
C：ポップ
の順番になりますが、その後でABの順に取り出せないので×
※取り出すときはBAの順になります。

回答No.5

gookinger

実際に手で書いて、確認はしていますか？

ノートに（縦書きで）、実際に設問の通り（PUSH、POP）
に書いて、よく見て下さい。

スルーは、別に横に書きます。

上からの順番、下からの順番、横の順番・・・・

ピンとくると思います。

回答No.4

seiiiichi

もちろん、質問者さんの言う通りDCBAの順番で取り出すこともできます。

でも、A、B、C、Dと全部入れ終わる前に途中で出すこともできるのです。

A、Bと入れた段階でB、Aと取り出し、その後
C、Dと入れてからD、Cと取り出せばBADCとなります。

回答の場合だと
A、B、Cと入れてC、Bを取り出す。（Aは残ったまま）
Dを入れてDを取り出し、残ってたAを取り出す。
とやると、CBDAの順番になります。

それ以外の選択肢のような取り出し方はやってみるとわかりますが
どうやってもできません。

回答No.2

bin-chan

基本情報の問12ですね。

> DCBAの順で取り出せると思ったんですが・・C
すべてをスタックに積み上げてありそのまま取り出せばその通りです。
この問題では、Ｄはスタックに積み上げ「無い」ことで、そのまま出力されてる、ということ。
残るＡ・Ｂ・Ｃは、到着順に積み上げられているからこそ、Ｃ・Ｂ・Ａの順で取り出せる。

かな。

回答No.1

bin-chan

種別は何ですか？基本情報？

補足

基本情報です