实现一个队列，其中push_rear（），pop_front（）和get_min（）都是常量时间操作

Question

实现一个队列，其中push_rear（），pop_front（）和get_min（）都是常量时间操作

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

我最初想过使用一个最小堆数据结构，它对于get_min（）具有O（1）复杂度。但是push_rear（）和pop_front（）将是O（log（n））。

有谁知道实现这样一个有O（1）push（），pop（）和min（）的队列的最佳方法是什么？

我搜索了这个，并想指出这个算法极客线程。但似乎没有一个解决方案遵循所有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)]。然后，您可以使用两个堆栈来实现队列。推到一个堆栈，从另一个堆栈弹出; 如果第二个堆栈在弹出期间为空，则将所有元素从第一个堆栈移动到第二个堆栈。例如，对于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()。