私はアルゴリズムの本でこの質問に出会いました（アルゴリズム、第 4 版ロバート・セジウィックとケビン・ウェイン著。
3 つのスタックを持つキュー。各キュー操作が一定数 (最悪の場合) のスタック操作を実行するように、3 つのスタックを持つキューを実装します。警告: 難易度が高いです。
2 スタックのキューを作成する方法はわかっていますが、3 スタックのソリューションが見つかりません。何かアイデアはありますか?
（あ、これは宿題ではありませんよ:)）
ベストアンサー1
まとめ
- O(1)アルゴリズムは6スタックで知られている
- O(1)アルゴリズムは3つのスタックで知られていますが、遅延評価を使用しているため、実際には余分な内部データ構造を持つことになり、解決策にはなりません。
- セジウィック近郊の人々は、元の質問のすべての制約内で3スタックソリューションを認識していないことを確認しました。
詳細
このリンクの背後には 2 つの実装があります。http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html
そのうちの 1 つは 3 つのスタックを持つ O(1) ですが、遅延実行を使用するため、実際には追加の中間データ構造 (クロージャ) が作成されます。
もう 1 つは O(1) ですが、6 つのスタックを使用します。ただし、遅延実行なしで動作します。
更新: 岡崎氏の論文はこちら:http://www.eecs.usma.edu/webs/people/okasaki/jfp95.psそして、遅延評価を持つ O(1) バージョンでは、実際には 2 つのスタックしか使用していないようです。問題は、それが実際には遅延評価に基づいていることです。問題は、それが遅延評価なしの 3 スタック アルゴリズムに変換できるかどうかです。
更新: 別の関連アルゴリズムは、第 7 回コンピューティングと組み合わせ論に関する年次会議で発表された Holger Petersen の論文「Stacks versus Deques」に記載されています。この記事は Google ブックスで見つけることができます。225 ～ 226 ページを確認してください。ただし、このアルゴリズムは実際にはリアルタイム シミュレーションではなく、3 つのスタック上の両端キューの線形時間シミュレーションです。
gusbro: 「@Leonel が数日前に言ったように、Sedgewick 教授に解決法を知っているか、何か間違いがあるか確認するのが公平だと思いました。それで、彼に手紙を書きました。ちょうど返事を受け取ったところです (彼からではなく、プリンストンの同僚からですが)。皆さんと共有したいと思います。彼は基本的に、3 つのスタックとその他の制約 (遅延評価を使用しないなど) を使用するアルゴリズムは知らないと言っていました。ここでの回答を見ると、彼は 6 つのスタックを使用するアルゴリズムを知っていました。ですから、アルゴリズムを見つける (またはアルゴリズムが見つからないことを証明する) ための質問はまだ残っていると思います。」