Min Stack

Implement a stack with min() function, which will return the smallest number in the stack.

It should support push, pop and min operation all in O(1) cost.

Example:

push(1)
pop()   // return 1
push(2)
push(3)
min()   // return 2
push(1)
min()   // return 1

Solution:

Create an additional stack to store the minimum value up to date.

Code:

public class MinStack {

    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int number) {
        if (minStack.empty() || number <= min()) {
            minStack.push(number);
        }
        stack.push(number);
    }

    public int pop() {
        int value = stack.pop();
        if (value == min()) {
            minStack.pop();
        }
        return value;
    }

    public int min() {
        if (minStack.empty()) {
            return Integer.MIN_VALUE;
        }
        return minStack.peek();
    }
}