MinStack

MinStack.java

import java.util.LinkedList;
import java.util.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.
 */

/**
 * Space - O(2n) push(x) - O(1) pop() - O(1) top() - O(1) getMin() - O(1)
 * @author hongfeili
 */
public class MinStack {

    private Stack<Integer> s;
    private LinkedList<Integer> min;

    public MinStack() {
        s = new Stack();
        min = new LinkedList();
    }

    public void push(int x) {
        s.push(x);
        if (min.size() != 0) {
            if (min.peek() > x) {
                min.push(1);
                min.push(x);
            } else {
                min.set(1, min.get(1) + 1);
            }
        } else {
            min.push(1);
            min.push(x);
        }
    }

    public int pop() {
        if (min.get(1) == 1) {
            min.pop();
            min.pop();
        } else {
            min.set(1, min.get(1) - 1);
        }
        return s.pop();
    }

    public int top() {
        return s.peek();
    }

    public int getMin() {
        return min.peek();
    }
    
    public String toString(){
        return s.toString() + "\n" + min.toString();
    }

}