问题描述
我遇到了这样一个问题：实现一个队列，其中push_rear（），pop_front（）和get_min（）都是常量时间的操作。
I came across this question:Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
我最初以为用最小堆数据结构，具有O（1）复杂的get_min的（）。但push_rear（）和pop_front（）是O（日志（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）推（），流行（）和MIN（）？
Does anyone know what would be the best way to implement such a queue which has O(1) push(), pop() and min()?
我GOOGLE了这一点，并希望指出该<一href="http://groups.google.com/group/algogeeks/browse_thread/thread/157129d83d284e07?pli=1">Algorithm极客线程。但似乎没有任何解决方案都遵循了所有3个方法一定的时间规律：推（），流行（）和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）流行（），推（）和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.
例如，对于一个流行的要求，将所有元素从第一个堆栈 [（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（）和推（）和摊销O（1）弹出（）。
It will have O(1) get_min() and push() and amortized O(1) pop().
这篇关于实现一个队列，其中push_rear（），pop_front（）和get_min（）都是固定的时间操作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！