[스택·큐] 시작하기 전에 정리하는 자료구조와 자주 쓰는 메서드

카테고리: 스택·큐 이 글은 문제 하나를 다루는 글이 아니라, 이 카테고리를 시작하기 전에 알아야 할 개념 전체를 한 번에 정리한 글이다. 앞으로 이 카테고리의 다른 글들은 이 글에서 정리한 내용을 전제로, 그 문제에서만 있었던 시행착오를 다룬다.

스택(Stack)이란?

LIFO(Last In, First Out) — 마지막에 넣은 게 가장 먼저 나온다. 접시를 쌓아놓고 위에서부터 꺼내는 것과 같다.

• 언제 쓰나: “가장 최근에 본 것”과 비교/매칭해야 하는 문제. 괄호 짝 맞추기, 함수 호출 스택, 실행 취소(undo), 문자열을 앞에서부터 처리하다가 뒤로 되돌아가야 할 때.

Deque<Character> stack = new ArrayDeque<>();
stack.push(c);     // 맨 위에 추가
stack.pop();        // 맨 위 꺼내면서 제거 (비어있으면 예외)
stack.peek();        // 맨 위 확인만 (비어있으면 null)
stack.isEmpty();

java.util.Stack도 있지만 Vector를 상속해서 내부적으로 동기화되어 느리다. 요즘은 ArrayDeque를 스택처럼 쓰는 게 사실상 표준이다.

큐(Queue)란?

FIFO(First In, First Out) — 먼저 넣은 게 먼저 나온다. 줄을 서는 것과 같다.

• 언제 쓰나: 순서대로 처리해야 하는 작업, BFS(너비 우선 탐색), “최근 N개”를 유지해야 하는 슬라이딩 윈도우류.

Queue<Integer> queue = new LinkedList<>();  // 또는 ArrayDeque
queue.offer(x);      // 뒤에 추가
queue.poll();          // 앞에서 꺼내면서 제거 (비어있으면 null)
queue.peek();          // 앞 확인만
queue.isEmpty();

덱(Deque)이란?

양쪽 끝에서 다 넣고 뺄 수 있는 자료구조. 스택으로도, 큐로도 쓸 수 있고, “슬라이딩 윈도우에서 최댓값 유지하기” 같은 몬로토닉 덱(monotonic deque) 패턴에서 자주 등장한다.

Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(x); deque.addLast(x);
deque.removeFirst(); deque.removeLast();
deque.peekFirst(); deque.peekLast();

스택으로 푸는 대표 패턴

1. 매칭/검증 — 괄호 짝 맞추기(LC20)처럼, 여는 것을 쌓아뒀다가 닫는 게 나오면 맨 위와 비교. HashMap으로 “닫는 것 → 여는 것” 짝을 미리 정의해두면 분기 없이 깔끔해진다.
2. 몬로토닉 스택(Monotonic Stack) — “다음으로 더 큰/작은 원소 찾기”류(Next Greater Element, Daily Temperatures). 스택에 항상 오름차순/내림차순을 유지하도록 넣고 빼면서, 조건이 깨지는 순간 그 관계를 기록한다.
3. 역순 처리 — 문자열/수식을 앞에서부터 읽다가, 뒤로 되짚어야 하는 계산(계산기, 역폴란드 표기법).

큐로 푸는 대표 패턴

1. BFS — 그래프/트리를 레벨 단위로 탐색할 때 큐에 다음에 방문할 노드를 넣어둔다 (아직 이 카테고리에서 다루지 않음, 다음 단계).
2. 슬라이딩 윈도우 — 덱을 써서 윈도우 안의 최댓값/최솟값을 O(1)에 유지.
3. 순서 보장이 필요한 시뮬레이션 — 대기열, 스케줄링류 문제.

함께 자주 쓰는 HashMap

스택/큐 문제에서 “짝을 미리 정의”하거나 “빈도수를 센다”는 목적으로 HashMap이 자주 같이 등장한다.

Map<Character, Character> map = new HashMap<>();
map.put(')', '(');   // 닫는 괄호 -> 여는 괄호

map.get(key);                // 값 꺼내기, 없으면 null
map.getOrDefault(key, def);  // 없으면 기본값
map.containsKey(key);
map.put(key, map.getOrDefault(key, 0) + 1);  // 빈도수 세기

자주 하는 실수

• 매칭에 성공했을 때 스택에서 빼는 걸 잊는다. 짝이 맞는지 “확인”만 하고 pop()을 안 하면, 이미 닫힌 괄호가 스택에 계속 남아서 그다음 비교가 전부 틀어진다.
• 루프가 끝난 뒤 스택이 비어있는지 확인을 빼먹는다. "((("처럼 여는 것만 있고 하나도 안 닫힌 경우, 루프 안에서는 아무 오류도 안 나지만 끝나고 나서 스택에 뭔가 남아있으면 무효로 처리해야 한다.
• 빈 스택에서 peek()/pop()을 부르면 어떻게 되는지 미리 생각 안 한다. peek()은 null을 반환하고(예외 안 남), pop()은 예외를 던진다. 닫는 괄호가 먼저 나오는 경우(")" 단독)처럼 스택이 빈 상태에서 닫는 걸 만나는 케이스를 조건문에서 놓치기 쉽다.

시간복잡도

스택/큐의 push/pop/peek/offer/poll 전부 O(1)이다. 대부분의 스택/큐 문제는 배열을 한 번만 순회(O(n))하면서 이 연산들을 쓰기 때문에 전체 O(n)으로 끝나는 경우가 많다 — 이게 이 카테고리의 핵심 장점이다.