1. 스택/큐 개념?
1-1. 스택
- LIFO (Last-In, First-Out): 나중에 들어온 데이터가 먼저 나가는 “후입선출” 구조
- 비유: 접시 더미에서 가장 위 접시부터 꺼내는 것
- 활용: 뒤로 가기(Undo), 괄호 짝 맞추기, 재귀 함수 호출 관리, DFS(깊이 우선 탐색) 등
1-2. 큐
- FIFO (First-In, First-Out): 먼저 들어온 데이터가 먼저 나가는 “선입선출” 구조
- 비유: 은행 창구 줄서기
- 활용: 프린터 출력 대기열, 은행 창구 업무, 작업/프로세스 스케줄링, BFS(너비 우선 탐색) 등
원형 큐(Circular Queue)란 ?
일반적인 선형 큐(배열 기반)는 dequeue 할 때 앞부분이 비게 됩니다. 이 빈 공간을 재사용하려면 데이터를 앞으로 당기는 작업(shift, O(n))이 필요할 수 있는데, 이를 해결하기 위해 배열의 끝과 시작이 연결된 것처럼 인덱스를 순환시키는 구조가 원형 큐입니다.
- 참고: Java의
ArrayDeque는 내부적으로 원형(서큘러 버퍼) + 자동 리사이즈 방식이라, 코딩 테스트에서는 별도로 원형 큐를 구현할 일이 거의 없습니다.
1-3. 시간복잡도
스택과 큐는 데이터의 입구/출구가 정해져 있어 성능이 매우 뛰어납니다.
| 연산 | 시간 복잡도 | 설명 |
|---|---|---|
| 삽입 (Push/Offer) | O(1) | 끝(또는 위)에 추가 (평균/분할 상환) |
| 삭제 (Pop/Poll) | O(1) | 정해진 위치에서 제거 |
| 조회 (Peek) | O(1) | 제거 없이 가장 앞/위 확인 |
| 탐색 (Search) | O(n) | 특정 값 찾으려면 전체 순회 필요 |
2. Java에서 스택/큐 다루기
2-1. 생성 및 초기화
import java.util.*;
// 스택(LIFO)
Stack<Integer> stack1 = new Stack<>();
Deque<Integer> stack2 = new ArrayDeque<>();
// 큐(FIFO)
Queue<Integer> queue = new ArrayDeque<>();- 스택처럼 쓸 때:
push / pop / peek - 큐처럼 쓸 때:
offer / poll / peek - Deque를 큐로 더 명시적으로 쓰고 싶으면:
addLast / pollFirst / peekFirst
Java의
Stack클래스는 내부적으로Vector를 상속받아 만들어졌고, 많은 메서드가synchronized기반이라 코딩 테스트처럼 단일 스레드 환경에서는 불필요한 오버헤드가 생길 수 있습니다. 그래서 보통ArrayDeque(Deque)를 스택/큐로 활용하는 것을 추천합니다.
2-2. 자주 쓰는 유틸
size(): 현재 데이터 개수 확인isEmpty(): 비어있는지 확인 (pop/poll 전 필수)clear(): 전체 초기화
3. 기본 메서드
3-1. 스택 메서드
| 기능 | 메서드 | 설명 |
|---|---|---|
| 삽입 | push(e) | 맨 위에 요소 추가 |
| 삭제 | pop() | 맨 위 요소 제거 후 반환 (비어있으면 예외 발생) |
| 확인 | peek() | 제거 없이 맨 위 요소 확인 |
3-2. 큐 메서드
| 기능 | 메서드 | 설명 |
|---|---|---|
| 삽입 | offer(e) | 큐 뒤에 추가 (실패 시 false) |
| 삭제 | poll() | 큐 앞 요소 제거 후 반환 (비어있으면 null) |
| 확인 | peek() | 제거 없이 맨 앞 요소 확인 |
3-3. 비었을 때 동작
- 예외 발생 계열:
pop,remove,element→ 비어있으면 예외 - null 반환 계열(Queue/Deque):
poll,peek→ 비어있으면null - (참고)
Stack클래스의pop()/peek()는 비어있으면EmptyStackException
4. 대표 패턴 및 실전 예제
코딩 테스트에서 스택과 큐가 어떻게 쓰이는지, 가장 자주 나오는 패턴의 템플릿입니다.
4-1. 괄호 검사 (Stack)
문자열을 순회하며 짝이 맞는지 확인하는 전형적인 스택 문제입니다.
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(') stack.push(')');
else if (c == '{') stack.push('}');
else if (c == '[') stack.push(']');
else if (stack.isEmpty() || stack.pop() != c) return false;
}
return stack.isEmpty();
}4-2. BFS 탐색 (Queue)
최단 거리나 인접 노드 탐색 시 사용되는 기본 구조입니다.
public void bfs(int startNode) {
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(startNode);
visited[startNode] = true;
while (!queue.isEmpty()) {
int curr = queue.poll();
for (int next : adj[curr]) {
if (!visited[next]) {
visited[next] = true;
queue.offer(next);
}
}
}
}4-3. 우선순위 큐 (PriorityQueue)
들어온 순서가 아니라 우선순위(값의 크기 등)에 따라 데이터가 나가는 자료구조입니다.
“가장 작은 값/큰 값”을 계속 뽑아야 할 때 유용합니다. (최소힙/최대힙)
// 최소 힙 (오름차순)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 최대 힙 (내림차순)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());4-4. 요세푸스 문제 (Queue/Deque)
큐의 회전(Rotate) 성질을 이용한 대표적인 문제입니다.
명의 사람이 원형으로 앉아 있을 때, 번째 사람을 계속해서 제거하는 로직입니다.
public List<Integer> josephus(int n, int k) {
Deque<Integer> queue = new ArrayDeque<>();
List<Integer> result = new ArrayList<>();
// 1. 큐 초기화 (1번부터 N번까지)
for (int i = 1; i <= n; i++) queue.addLast(i);
// 2. 큐가 빌 때까지 반복
while (!queue.isEmpty()) {
// K-1번 동안 맨 앞의 요소를 뒤로 보냄
for (int i = 0; i < k - 1; i++) {
queue.addLast(queue.pollFirst());
}
// K번째 요소를 제거하고 결과 리스트에 추가
result.add(queue.pollFirst());
}
return result;
}5. 주의사항
- Empty Check
poll()/peek()는 비어있을 때null을 반환pop()/remove()는 비어있을 때 예외 발생
→ 코딩 테스트에서는 안전하게isEmpty()로 먼저 확인하거나,poll/peek계열을 선호하는 편이 좋습니다.
- null 처리
poll()이나peek()반환값은 비어있으면null- 기본 타입
int에는null을 담을 수 없으니Integer로 받거나,isEmpty()로 먼저 검사하세요.
- ArrayDeque vs LinkedList
- 단순 삽입/삭제만 반복하는 큐/스택 용도라면 보통
ArrayDeque가 더 빠르고 메모리 효율적입니다. LinkedList는 노드 객체가 많아져 오버헤드가 생길 수 있습니다.ArrayDeque는 null 요소를 허용하지 않습니다. (offer(null)같은 것 금지)
마무리
오늘은 알고리즘의 기초인 스택과 큐에 대하여 정리해 보았습니다.
공부하다 보면 구현 그 자체보다 '이 문제에 왜 이 자료구조를 써야 하지?'를 고민하는 게 가장 어려운 것 같습니다.
아직 어렵지만 문제를 많이 풀다보면, 적절한 자료구조를 찾는 것도 익숙해지지 않을까 싶습니다.☺️
다음 포스팅은 해시(Hash) 관련 내용을 정리해보겠습니다.🔥
