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.