实现一个队列，其中 push_rear()、pop_front() 和 get_min() 都是常量时间操作 [英] Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations

问题描述

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

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

I initially thought of using a min-heap data structure which has O(1) complexity for a get_min(). But push_rear() and pop_front() would be O(log(n)).

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

Does anyone know what would be the best way to implement such a queue which has O(1) push(), pop() and min()?

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

I googled about this, and wanted to point out this Algorithm Geeks thread. But it seems that none of the solutions follow constant time rule for all 3 methods: push(), pop() and min().

感谢所有建议.

推荐答案

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

You can implement a stack with O(1) pop(), push() and get_min(): just store the current minimum together with each element. So, for example, the stack [4,2,5,1] (1 on top) becomes [(4,4), (2,2), (5,2), (1,1)].

那你就可以使用两个栈来实现队列.压入一个堆栈，从另一个堆栈弹出；如果弹出时第二个堆栈为空，则将第一个堆栈中的所有元素移至第二个堆栈.

Then you can use two stacks to implement the queue. Push to one stack, pop from another one; if the second stack is empty during the pop, move all elements from the first stack to the second one.

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

E.g for a pop request, moving all the elements from first stack [(4,4), (2,2), (5,2), (1,1)], the second stack would be [(1,1), (5,1), (2,1), (4,1)]. and now return top element from second stack.

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

To find the minimum element of the queue, look at the smallest two elements of the individual min-stacks, then take the minimum of those two values. (Of course, there's some extra logic here is case one of the stacks is empty, but that's not too hard to work around).

它将有 O(1) get_min() 和 push() 并且摊销 O(1) pop().

It will have O(1) get_min() and push() and amortized O(1) pop().

这篇关于实现一个队列，其中 push_rear()、pop_front() 和 get_min() 都是常量时间操作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！