从队列中获取 O（1） 时间中的最小值/最大值？[已关闭]

存在这样一个结构，它的作用类似于队列，但允许您在恒定时间内检索最小值/最大值，实际上不是严格恒定值，它是摊销的常量时间（您可以猜测命名为最小/最大队列）。有两种实现它的方法 - 使用两个堆栈或使用队列和deque。

Deque 实现看起来更不像这样（与语言无关）：

所以我们有一个max元素的deque，前面的那个是所需的max，还有一个标准队列。

推送操作

1. 如果队列为空，只需将元素同时推送到队列和 deque 上即可。
2. 如果队列不为空，则将元素推送到队列上，从 deque 的后面删除所有严格小于我们现在推送的元素（它们肯定不是最大值，因为推送的元素更大，将在队列中持续更长时间），并将当前元素推到 deque 的背面

删除操作

1. 如果 deque 的前部等于队列的前部，则弹出两者（从前面弹出 deque）
2. 如果 deque 的前面不等于队列的前面，则只弹出队列，poped 元素肯定不是最大的元素。

获取最大值

1. 它只是德克的第一个元素。

（应该添加许多参数以明确它为什么有效，但下面介绍的第二个版本可能是对这种必要性的答案）

Stack的实现非常相似，我认为它的实现时间可能有点长，但可能更容易掌握。首先要注意的是，很容易将最大元素存储在堆栈中 - 易于练习（对于懒惰的人 - 使用find-min/find-max的堆栈比O（n）更有效？第二部分，如果第一次看到，可能有点棘手，是使用两个堆栈实现队列非常容易，可以在这里找到 - 如何使用两个堆栈实现队列？ 。基本上就是这样 - 如果我们能得到两个堆栈的最大元素，我们就可以得到整个队列的最大元素（如果你想要一个更正式的论证，取最大值是结合或类似的东西，但我敢打赌你没有，这真的是显而易见的）。

最小版本是类比完成的。

在O（nlogn）时间内，一切都可以使用集合（或类似的东西）来完成，但这是毫无意义的，因为O（n）中的常量真的很小，它应该更快，但易于实现。

第一版中不有趣的部分：

希望我能帮上一点忙。希望没有说错什么。如果需要，可以在C++ / C中给出一个简单的实现。非常感谢您对表格的任何反馈，因为这是我第一个这种类型的帖子，:)（英语不是我的母语）。此外，对正确性的一些确认会很棒。

编辑：由于这个答案让我得到了一些要点，我觉得有必要清理一下，也延长一点。

您只有 2 种方法可以获得最小/最大操作的 O（1）：

• 如果结构已排序，并且您知道最大值/最小值的位置
• 如果结构未排序且仅允许插入：则可以在每次插入项目时重新计算最小值/最大值并单独存储值
• 如果结构没有排序并允许插入和删除：我认为你不能比O（n）做得更好，除非你使用多个集合（但该解决方案不支持删除任何元素，只支持头部/尾部元素，队列应该是这种情况）。