Write a java program for a stack which in addition to to push() and pop(), has a function min() to returns the minimum element of the stack. Push, pop and min should all operate in O(1) time.

For example:

push(5); // stack is (5), min is 5

push(6); // stack is (6, 5), min is 5

push(3); // stack is (3, 6, 5), min is 3

push(7); // stack is (7, 3, 6, 5), min is 3

pop(); // pops 7, stack (3, 6,5), min: 3

pop(); // pops 3, stack (6, 5), min 5

Hint: if we keep track of the minimum at each state we would be able to easily know the minimum in O(1). We can do this by having each node record what the minimum beneath itself is.