我想实现双端优先队列有以下限制：需要实现双端优先级队列的最佳方式是什么？
在一个固定的大小来实现array..say 100个elements..if新元素需要后添加阵列是满的，历史最悠久的需要移除
需要最大和最小在O（1）
如果可能插入在O（1）
如果可能删除最小在O（1）
清楚为O空/初始状态（1）如果在在O时刻在数组元素的数目的可能
计数（1）
我想O（1）所有上述5个操作，但它不可能在所有的O（1）在相同的实现。至少O（1）在3次操作上和O（log（n））在其他2次操作上应该足够了。
如果有任何指针可以提供给这样的实现，将不胜感激。
A binary heap会给你插入和删除最小的O(log n)和其他O(1)。
唯一棘手的部分是在阵列满后删除最老的元素。为此，请保留另一个阵列：
time[i] = at what position in the heap array is the element
added at time i + 100 * k.
每100次迭代，您将增加k。
然后，当阵列第一次填满时，您删除heap[ time[0] ]，当它第二次填满时，您删除heap[ time[1] ]，...，当它填满第100次时，您环绕并移除heap[ time[0] ]再等等。当它填充为k次时，您删除heap[ time[k % 100] ]（100是您的数组大小）。
确保在插入和移除元素时也更新time数组。
去除的任意元素都可以在O(log n)做，如果你知道它的位置：刚才在你的堆数组的最后一个元素将其交换，并筛选下来，你已经在交换元素
如果你绝对需要。最大值和最小值都是O（1），那么你可以做的就是创建一个链表，在这里你不断追踪最小值，最大值和大小，然后将所有节点链接到某种树结构，可能是一堆。最小值，最大值和大小都将保持不变，并且由于找到任何节点将位于O（log n）中，插入和移除都是log n。清算将是微不足道的。
这里有很多专门的数据结构。一个简单的数据结构是最小 - 最大堆，它被实现为二进制堆，其中层在“最小层”（每个节点小于或等于其后代）和“最大层”（每个节点大于或者等于它的后代。）最小值和最大值可以在时间O（1）中找到，并且如在标准二进制堆中一样，可以在每个时间O（log n）时间内完成入队和出队。
您也可以使用interval heap data structure，这是该任务的另一个专用优先级队列。
或者，您可以使用两个优先级队列 - 一个按升序存储元素，另一个按降序排列。无论何时插入值，都可以将元素插入到两个优先级队列中，并且每个存储都有一个指向另一个的指针。然后，每当您将最小或最大值出队时，您可以从另一堆中移除相应的元素。
作为另一种选择，您可以使用平衡二叉搜索树来存储元素。然后可以在时间O（log n）中找到最小值和最大值（如果缓存结果，则为O（1）），并且可以在时间O（log n）中完成插入和删除操作。如果您使用的是C++，那么您只需使用std::map即可，然后分别使用begin()和rbegin()获取最小值和最大值。
希望这会有所帮助！
感谢，需要的最大帮助将是C或C++中最小 - 最大堆的干净实现 – Medicine
@ Medicine-我用其他几种解决方案更新了我的答案。最后一个解决了一个简单的C++想法。 – templatetypedef
如果你的队列是一个固定的大小，那么O-notation就没有意义了。任何O（log n）或者甚至O（n）操作本质上都是O（1），因为n是固定的，所以你真正想要的是对于给定数据集快速的算法。也许两个平行的传统堆优先级队列会很好（一个用于高，一个用于低）。
如果你更了解你有什么样的数据，你可能可以做一些更特别的事情。
你有试过什么吗？至少在O（1）中清空/初始化状态对于了解基本数据结构的人来说是微不足道的：（ – Fallen
@Fallen ya即使计数太多......只是记住它......我只是在做操作和时间复杂性明确:)，所以有人建议一个特定的实现将有清晰的想法的想法 – Medicine
嗯，你不能有插入*和*提取最小/最大值是恒定的或分期不变的时间，因为那意味着一个线性时间排序算法。所有假设您的密钥不是整数或这样，但与比较运算符的黑匣子。 – delnan