我想实现一个具有以下约束的双端优先级队列：
需要在固定大小的数组中实现..比如说100个元素..如果数组满后需要添加新元素，则需要删除最旧的元素
需要 O(1) 中的最大值和最小值
如果可能，插入 O(1)
如果可能，删除 O(1) 中的最小值
如果可能，在 O(1) 中清除为空/初始化状态
以 O(1) 计算当前数组中的元素数
对于以上 5 个操作，我希望 O(1)，但在同一实现中不可能对所有操作都使用 O(1)。至少 3 个操作的 O(1) 和其他 2 个操作的 O(log(n)) 就足够了。
如果可以为这样的实现提供任何指针，将不胜感激。
为此有许多专门的数据结构。一种简单的数据结构是最小-最大堆，它被实现为二进制堆，其中层在“最小层”（每个节点小于或等于其后代）和“最大层”（每个节点大于或等于它的后代。）最小值和最大值可以在 O(1) 时间内找到，并且与标准二叉堆一样，入队和出队可以在 O(log n) 时间内完成。
您还可以使用间隔堆数据结构，这是任务的另一种专用优先级队列。
或者，您可以使用两个优先级队列——一个以升序存储元素，一个以降序存储元素。每当您插入一个值时，您都可以将元素插入两个优先级队列，并让每个队列存储一个指向另一个队列的指针。然后，每当您将最小值或最大值出列时，您都可以从另一个堆中删除相应的元素。
作为另一种选择，您可以使用平衡二叉搜索树来存储元素。然后可以在 O(log n) 时间内找到最小值和最大值（如果缓存结果，则为 O(1)），并且可以在 O(log n) 时间内完成插入和删除。如果您使用的是 C++，您可以只使用std::map它，然后使用begin()andrbegin()分别获取最小值和最大值。
希望这可以帮助！
二叉堆将为您提供插入和删除最小 inO(log n)和其他 in O(1).
唯一棘手的部分是在数组已满后删除最旧的元素。为此，保留另一个数组：
time[i] = at what position in the heap array is the element
added at time i + 100 * k.
每 100 次迭代，您递增k.
然后，当数组第一次填满时，您 remove heap[ time[0] ]，当它第二次填满时 remove heap[ time[1] ]，...，当它第 100 次填满时，您环绕并heap[ time[0] ]再次删除等。当它填满时第k一次，您删除heap[ time[k % 100] ]（100 是您的数组大小）。
确保time在插入和删除元素时也更新数组。
如果您知道它的位置，则可以删除任意元素O(log n)：只需将其与堆数组中的最后一个元素交换，然后筛选掉已交换的元素。
如果您绝对需要 max 和 min 为 O(1)，那么您可以做的是创建一个链表，在其中不断跟踪 min、max 和 size，然后将所有节点链接到某种树结构，可能是一堆。最小值、最大值和大小都是恒定的，并且由于找到任何节点都在 O(log n) 中，因此插入和删除都是 log n。清算将是微不足道的。
如果您的队列是固定大小的，那么 O-notation 是没有意义的。任何 O(log n) 甚至 O(n) 操作本质上都是 O(1)，因为 n 是固定的，所以你真正想要的是一种对给定数据集快速的算法。可能两个并行的传统堆优先级队列会很好（一个用于高，一个用于低）。
如果您对自己拥有的数据类型了解得更多，您也许可以制作出更特殊用途的东西。