如何获取队列的最小值和最大值？

Question

你能设计一个像队列一样包含“入队”、“出队”、“最小值”和“最大值”的数据结构吗？ 我知道一种使用 2 个堆栈创建队列来分别查找最小值和最大值的方法，但如何同时获取两者？

谢谢

Answer 1

使用标准容器，像

std::set

这样的完全有序的数据结构将提供对两个极值的访问，例如使用

*s.begin()

和

*s.rbegin()

。如果您有多个具有相同优先级的对象，您可能希望以任意方式打破联系，或者使用

std::multiset

来代替。

大多数实现可能会使用某种形式的“红黑树”来实现这样的集合。由于数据结构始终保持排序，因此渐近性能可能比常规单端基于堆的优先级队列所提供的性能更差，但对于许多应用程序来说，差异并不重要，因此应该避免实现自定义数据结构的努力。

Answer 2

C++ STL

#include<queue>

优先级队列通常是通过二叉堆实现的。但它不能同时保持最大值和最小值。 @_@

也许平衡搜索树，比如 AVL、Splay 或红黑树应该是更好的选择。

Answer 3

堆结构

来实现优先级队列。有一种称为“最小-最大堆”的变体，它允许恒定时间访问最大和最小元素。已经有“一个问题”要求 C++ 实现这样的最小-最大堆。它的答案应该对您也有用。 Paul Dixon的这个评论

首先提到了最小-最大堆，而

Chris Mansley的这个评论指出了Stack Overflow上的实现问题。 数据结构是一种众所周知的结构，称为优先级队列。 队列中的每个元素都有一个关联的优先级，并且队列保持从高到低的排序顺序。 队列中的每个元素都必须带有优先级，并且代码必须维护顺序契约。

Answer 4

您可以同时存储最小堆栈和最大堆栈 - 每个堆栈依此类推。这就是胜利。您还可以使用两个牌组和一个队列来实现。 推入队列：我们推入正常的队列，从一副最小值的开头开始，我们删除比我们放入的元素大的元素（可能是这副牌的所有元素）。然后我们将元素放在牌组的开头。 从队列中弹出：查看我们的元素是否等于牌组中的最小值（并且最小值始终位于牌组的末尾）。如果相等，那么我们也将其从牌组中删除，否则我们将其保留。 与最大值相同。