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.

-
 I think that O(1) time is possible by using data structures called real-time queues, but I am not familiar with them. (If you are satisfied with amortized O(1) time, then it is definitely possible by implementing a queue by using two stacks.) – Tsuyoshi Ito Oct 19 '12 at 23:38

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.

-
Would you please provide some context for your link: either "quote the most relevant part" or describe the solution in your own words ("in case the target site is unreachable or goes permanently offline"). – Merbs Nov 4 '12 at 5:35
@Merbs Thanks for pointing that out. I've updated the question as suggested. – Vicky Chijwani Nov 4 '12 at 13:33

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.

-
 I suppose the OP does not want to remove the minimum. Otherwise, its not possible to realize this is $O(1)$ on a stack, since it would allow you to sort in linear time. – A.Schulz Oct 18 '12 at 12:30 Correct - the minimum value is not removed. – Igor Markov Oct 18 '12 at 12:39 When you dequeue something from the queue, I do not see how you can find the new minimum in $O(1)$ time. You can, of course, perform a linear search, but that would not satisfy the requirements of the problem. "Behaves just like a stack" and "behaves just like a queue" includes $O(1)$-time operations. The question is really about proving impossibility (I just revised the wording to clarify the constraints). – Igor Markov Oct 18 '12 at 12:43