class MinStack {
    
    // 스택이니까 헤드노드와 다음노드만 유지하면 된다.
    private Node head;

    public MinStack() {
        
    }
        
    // 입력할때 최소값 처리를 한다.
    public void push(int val) {
        if (head == null) {
            head = new Node(val, val, null);
        } else {
            // 최소값을 체크해서 갱신한다.
            head = new Node(val, Math.min(val, head.min), head);
        }
    }
    
    // 헤드노드를 다음노드로 갱신한다.
    public void pop() {
        head = head.next;
    }
    
    public int top() {
        return head.val;
    }
    
    public int getMin() {
        return head.min;
    }
        
    private class Node {
        int val;
        int min; // 최소값을 유지하면 모든 노드를 찾지 않아도 된다.
        Node next;
            
        private Node(int val, int min, Node next) {
            this.val = val;
            this.next = next;
            this.min = min;
        }
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */