0

n個の要素を含むキューがあり、前面はにあり0ます。これらの数字のスタックを0一番上に作成する必要があります。

これは、 EnQueue、DeQueue、Push、Pop、およびコンスタントストレージでのみ実行できます。この問題にどのように取り組むことができるかという考えほど、答えは必要ありません。

私のためにこれに答えないでください、しかしただ私がプログラミングに不慣れであり、これができる方法のアイデアを使うことができることを理解するようにしてください。

  • それはハノイの塔のようなアプローチですか？
  • それは一定のストレージのみを使用しますか？

これは宿題ではありません。進め方についてアドバイスが必要です。私の最初のアイデアは、キューを逆にしてからプッシュすることはうまくいきませんでした。私は他の状況を無駄にスケッチしてみました。次に、それらすべてをデキューしてプッシュし、次にそれらすべてをポップしてエンキューし、次にデキューして再度プッシュするかどうか疑問に思いました。

  • これは効率的ですか？
  • これは一定のストレージを使用しますか？

私はまだ基​​本的なプログラミングの概念を学んでいます。よろしくお願いします！:)

4

2 に答える 2

4

キューからすべてをデキューし、各要素をすぐにスタックにプッシュします。次に、スタックからすべてをポップし、すぐにキューに入れます。現在キューには何がありますか？

キューとスタックが固定サイズのアイテムを保持していると仮定すると、上記のahemサブルーチンは、一定の追加ストレージのみを使用します。各アイテムがキューからスタックに、またはその逆に移動するときに、1つのアイテムのストレージのみが必要です。

編集：あなたが指摘するように、私のサブルーチンはキューの内容を逆にします。そうすれば、キューをスタックに再度排出して、目的の結果を得るのは非常に簡単です。

そして、あなたが指摘するように、これは3n = O(n)アイテムを転送する必要があります。ここnで、はキューの初期サイズです。もっと上手くできますか？私はそうは思わない、あるいは少なくとも重要ではない。ある意味では、カウンター（O(log n) > O(1)追加のストレージを必要とする）さえなければ、実行する唯一の合理的なことは、キューをスタックに排出すること、またはその逆です。

于 2012-07-14T06:22:10.570 に答える
3

私は何に直面していますか？

あなたが直面している最大の問題は、2つのコンテナが互いに直接互換性がないことです。

キューは通常FIFO1コンテナですが、スタックはLIFO2です。これは、キューからスタックにデータを順番にコピーすることはできないことを意味します。これにより、要素が「間違った」順序で表示されるためです（説明に従って）。

もう1つの問題は、キューを元に戻すための（パフォーマンス面での）良い方法がないことです。キューは一方向のコンテナであり、内部的には、要素は前の要素ではなく、行の次の要素についてのみ知る必要があります。これは、キューの後ろから反復することはできず、反復は常にO（n）であることを意味します。

同じ問題がスタックにもあります。

前に説明したことをまとめると、これは非常に退屈な問題になりますが、解決策はありますが、必ずしも最も簡単であるとは限りません。

この問題を解決するためのヒント。

要素を格納するために何らかの中間状態が必要になりますか、それともコンテナのLIFO / FIFOプロパティを有利に使用できますか？

以下はあなたが望むことをする実装です、あなたがあなたの質問への答えを知りたくないならば、この灰色の領域の上にマウスを置いてはいけません。

あるコンテナから別のコンテナへのコピー中に追加の要素用のスペースが割り当てられるため、追加のストレージが必要になります。ストレージは一定ですが、これは避けられません。

コピーの初期化は、右辺値参照を使用して最適化し、C++11で移動できることを忘れないでください。

スポイラー内でシンタックスハイライトが機能しているようには見えません。

サンプルの実装は ここにあります。 キューがFIFOおよびスタックLIFOで

あるという事実を利用して、データキューをスタックにコピーし、次にスタックからキューに、最後に再びキューにスタックすることにより、説明に一致する方法で要素の順序を効果的に逆にしました。

脚注1.FIFO =先入れ先出し2.LIFO =後入れ先出し
   
   

于 2012-07-14T06:32:16.023 に答える