155 Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Solution. using two stacks, push value as usually, but at mean time, push the top of another stack, minStack, or the current value onto minStack, whichever is smaller.

class MinStack {
    private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();

    public void push(int x) {
        if(stack.empty()){
            stack.push(x);
            minStack.push(x);
        }else{
            stack.push(x);
            if(minStack.peek() > x){
                minStack.push(x);
            }else{
                minStack.push(minStack.peek());
            }
        }
    }

    public void pop() {
        if(stack.empty()){
            //throw exception
        }else{
            stack.pop();
            minStack.pop();
        }
    }

    public int top() {
        if(stack.empty()){
            //throw Exception();
            return -1;
        }else{
            return stack.peek();
        }
    }

    public int getMin() {
        if(minStack.empty()){
            //throw Exception
            return -1;
        }else{
            return minStack.peek();
        }
    }
}