스택 (Stack)

관련 문제

문제	난이도	핵심
9012번 — 괄호	실버 IV	괄호 유효성 검사
10828번 — 스택	실버 IV	스택 기본 구현
17298번 — 오큰수	골드 IV	단조 스택
17413번 — 단어 뒤집기 2	실버 III	스택 활용
2504번 — 괄호의 값	골드 V	괄호 계산

---

1. 개념

스택(Stack)은 나중에 넣은 데이터가 먼저 나오는(LIFO, Last In First Out) 자료구조다.

마지막에 넣은 것이 가장 먼저 나온다.

접시를 쌓는 것과 같다. 가장 위에 올린 접시를 가장 먼저 꺼낸다.

push(1) → push(2) → push(3) → pop() → pop() → pop()
[1] → [1,2] → [1,2,3] → [1,2] → [1] → []
반환값:                           3       2      1

---

2. 동작 과정

괄호 유효성 검사 예시: ( ( ) ( ) )

단계	문자	동작	스택 상태
1	(	push	[(]
2	(	push	[(, (]
3	)	pop	[(]
4	(	push	[(, (]
5	)	pop	[(]
6	)	pop	[]

최종 스택이 비어 있음 → 유효한 괄호

---

3. 핵심 포인트 2가지

Java에서 Stack보다 Deque를 써라

Java의 Stack 클래스는 Vector를 상속해 동기화 오버헤드가 있다.
알고리즘 문제에서는 ArrayDeque를 스택처럼 쓰는 것이 표준이다.

// ❌ 느린 방식
Stack<Integer> stack = new Stack<>();

// ✅ 빠른 방식
Deque<Integer> stack = new ArrayDeque<>();

단조 스택(Monotonic Stack)

스택에 값을 넣을 때 단조 증가 또는 단조 감소 순서를 유지하는 스택이다.
"현재 원소보다 크거나 작은 값을 스택에서 제거"하는 방식으로 동작한다.
오큰수, 히스토그램 등 이전/다음 크거나 작은 원소를 O(N)에 구할 수 있다.

---

4. 코드

기본 연산

Deque<Integer> stack = new ArrayDeque<>();

stack.push(1);           // push: 맨 위에 추가
stack.push(2);
stack.push(3);

int top = stack.peek();  // peek: 맨 위 값 확인 (꺼내지 않음) → 3
int val = stack.pop();   // pop: 맨 위 값 꺼내기 → 3

boolean empty = stack.isEmpty();  // 비어 있는지 확인
int size = stack.size();          // 현재 원소 개수

괄호 유효성 검사 패턴

static boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();

    for (char c : s.toCharArray()) {
        if (c == '(') {
            stack.push(c);           // 여는 괄호 → push
        } else {
            if (stack.isEmpty()) return false;  // 닫는 괄호인데 스택이 비어있음
            stack.pop();             // 닫는 괄호 → pop으로 짝 제거
        }
    }

    return stack.isEmpty();          // 모두 짝이 맞으면 스택이 비어 있어야 함
}

단조 스택 패턴 (오큰수)

// 각 원소의 오른쪽에서 처음으로 자신보다 큰 수를 구하는 패턴
static int[] nge(int[] arr) {
    int N = arr.length;
    int[] result = new int[N];
    Arrays.fill(result, -1);         // 오큰수가 없으면 -1

    Deque<Integer> stack = new ArrayDeque<>();  // 인덱스를 저장

    for (int i = 0; i < N; i++) {
        // 스택 top의 원소보다 현재 원소가 크면 → 오큰수 발견
        while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
            result[stack.pop()] = arr[i];
        }
        stack.push(i);
    }

    return result;
}

---

5. 시간복잡도

연산	시간복잡도
push	O(1)
pop	O(1)
peek	O(1)
단조 스택 전체 순회	O(N)

push/pop 모두 O(1)이다. 단조 스택은 각 원소가 최대 한 번 push되고 한 번 pop되므로 전체 O(N)이다.

---

6. 주의사항

• pop 전에 isEmpty() 확인을 습관화하라. 빈 스택에서 pop하면 NoSuchElementException이 발생한다.
• Java Stack 클래스는 쓰지 마라. ArrayDeque가 더 빠르고 공식 문서도 이를 권장한다.
• 단조 스택은 인덱스를 저장하는 경우가 많다. 값 자체보다 위치 정보가 필요한 경우가 대부분이기 때문이다.
• ArrayDeque의 push/pop은 앞(front) 기준이다. 스택처럼 쓸 때는 push, pop, peek만 사용하고 offer, poll과 섞어 쓰지 않도록 주의하라.