MinStack

class MinStack {

    private static Node max = new Node(Integer.MAX_VALUE);
    private Node stack;

    public MinStack() {
        stack = new Node(Integer.MAX_VALUE);
        stack.min = max;
    }

    public void push(int data) {
        Node node = new Node(data);
        node.next = stack;
        if (data <= stack.min.data)
            node.min = node;
        else
            node.min = stack.min;
        stack = node;
    }

    public void pop() {
        stack = stack.next;
    }

    public int top() {
        return stack.data;
    }

    public int getMin() {
        return stack.min.data;
    }
}

class Node {

    public int data;
    public Node min;
    public Node next;

    public Node(int data) {
        this.data = data;
    }
}