みんなの「教えて(疑問・質問)」にみんなで「答える」Q&Aコミュニティ

こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

キューとスタックの問題です、宜しくお願いします

 (多分基本情報処理に関する問題だと思うのですが)データ構造に関する問題です、いくら考えても分かりません、宜しくお願いします。

【問】空の状態のキューとスタックの二つのデータ構造がある。
次の手続きを順に実行した場合、変数xに代入されるデータはどれか。
ここで、
・データyをスタックに挿入することをpush(y)
・スタックからデータを取り出すことをpop( )
・データyをキューに挿入することをenq(y)
・キューからデータを取り出すことをdeq( )
と表す。
(1)push(a)
(2)push (b)
(3)enq(pop( ))
(4)enq(c)
(5)push(d)
(6)push(dep( ))
(7)pop( ) → x

以上の答えとして(6)にはbがスタックにpushされるので、後入れ先出し
を考えると当然「xにはb」が入るはずなのですが、どうも答えは「d」となっています。
「d」は「b」より前にスタックされてますので、最新で取出される情報は「b」しかないと思うのですが、誰か誤りを指摘してください、宜しくお願いします。

投稿日時 - 2007-08-05 19:37:50

QNo.3230210

すぐに回答ほしいです

質問者が選んだベストアンサー

> スタックは、後入れ先出し
> スタックは、後入れ後出し
もちろん、後入れ咲き出しですね。

depがdeqだとすると答えはおっしゃるとおりdですね。
depが正しいとするとこれはノーゲームですね。
depをスキップすると確かにdですが。
通常の処理系なら7)までたどり着かないでしょう。

投稿日時 - 2007-08-05 20:45:58

補足

ステップを踏んでいくと以下の状態になるのではないでしょうか?

(1)push(a)
   スタック a    キュー
(2)push(b)
   スタック a,b   キュー
(3)enq(pop())
   スタック a    キュー b
(4)enq(c)
   スタック a    キュー b,c
(5)push(d)
   スタック a,d   キュー b,c
(6)push(deq())
   スタック a,d,b   キュー c
(7)pop() → x

 ∴ x=b (一番最後に入れたものが最初に取出される(後入れ先出しの原理))

投稿日時 - 2007-08-05 21:18:44

このQ&Aは役に立ちましたか?

1人が「このQ&Aが役に立った」と投票しています

回答(7)

ANo.7

makohyuです。

申し訳ありませんが、私がこれ以上回答できることはありません。

質問、補足になんどもご友人がこういっている、・・・らしい、・・・聞いている、と不確定な情報ばかりです。

htgoさんが、この質問についての納得のいく回答を得たいのでしたら、質問の内容を精査し、あらためて質問をたてられることをお薦めいたします。

お役に立てず、すみませんでした。

投稿日時 - 2007-08-06 08:40:47

ANo.6

makohyuです。

> どうももう一つ腑に落ちないのですが。
腑に落ちないとは、どういった点ですか?
わかりやすく、説明してください。

投稿日時 - 2007-08-05 23:25:56

お礼

>話を戻すと、「この問題は間違ってる」が私の回答です。
というところです。

それと、どうも答えは「d」であるらしいと友人から聞いている事です。

投稿日時 - 2007-08-06 00:10:59

ANo.5

#1,#3のmakohyuです。

>⇒ これは私が投稿する際のミスプリです。
あらら~、そうなんですか?
てっきりそういう設問だと思いました。

だとすると、単純に設問が間違ってるのでは?

このあいだに、「そういう設問」だとして、次の回答をせっかく書いてみたので読んでみてください。

=======================================
ご理解のために、この設問の意図を想像してみました。

出題者は、この設問の答えによって、

1) b と回答
 おしい。しかし、学んだことは理解している。

2) b,d 以外の回答
 おいおい、もう少しがんばりましょう!

3) d と回答
 正解! よくぞ私の与えた矛盾に耐えた。

dep() の p に気がついて、これでは動かない、けど、「変数xに代入されるデータはどれか」という矛盾。

矛盾に耐えて答えを出せ! という意図なのだと思います。

================================================
深読みしすぎました^^;

お茶目な出題者だな~、と。

話を戻すと、「この問題は間違ってる」が私の回答です。

投稿日時 - 2007-08-05 22:26:52

お礼

makohyuさん、有難う御座います。

 ⇒ と言うことは、「(6)push(deq( ))」なら、答えは「b」で良いのでしょうか。
   どうももう一つ腑に落ちないのですが。

投稿日時 - 2007-08-05 22:48:44

ANo.4

No.2です。

> ∴ x=b (一番最後に入れたものが最初に取出される(後入れ先出しの原理))
pがqの転記ミスということで有ればその通りです。
私もbをdと転記ミスしてました。すみません。

投稿日時 - 2007-08-05 21:57:01

ANo.3

makohyuです。

編集ミスです。謹んで訂正いたします。

>⇒ということなら、(3)enq(pop( ))もなにもしないということですか?
>そうじゃないですよね?「b」をスタックから取出し、キューに入れていますよね。
そのとおりです。

確認なのですが、
>(6) のdep() は(6) のdeq()の間違いです。
とは、もともとの問題がそう書いてあるという意味ですか?

そうだとすると、
#2の方もおっしゃってましたが、この問題はペーパーに書かれた設問なので実際の処理は考慮しないという、昔からよくある設問なのではないでしょうか。

ですから、「スペルミスを見つけられるかというデバッグの力を問われている設問」と説明したのです。

>多分基本情報処理に関する問題だと思うのですが
「多分」、のあたりでこの辺かな? と思ったしだいです。
実際のコンピュータのメモリを対象にしている設問なら、「多分」とは書かれないはずですから。。。

投稿日時 - 2007-08-05 21:47:23

お礼

makohyuさん、有難う御座います。

>多分基本情報処理に関する問題だと思うのですが
⇒ 私も友人に聞かれたのですが、どうも答えは「d」のようです。
 その友人も答えは「b」になると言ってますので、私に確認を求めてきたのです。

>(6) のdep() は(6) のdeq()の間違いです。
⇒ これは私が投稿する際のミスプリです。

以上ステップを追って行くと「b」が正解と思われるのですが、皆様方の回答なり考え方はどのようなものでしょうか、宜しくお願いします。

投稿日時 - 2007-08-05 22:03:00

ANo.1

スタックは、後入れ後出しです。

(1)push(a)
   スタック a    キュー
(2)push(b)
   スタック a,b   キュー
(3)enq(pop())
   スタック a    キュー b
(4)enq(c)
   スタック a    キュー b,c
(5)push(d)
   スタック a,d   キュー b,c
(6)push(dep())
   スタック a,d   キュー b,c
(7)pop() → x

(6) のdep() がスペルミスでなければ、X は d になりますけど。。。

dep()は定義されていないので、何もしない、データは動いていないというわけではないですか?
スペルミスを見つけられるかというデバッグの力を問われている設問ですかね。

投稿日時 - 2007-08-05 20:12:47

お礼

makohyuさん、有難うございます。
(6) のdep() は(6) のdeq()の間違いです。

>スタックは、後入れ後出しです。
⇒スタックは、後入れ先出しではないのですか。一体どこで定義されているのですか?私の見ている参考書では「Last In First Out」と定義されていますが?

>deq()は定義されていないので、何もしない、データは動いていないというわけではないですか?
⇒ということなら、(3)enq(pop( ))もなにもしないということですか?
そうじゃないですよね?「b」をスタックから取出し、キューに入れていますよね。

makohyuさんの回答では、(6)は何も処理行為を実行していませんが、これは何故ですか。これはキューからbを取出し、スタックに入れるという行為だと思うのですが、全くここが理解できません。
宜しくお願いします。

投稿日時 - 2007-08-05 20:53:33

あなたにオススメの質問