algorithm - 实现一个队列，其中push_rear()、pop_front()和get_min()都是常量时间操作

Question

我遇到了这个问题:实现一个队列，其中push_rear()、pop_front()和get_min()都是常量时间操作。

我最初想到使用最小堆数据结构，它的 get_min() 复杂度为 O(1)。但是 push_rear() 和 pop_front() 将是 O(log(n))。

有谁知道实现这种具有 O(1) push()、pop() 和 min() 的队列的最佳方法是什么？

我用谷歌搜索了这个，想指出这个 Algorithm Geeks thread .但似乎没有一个解决方案遵循所有 3 种方法的恒定时间规则:push()、pop() 和 min()。

感谢所有建议。

Answer 1

您可以使用 O(1) pop()、push() 和 get_min() 实现堆栈:只需将当前最小值与每个元素一起存储。因此，例如，堆栈 [4,2,5,1](顶部为 1)变为 [(4,4), (2,2), (5,2) , (1,1)].

然后你可以use two stacks to implement the queue .插入一个堆栈，从另一个堆栈弹出；如果在 pop 期间第二个堆栈为空，则将所有元素从第一个堆栈移动到第二个堆栈。

例如，对于 pop 请求，从第一个堆栈移动所有元素 [(4,4), (2,2), (5,2), (1,1) ]，第二个堆栈将是 [(1,1), (5,1), (2,1), (4,1)]。现在从第二个堆栈返回顶部元素。

要找到队列的最小元素，请查看各个最小堆栈中最小的两个元素，然后取这两个值中的最小值。 (当然，如果其中一个堆栈为空，这里还有一些额外的逻辑，但这并不难解决)。

它将有 O(1) get_min() 和 push() 和摊销 O(1) pop()。