Priority Queue Using Stack
Think about it. You can sort an array by adding all the items to a priority queue, then removing the items in sorted order. 

If you could run a priority queue in constant time, you could sort in linear time. But you can't.