[解決済み] 3つのスタックを持つ待ち行列を実装するには？

質問

あるアルゴリズムの本で、こんな質問を見かけました。 アルゴリズム 第4版 by Robert Sedgewick and Kevin Wayne)で見つけました。

3つのスタックを持つキュー 3つのスタックを持つキューを実装し、各キューの操作にかかるスタック操作の数が一定（最悪ケース）になるようにします。警告：難易度が高いです。

2つのスタックを持つ待ち行列を作る方法は知っているのですが、3つのスタックを持つ解答が見つかりません。何かアイデアはありますか？

(あ、これは宿題ではありません :) )

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

概要

• 6個のスタックに対してO(1)のアルゴリズムが知られている
• 3つのスタックに対してO(1)のアルゴリズムが知られているが、遅延評価を用いており、これは実際には余分な内部データ構造を持つことに相当するため、解決策にはならない。
• Sedgewick の近くにいる人々は、元の質問のすべての制約の範囲内で 3 つのスタックのソリューションを知らないことを確認しました。

詳細情報

このリンクには、2つの実装があります。 http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html

そのうちの1つは3つのスタックでO(1)ですが、遅延実行を使用しており、実際には余分な中間データ構造(クロージャ)を生成します。

もうひとつはO(1)ですが、SIXスタックを使用します。しかし、これは遅延実行なしで動作します。

UPDATE: 岡崎の論文はこちらです。 http://www.eecs.usma.edu/webs/people/okasaki/jfp95.ps で、遅延評価ありのO(1)版では実際には2スタックしか使っていないようです。問題は、それが本当に遅延評価に基づいているかどうかです。問題は、それが遅延評価なしの3スタックアルゴリズムに変換できるかどうかです。

UPDATE: 別の関連するアルゴリズムは、7th Annual Conference on Computing and Combinatoricsに掲載されたHolger Petersenによる論文 "Stacks versus Deques" で説明されています。この論文はGoogleブックスで見ることができる。225-226ページをご覧ください。しかし、このアルゴリズムはリアルタイムシミュレーションではなく、3つのスタック上のダブルエンド待ち行列の線形時間シミュレーションです。

gusbro: 数日前に @Leonel が言ったように、Sedgewick 教授が解決策を知っているか、あるいは何かの間違いかどうかを確認するのがフェアだと思ったのです。そこで私は彼に手紙を書きました。彼は基本的に、3つのスタックと課された他の制約（遅延評価を使わないなど）を使ったアルゴリズムは知らないと言っていました。彼は、6個のスタックを使うアルゴリズムは知っていました。だから私は、問題はまだアルゴリズムを見つける（または1つが見つからないことを証明する）ために開いていると思います。