Pasted

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;
    }
}