问题描述
我遇到这个问题：
实现一个队列，其中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)).
有谁知道实现这样一个队列的最佳方式是什么？ （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()?
我google了这个，并想指出这个。但是似乎没有一个解决方案遵循所有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（） code>。
It will have O(1) get_min() and push() and amortized O(1) pop().
这篇关于实现一个队列，其中push_rear（），pop_front（）和get_min（）都是常量时间操作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！