테마
스택과 큐
스택(stack)은 가장 나중에 넣은 것을 가장 먼저 꺼내는 자료구조(data structure)이고, 큐(queue)는 먼저 넣은 것을 먼저 꺼내는 자료구조다. 둘 다 넣고 꺼내는 위치를 한쪽 끝으로 제한한 대신, 넣기와 꺼내기를 원소 수와 상관없이 일정한 시간, 곧 빅오 표기법(Big-O notation)으로 O(1)에 한다. 스택은 "되돌아가기"에, 큐는 "도착 순서대로 처리하기"에 맞는다.
스택: 후입선출
스택은 LIFO(Last In First Out, 후입선출) 규칙을 따른다. 접시를 쌓듯 모든 동작이 맨 위(top) 한쪽 끝에서만 일어난다. 맨 위에 넣는 push, 맨 위를 꺼내는 pop, 꺼내지 않고 맨 위를 보는 peek 모두 O(1)이다. 배열(array)로 만들면 배열 끝을 맨 위로 쓰고, 연결 리스트(linked list)로 만들면 첫 노드(node)를 맨 위로 쓴다. 어느 쪽이든 다른 원소를 옮길 일이 없다. 대표 쓰임은 다음과 같다.
- 호출 스택(call stack): 함수를 호출하면 지역 변수와 돌아갈 위치가 한 겹 쌓이고, 끝나면 빠진다. 가장 나중에 부른 함수가 가장 먼저 끝나기 때문이다.
- 괄호 짝 검사: 아래 코드처럼 여는 괄호는 넣고, 닫는 괄호가 나오면 꺼내 짝을 본다. 끝에 스택이 비어 있어야 올바른 식이다.
- 되돌리기(undo): 편집기는 작업을 할 때마다 기록을 쌓고, 되돌리기를 누르면 가장 최근 작업부터 꺼내 취소한다.
- DFS(Depth-First Search, 깊이 우선 탐색): 그래프(graph)를 한 길로 끝까지 들어갔다가 막히면 가장 최근 갈림길로 되돌아가는 탐색이라, 갈림길을 스택에 쌓아 둔다(그래프).
java
boolean valid(String s) {
Deque<Character> st = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[') st.push(c);
else if (st.isEmpty() || st.pop() != (c == ')' ? '(' : '[')) return false;
}
return st.isEmpty();
}재귀와 스택 오버플로
함수가 자기 자신을 다시 부르는 재귀(recursion)가 한 단계 깊어질 때마다 호출 스택에 한 겹이 더 쌓인다. 호출 스택은 크기가 정해져 있어서, 종료 조건이 빠졌거나 입력이 커서 재귀가 너무 깊어지면 넘친다. 이것이 스택 오버플로(stack overflow)다. Java에서는 StackOverflowError가 나고, 처리하지 않으면 프로그램이 멈춘다. 크기는 운영체제와 실행 설정(Java는 스레드 스택 크기 옵션 -Xss)에 따라 다르다. 깊이가 입력 크기에 비례하는 재귀는 반복문과 직접 만든 스택으로 바꾸면 이 한계를 피할 수 있다.
큐: 선입선출
큐는 FIFO(First In First Out, 선입선출) 규칙을 따른다. 매표소 줄처럼 뒤(rear)로 들어와 앞(front)으로 나간다. 넣기(enqueue)와 꺼내기(dequeue) 모두 O(1)이다.
- BFS(Breadth-First Search, 너비 우선 탐색): 가까운 곳부터 한 겹씩 넓혀 가는 그래프 탐색으로, 방금 발견한 곳을 큐 뒤에 넣고 앞에서 꺼내므로 먼저 발견한 곳이 먼저 처리된다.
- 작업 대기열: 인쇄 대기열이나 서버의 요청 대기열처럼, 먼저 온 작업을 먼저 처리해야 공정한 곳에 쓴다.
배열로 큐를 만들 때의 문제와 원형 큐
배열로 큐를 만들면 꺼내기가 문제다. 앞 원소를 꺼낼 때마다 나머지를 한 칸씩 당기면 원소 수(n)에 비례하는 O(n)이 된다. "앞" 인덱스만 한 칸 옮기면 O(1)이지만 앞쪽에 빈칸이 쌓여, 뒤 인덱스가 배열 끝에 닿으면 앞이 비어 있어도 더 넣을 수 없다.
원형 큐(circular queue)는 배열의 끝과 처음이 이어진 것처럼 써서 이 빈칸을 다시 쓴다. 인덱스를 늘릴 때 배열 길이로 나눈 나머지를 쓰면, 마지막 칸 다음이 0번 칸이 된다.
java
int[] buf = new int[N]; int head = 0, size = 0;
void offer(int x) { buf[(head + size) % N] = x; size++; } // 가득 찼는지 검사는 생략
int poll() { int x = buf[head]; head = (head + 1) % N; size--; return x; }앞과 뒤 인덱스만으로 관리하면 "비었을 때"와 "가득 찼을 때" 두 인덱스가 똑같아져 구분이 안 된다. 그래서 위 코드처럼 원소 수를 따로 세거나, 한 칸을 일부러 비워 두어 "뒤 다음 칸이 앞이면 가득 참"으로 판단한다.
덱과 Java에서의 선택
덱(deque)은 double-ended queue의 줄임말로, 앞과 뒤 양쪽에서 넣고 꺼낼 수 있는 큐다. 한쪽 끝만 쓰면 스택이 되고, 한쪽으로 넣고 반대쪽으로 꺼내면 큐가 된다.
| 구조 | 넣는 곳 | 꺼내는 곳 | 대표 쓰임 |
|---|---|---|---|
| 스택 | 위 | 위 | 호출 스택, 괄호 검사, 되돌리기 |
| 큐 | 뒤 | 앞 | BFS, 작업 대기열 |
| 덱 | 앞·뒤 | 앞·뒤 | 스택과 큐 모두, 슬라이딩 최댓값 |
슬라이딩 최댓값은 일정한 폭의 구간을 한 칸씩 밀며 구간마다 최댓값을 구하는 문제로, 덱 양 끝에서 쓸모없어진 원소(앞은 구간 밖, 뒤는 새 값보다 작은 값)를 빼 가며 O(n)에 푼다.
Java에서는 스택도 큐도 Deque 인터페이스(덱이 제공할 연산만 정한 약속)를 구현한 ArrayDeque로 쓴다. 공식 문서는 오래된 Stack 클래스 대신 Deque를 권하고, ArrayDeque가 스택으로는 Stack보다, 큐로는 LinkedList보다 보통 빠르다고 적는다. OpenJDK의 ArrayDeque는 내부를 원형 큐처럼 쓰는 동적 배열(dynamic array)이라, 원소가 연속으로 붙어 캐시 메모리(cache memory)에 한꺼번에 올라오고 노드마다 메모리를 할당할 필요도 없기 때문이다.
넣은 순서가 아니라 우선순위가 높은 것부터 꺼내야 하면 우선순위 큐(priority queue)를 쓴다. 이름에 "큐"가 들어가지만 FIFO가 아니고, 보통 힙(heap)으로 만든다(힙과 우선순위 큐).
면접 포인트
- "스택과 큐의 차이는?" → LIFO vs FIFO. 둘 다 넣기·꺼내기 O(1).
- "스택은 어디에 쓰나요?" → 호출 스택, 괄호 검사, 되돌리기, 깊이 우선 탐색. 큐는 BFS, 작업 대기열.
- "배열로 큐를 만들면 뭐가 문제죠?" → 꺼낼 때 당기면 O(n), 안 당기면 앞 빈칸 낭비 → 원형 큐(나머지 연산으로 인덱스 순환).
- "원형 큐에서 빈 것과 가득 찬 것을 어떻게 구분하나요?" → 원소 수를 세거나 한 칸을 비워 둔다.
- "Java에서 스택은 뭘 쓰나요?" →
Stack대신ArrayDeque(Deque). - 우선순위 큐는 FIFO가 아니다.