push_rear(), pop_front(), get_min() がすべて定数時間操作となる待ち行列を実装する。

質問

こんな質問を見かけました。 push_rear()、pop_front()、get_min()がすべて定数時間の処理であるキューを実装してください。

私は最初、get_min()のためにO(1)の複雑さを持つmin-heapデータ構造を使用することを考えました。しかし、push_rear() と pop_front() は O(log(n)) となるでしょう。

O(1) push()、pop()、min()を持つそのようなキューを実装する最良の方法は何か、誰か知っていますか？

私はこのことについてググって、これを指摘したいと思いました。 Algorithm Geeks スレッド . しかし、どの解決策も3つのメソッド（push()、pop()、min()）すべてにおいて一定時間のルールに従わないようです。

すべての提案に感謝します。

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

O(1) pop()、push()、get_min()でスタックを実装することができます。は、各要素と一緒に現在の最小値を格納するだけです。つまり、例えばスタック [4,2,5,1] (1 が一番上) は次のようになります。 [(4,4), (2,2), (5,2), (1,1)] .

次に は2つのスタックを使ってキューを実装します。 . 1つのスタックにプッシュし、もう1つのスタックからポップします。ポップ中に2番目のスタックが空になった場合、最初のスタックから2番目のスタックにすべての要素を移動させます。

例えば pop リクエストの場合、最初のスタックからすべての要素を移動して [(4,4), (2,2), (5,2), (1,1)] に移動し、2 番目のスタックには [(1,1), (5,1), (2,1), (4,1)] となり、2つ目のスタックから一番上の要素を返します。

キューの最小要素を見つけるには、個々の min-stacks の最小の 2 つの要素を調べ、その 2 つの値の最小値を取ります。 (もちろん、スタックの1つが空の場合、ここでいくつかの余分なロジックがありますが、それは回避するのがそれほど難しくありません)。

これは O(1) get_min() と push() であり、償却済みO(1) pop() .