스택 (Stack)

정의

스택 (Stack) 은 LIFO (Last In, First Out) 순서로 원소를 관리하는 추상 자료구조입니다. push(x), pop(), top() 세 연산만 제공하며, 가장 최근 삽입된 원소만 접근 가능합니다.

C++ STL std::stack, Python list, Java Stack / ArrayDeque 로 기본 제공됩니다.

문제 상황과 동기

함수 호출, 괄호 매칭, DFS 구현, 수식 파싱 등 “가장 최근 상태로 되돌아가야 하는” 모든 문제에서 스택이 자연스럽게 등장합니다.

• naive: 배열 전체를 순회하며 “최근 값” 을 찾으면 O(N²).
• stack: 최근 값만 O(1) 접근. push/pop 도 O(1).

핵심 통찰: 재귀 = 시스템 스택, 모든 DFS / backtracking 은 스택 기반. 명시적 스택을 쓰면 재귀 깊이 제한 (Python 기본 1000) 을 피할 수 있습니다.

시각화

핵심 아이디어

invariant: top 은 항상 가장 최근 삽입 원소. 삽입 / 삭제 순서가 역순.

단조 스택 (Monotonic Stack)

스택 내부를 오름차순 / 내림차순으로 유지하면서 push. 새 원소가 들어올 때, 조건 위배되는 top 을 pop. “다음 큰 원소 (Next Greater Element)” 같은 문제를 O(N) 에 해결.

for each x in array:
    while stack not empty and stack.top < x:
        stack.pop()   # top 이 x 보다 작으면 제거
    stack.push(x)

스택에 남은 원소들은 감소 수열. 각 원소는 최대 1번 push + 1번 pop, amortized O(1).

알고리즘

기본 스택 (배열 구현)

class Stack:
    data = []
    size = 0

    push(x):
        data[size++] = x

    pop():
        return data[--size]

    top():
        return data[size - 1]

    empty():
        return size == 0

단조 스택 (Next Greater Element)

next_greater(a):
    result = array of length N, fill with -1
    stack = empty
    for i = 0..N-1:
        while stack not empty and a[stack.top] < a[i]:
            idx = stack.pop()
            result[idx] = a[i]
        stack.push(i)
    return result

구현

// 괄호 매칭 (valid parentheses)
#include <bits/stdc++.h>
using namespace std;
int main() {
  string s; cin >> s;
  stack<char> st;
  for (char c : s) {
      if (c == '(' || c == '[' || c == '{') {
          st.push(c);
      } else {
          if (st.empty()) { cout << "NO\n"; return 0; }
          char t = st.top(); st.pop();
          if (c == ')' && t != '(') { cout << "NO\n"; return 0; }
          if (c == ']' && t != '[') { cout << "NO\n"; return 0; }
          if (c == '}' && t != '{') { cout << "NO\n"; return 0; }
      }
  }
  cout << (st.empty() ? "YES" : "NO") << "\n";
}

# 괄호 매칭
s = input().strip()
st = []
pairs = {'(': ')', '[': ']', '{': '}'}
for c in s:
  if c in pairs:
      st.append(c)
  else:
      if not st or pairs[st.pop()] != c:
          print("NO")
          exit()
print("YES" if not st else "NO")

// 괄호 매칭 (ArrayDeque 사용, Stack 보다 빠름)
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      String s = br.readLine();
      Deque<Character> st = new ArrayDeque<>();
      for (char c : s.toCharArray()) {
          if (c == '(' || c == '[' || c == '{') {
              st.push(c);
          } else {
              if (st.isEmpty()) { System.out.println("NO"); return; }
              char t = st.pop();
              if (c == ')' && t != '(') { System.out.println("NO"); return; }
              if (c == ']' && t != '[') { System.out.println("NO"); return; }
              if (c == '}' && t != '{') { System.out.println("NO"); return; }
          }
      }
      System.out.println(st.isEmpty() ? "YES" : "NO");
  }
}

()[]{}

YES

([)]

NO

단조 스택 예제 (Next Greater Element)

// 각 원소의 오른쪽에서 가장 가까운 큰 값
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n; cin >> n;
  vector<int> a(n), res(n, -1);
  for (auto& v : a) cin >> v;
  stack<int> st;
  for (int i = 0; i < n; i++) {
      while (!st.empty() && a[st.top()] < a[i]) {
          res[st.top()] = a[i];
          st.pop();
      }
      st.push(i);
  }
  for (int v : res) cout << v << " ";
  cout << "\n";
}

# Next Greater Element
n = int(input())
a = list(map(int, input().split()))
res = [-1] * n
st = []
for i in range(n):
  while st and a[st[-1]] < a[i]:
      res[st.pop()] = a[i]
  st.append(i)
print(*res)

6
2 1 2 4 3 5

4 2 4 5 5 -1

복잡도

변형 / 활용

함정

1. pop() 전 empty 체크

스택이 비었는데 pop 하면 런타임 에러 (C++, Java) 또는 IndexError (Python).

if (!st.empty()) st.pop();   // 항상 확인

2. top() 도 empty 체크 필요

if (!st.empty()) cout << st.top();

3. 단조 스택 조건 방향

“다음 큰 원소” 는 a[st.top()] < a[i] 일 때 pop. “다음 작은 원소” 는 a[st.top()] > a[i]. 부등호 방향 주의.

4. 인덱스 vs 값

단조 스택에 값을 넣으면 나중에 원래 위치를 찾을 수 없습니다. 인덱스를 저장하고, a[st.top()] 로 값 접근.

5. Java Stack 대신 Deque

Java Stack 은 레거시 클래스 (Vector 기반, synchronized). ArrayDeque 가 더 빠릅니다.

Deque<Integer> st = new ArrayDeque<>();
st.push(x); st.pop(); st.peek();

BOJ 연습 문제

참고

• 큐 (FIFO)
• 깊이 우선 탐색 (명시적 스택)
• 재귀 (시스템 스택)