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

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.

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.

StackExchange Computer Science Q#6146, answer score: 10