我想實現雙端優先隊列有以下限制：需要實現雙端優先級隊列的最佳方式是什麼？
在一個固定的大小來實現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