155. Min Stack, 자바 풀이

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

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.

https://leetcode.com/problems/min-stack/?envType=study-plan-v2&envId=top-interview-150

class Node {
    int val;
    Node next;

    Node(int val) {
        this.val = val;
    }
}

class MinStack {

    Node top; // 스택의 항상 위에있는 노드
    int min_val = Integer.MAX_VALUE;

    public MinStack() {
        top = null;
    }

    public void push(int val) {
        // 새로운 노드 만들기
        Node newNode = new Node(val);
        // top을 다음 노드로 선정
        newNode.next = top;
        // 가장 최근 들어온 노드를 top으로 변경
        top = newNode;
        // 스택의 최솟값을 갱신
        min_val = Math.min(min_val, val);
    }

    public void pop() {
        // 가장 최근 들어온 노드의 다음 노드를 top으로 변경
        top = top.next;

        // 스택의 최솟값을 갱신하기 위해 스택을 순회하자.
        min_val = Integer.MAX_VALUE; // 최솟값 초기화
        Node node = top;
        while (true) {
            if (node == null) {
                break;
            }

            min_val = Math.min(min_val, node.val);
            // 다음 노드로 이동
            node = node.next;
        }
    }
    
    public int top() {
        return top.val;
    }
    
    public int getMin() {
        return min_val;
    }
}

// MinStack stack = new MinStack();
// 

/**
 * 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();
 */

연결리스트를 활용하여 자료구조 Stack을 구현하는 문제이다.
신경써야 할 부분은 Stack 최소값을 항상 유지시켜야 한다. 따라서 push(), pop() 의 과정에서 Stack의 요소에 변경이 생기기 때문에 최소값을 갱신해준다.
push()는 값이 들어올 때, pop()은 tail node를 제외하고 Stack을 순회하여 최소값을 찾는다.