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.