我只是想知道，是否有可能为get_min(), push_back(), push_front(), pop_back(), pop_front()操作实现一个具有O(1)复杂性(常量/摊销无关紧要(的结构(list/deque(？
肯定可以实现满足这些条件的堆栈甚至队列(对它们来说，push()和pop()仅对一端可用(。但我无法将这种逻辑重用到出列的情况中。
还可以创建对于推送/弹出具有O(logn)复杂度、对于get_min具有O(1)复杂度的结构(仅使用简单列表和min_heap，其中可以删除O(logn)的任意元素(。
但对我来说，仍然为所有操作摊销O(1)似乎是不可能的。如果是这样的话，关于操作的确切数量(或列表中元素的最大可能数量(n的信息能帮助(更简单的情况(吗？我们能以某种方式使用O(n)(甚至更多(额外的内存或类似的smth吗？
确实可以构建一个最小deque，其中前推、后推和查找最小运算在最坏情况下的时间O(1(内工作，而前推和后推运算占用摊销时间O(2(。我所知道的最简单的路线是这样的：
- 首先，制作一个支持push、pop和find min in time O(1(的堆栈。我们将以此为基础
- 使用从三个堆栈构建deque的构造，除了使用这些最小堆栈而不是常规堆栈。然后，您可以通过查询三个堆栈中的每个堆栈的最小元素并返回这些值中的最小值来实现find-min操作
如果您还没有看到如何执行步骤(2(，那么这个想法是如何从两个堆栈生成队列的概括。您维护两个表示deque元素的堆栈，这样一个堆栈以相反的顺序表示deque的前面(堆栈顶部是deque的前部，较深的元素是deque下一个元素(，另一个堆栈的元素表示deque后面(顶部元素是deque最后一个元素，较深元素在deque中向后(。例如，这里有一种方法来编码deque 1，2，3。。。，10:
front: | 7 6 5 4 3 2 1
back: | 8 9 10
要推到deque的前面或后面，只需推到合适的deque上即可。要弹出deque的前面或后面，如果相应的堆栈不是空的，只需从中弹出即可。否则，如果堆栈是空的，则需要将另一个堆栈中的一些元素移到上面。具体来说，为了保持两个堆栈之间的平衡，您可以进行一系列的推送和弹出操作，将一半的元素放入两个堆栈中。看起来是这样的：
- 从另一个堆栈中弹出一半元素，并将它们推到临时堆栈中
- 从另一个堆栈中弹出其余元素，并将它们推到空堆栈上
- 从临时堆栈中弹出元素，然后将它们推回到另一个堆栈中
您可以使用一个潜在的自变量(请参阅Φ，它是两个堆栈高度差的绝对值(来显示每个操作需要摊销时间O(1(。
使用某种调度方案，可能会以某种方式将每次操作的O(1(时间加快到最坏的情况，但我不知道如何做到这一点。我知道有一种方法可以实现一个具有四个堆栈的队列，每个操作的最坏情况为O(1(，所以也许这个想法可以推广到这里？