Get Min/Max in O(1) time from a Queue? [closed]

Question

How can I retrieve the max and min element from a queue at any time in 0(1) time complexity? Earlier I was using Collections.max and min to find the elements but that would be 0(n).

Answer 1

There exist such a structure that acts like a queue but lets you retrieve min/max value in constant time, actually not strictly constant, it is amortized constant time (named min/max queue as you could guess). There are two ways of implementing it - using two stacks or using a queue and a deque.

Deque implementation looks more less like this (language agnostic):

so we have a deque of max elements, the one on the front is the desired max, and a standard queue.

Push operation

1. If the queue is empty, just push the element on both, the queue and the deque.
2. If the queue is not empty, push the element on the queue, going from the back of the deque delete all elements that are strictly less than the one we are now pushing (they will surly not be the max, since the pushed element is larger and will last on the queue for longer) and push the current element on the back of the deque

Remove operation

1. If the front of the deque is equal to the front of the queue then pop both (deque from the front)
2. If the front of the deque is not equal to the front of the queue then pop just the queue, the poped element surely is not the largest one.

Get max

1. It is just the first element of the deque.

(lots of arguments should be added to make it clear why it works, but the second version presented below may be the answer to this necessity)

The Stack implementation is quite similar, I think it may be a bit longer to implement but perhaps easier to grasp. The first thing to note is that it is easy to store the maximal element at the stack - easy exercise (for the lazy ones - Stack with find-min/find-max more efficient than O(n)?). The second part, perhaps a bit tricky if seen the first time, is that it is quite easy to implement a queue using two stacks, it can be found here - How to implement a queue using two stacks? . And that is basically it - if we can get the maximal element of both of the stacks we can get the maximal element of the whole queue (taking maximum is associative or something like that if you want a more formal argument, but I bet you don't, it is really obvious).

The min versions is done analogically.

Everything may also be done using a set (or something of it's kind) in O(nlogn) time but it is pointless as the constant in O(n) is really small and it should be much faster, yet easy to implement.

NON-INTERESTING parts from the first version:

Hope I helped a little bit. And hope that didn't say anything wrong. Can give a simple implementation in C++/C if required. Would be grateful for any feedback on the form as it is my first post of this type anywhere :) (and English is not my native language). Also some confirmation on the correctness would be great.

EDIT: as this answer got me some points I felt obliged to clean it up a bit, also extending it a bit.

Answer 2

You only have 2 ways to get O(1) for a min/max operation:

• if the structure is sorted and you know where the max / min is located
• if the structure is not sorted and only allows insertion: you can recalculate the min / max every time you insert an item and store the value separately
• if the structure is not sorted and allows insertions and removals: I don't think you can do better than O(n), unless you use more than one collection (but that solution does not support removal of any elements, only head / tail elements, which should be the case with a queue).

Answer 3

Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations