我想实现一个双端优先队列,具有以下约束条件:
必须在固定大小的数组中实现。比如说100个元素。如果在数组已满后需要添加新元素,则需要删除最旧的元素。
最大值和最小值需要在O(1)内找到。
如果可能,在O(1)内插入元素。
如果可能,在O(1)内删除最小值。
如果可能,在O(1)内清空/初始化状态。
在任何时刻数组中的元素数量计数应该在O(1)内完成。
我希望上述5个操作都可以在O(1)内完成,但是在同一实现中不可能同时实现所有操作的O(1)效率。至少在3个操作上达到O(1),并在另外2个操作上达到O(log(n))的效率就足够了。
如果您有指针可以提供这样的实现,将不胜感激。