Lower bounds: queues that return their min elements in $O(1)$ time

Question

First, consider this simple problem --- design a data structure of comparable elements that behaves just like a stack (in particular, push(), pop() and top() take constant time), but can also return its min value in $O(1)$ time, without removing it from the stack. This is easy by maintaining a second stack of min values.

Now, consider the same problem, where the stack is replaced by a queue. This seems impossible because one would need to keep track of $\Theta(n^2)$ values (min values between elements $i$ and $j$ in the queue). True or false ?

Update: $O(1)$ amortized time is quite straightforward as explained in one of the answers (using two min-stacks). A colleague pointed out to me that one can de-amortize such data structures by performing maintenance operations proactively. This is a little tricky, but seems to work.

Answer 1

Yes, it can be done in amortized O(1) time (enqueue, dequeue, minimum). Have a look at the code and explanation given here.

Here are the most relevant parts quoted from the above link (emphasis mine; and of course, all credits for the solution go to the original author, Keith Schwarz):

A FIFO queue class that supports amortized O(1) enqueue, dequeue, and find- min. Here, the find-min returns (but does not remove) the minimum value in the queue. This is not the same as a priority queue, which always removes the smallest element on each dequeue. The min-queue simply allows for constant-time access to that element.

The construction that enables the min-queue to work is based on a classic construction for creating a queue out of two stacks. ... we apply this construction to two min-stacks instead of two regular stacks. The minimum element of the queue can then be found by looking at the minimum element of the two stacks taken together.

Answer 2

When returning the min element, I assume you also want to remove it from the data structure? Otherwise it's trivial to just always keep track of the least element when you alter the data structures via any of the other operations.

I'm not entirely sure how much cheating you allow, but you could keep two additional queues, such that on insertion to your data structure, you also use as much time as you need to keep a queue sorted with the least elements in the first-outs position.

Let Q be your main queue, S your sorted queue and A an (empty) additional queue. When you receive a new element, e, to Q, you push all your elements in S less than e into A, then you push e to A, and then you empty the rest of S into A. Finally you push all of A into S. This takes O(n) time, you use only queues, and you can find the minimal element in constant time. If you also need to be able to remove it from the main queue, you can keep pointers from the elements in S to the positions in Q.