1. ホーム
  2. algorithm

[解決済み] 2つのキューを使用したスタックの実装

2022-04-29 05:30:19

質問

以前、同じような質問がありました。 そこ が、ここでの質問はその逆で、2つのキューをスタックとして使用するものです。 質問は...

2つのキューとその標準的な操作( enqueue , dequeue , isempty , size ) を実装し、スタックとその標準的な操作 ( pop , push , isempty , size ).

があるはずです。 2 のバージョンで解決します。

  • バージョン A : スタックはアイテムをプッシュするときに効率的であるべきである。
  • バージョン B : アイテムのポップアップ時にスタックを効率的に使用するようにしました。

私は、特定の言語の実装よりも、アルゴリズムに興味があります。 しかし、私がよく知っている言語( ジャワ , c# , パイソン , ビブ , ジャバスクリプト , php ).

どのように解決するのですか?

バージョンA(効率的なプッシュ)。

  • を押してください。
    • queue1 に待ち行列を作る
  • ポップ
    • キュー1のサイズが1より大きい間、キュー1からキュー2にデキューされたアイテムをパイプする。
    • queue1 の最後の項目を dequeue して返し、queue1 と queue2 の名前を入れ替える。

バージョンB(効率的なポップ)。

  • を押してください。
    • queue2 に待ち行列を作る
    • queue1 の全アイテムを queue2 に待ち行列させ、queue1 と queue2 の名前を入れ替える。
  • ポップ
    • queue1 から deqeue