How to design a data structure which supports the following operations in constant time?

Question

1. Push(): add an element into the collection.
2. Pop(): return and remove the minimal element from this collection.
3. Min(): return but do not remove the minimal element from this collection.

Answer 1

Suppose such a data structure existed.

Then here is an O(n) comparison-based sorting algorithm:

1. Push() every item into this data structure.
2. Pop() them all off in sorted order.

No O(n) comparison-based sorting algorithm can exist, therefore no such data structure can exist.

Answer 2

Constant time push(), pop() and remove is possible in Stack. The below post demonstrates it:

design a stack such that getMinimum( ) should be O(1)