스택/큐를 공부하고 있었는데, 강사님께서 스택/큐 이런 거 그냥 다 Deque로 구현하라고 말씀하셨다.
왜 그렇게 말씀하셨을까?
오늘은 강사님께서 왜 그렇게 말씀하셨는지, 그 이유를 알아보도록 하겠다.
Deque, 스택과 큐의 만능 해결사!
Deque는 "양쪽 끝에서 데이터를 넣고 뺄 수 있는 큐"라는 뜻입니다.
Deque의 장점
- 하나로 두 가지 기능: Deque는 스택(LIFO)처럼도, 큐(FIFO)처럼도 사용할 수 있습니다!
- 추출에서는 ArrayList랑 Deque 모두 매우 빠른 속도로 실행되고, 속도에서 큰 차이가 없습니다. 반면 삽입에서 속도 차이가 많이 발생하기 때문에 코딩테스트에서는 Deque를 사용하는 것이 더 바람직 해 보입니다.
Java Deque의 핵심 메서드 정리
Java의 Deque는 List처럼 인덱스로 중간 요소를 직접 건드릴 순 없고, 오직 양쪽 끝에서만 작업할 수 있습니다. 메서드 이름에 First와 Last가 붙어서 어디서 작업하는지 명확히 알 수 있습니다.
| 카테고리 | 메서드 | 설명 | 비고 (주의사항) |
|---|---|---|---|
| 추가 | offerFirst(E e) | Deque의 앞쪽(Head)에 요소를 추가합니다. | 용량 초과 시 false 반환 (안전하게 추가) |
offerLast(E e) | Deque의 뒤쪽(Tail)에 요소를 추가합니다. | 용량 초과 시 false 반환 (안전하게 추가) | |
| 제거 | pollFirst() | Deque의 앞쪽(Head) 요소를 제거하고 반환. | Deque 비어 있을 시 null 반환 (안전하게 제거) |
pollLast() | Deque의 뒤쪽(Tail) 요소를 제거하고 반환. | Deque 비어 있을 시 null 반환 (안전하게 제거) | |
| 확인 | peekFirst() | Deque의 앞쪽(Head) 요소를 제거 없이 확인. | Deque 비어 있을 시 null 반환 (안전하게 확인) |
peekLast() | Deque의 뒤쪽(Tail) 요소를 제거 없이 확인. | Deque 비어 있을 시 null 반환 (안전하게 확인) |
| 메서드 | 설명 | 예시 | 주의사항 |
|---|---|---|---|
isEmpty() | Deque가 비었는지 확인 (true/false) | while (!dq.isEmpty()) | 요소가 없을 때만 true |
size() | 현재 요소의 개수 반환 | dq.size() | 큰 Deque는 성능 이슈 가능 |
contains(o) | 특정 요소 존재 여부 확인 | dq.contains("A") | 내부 순회 필요 (느릴 수 있음) |
clear() | 모든 요소 제거 | dq.clear() | 이후 참조 주의 |
Deque<String> deque = new ArrayDeque<>();
deque.offerLast("A");
deque.offerLast("B");
deque.offerFirst("C");
System.out.println(deque); // [C, A, B]
System.out.println(deque.isEmpty()); // false
System.out.println(deque.size()); // 3
/*
* Q. contains의 작동 원리
* - Deque 내부 요소들을 처음부터 끝까지 하나씩 비교
* - equals() 메서드를 사용해서 비교
* - 같다고 판단되는 게 있으면 true, 아니면 false
*/
System.out.println(deque.contains("A")); // true
deque.clear(); // 모든 요소 삭제
System.out.println(deque); // []왜
offer/poll/peek을 추천하나요?
물론 add/remove/get도 있지만, add/remove/get는 Deque가 비어있거나 용량 제한이 있을 때 예외(Exception)를 발생시킵니다.
반면, offer/poll/peek 계열은 문제가 생겼을 때 false나 null을 반환하여 코드를 더 간결하고 안전하게 작성할 수 있게 해줍니다.
코딩테스트에서는 불필요한 예외 처리를 줄이는 것이 중요하므로, 이들을 사용하는 것이 일반적입니다.
사용
Deque<타입> 변수명 = new ArrayDeque<>();
스택(Stack)처럼 사용하고 싶을 때(LIFO):
자바에서 Deque로 스택을 구현할 때 보통 Last 보다는 First를 씁니다.
물론, Last든, First든 일관성 있게 쓰면 동작상 문제는 없지만,
자바 Deque의 스택 관련 메서드는 모두 앞쪽에 해당하며, 많은 자바 예시 코드도 이를 따르고 있습니다.
- 데이터 추가: offerFirst()
- 데이터 제거: pollFirst()
- 데이터 확인: peekFirst()
큐(Queue)처럼 사용하고 싶을 때(FIFO):
- 데이터 추가: offerLast()
- 데이터 제거: pollFirst()
- 데이터 확인: peekFirst()
코딩테스트에서 Deque를 쓰는 패턴은 거의 정해져 있어요. 자주 쓰는 형태들을 정리해드릴게요.
1. Deque<Integer> — 가장 많이 씀
정수 큐/스택, BFS 탐색, 슬라이딩 윈도우 등에서 압도적으로 많이 사용합니다.
Deque<Integer> deque = new ArrayDeque<>();
deque.addLast(1); // 뒤에 추가 (큐처럼)
deque.addFirst(2); // 앞에 추가 (스택처럼)
deque.pollFirst(); // 앞에서 꺼내기
deque.pollLast(); // 뒤에서 꺼내기예시: BFS에서 큐로 사용
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(startNode); // 큐에 시작 노드 추가
while (!queue.isEmpty()) {
int cur = queue.poll();
for (int next : graph.get(cur)) {
queue.offer(next);
}
}2. Deque<int[]> — 좌표(행, 열)를 같이 다룰 때
격자(2D 배열) 탐색 문제(BFS/DFS)에서 (row, col) 쌍을 큐에 넣어야 할 때 자주 씁니다.
Deque<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{0, 0}); // (행, 열) 좌표
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int row = cur[0];
int col = cur[1];
// 상하좌우 탐색...
}미로 탐색, 섬 개수 구하기 같은 문제에서 정말 자주 쓰는 패턴이에요.
3. Deque<String> — 단어/문자열 단위 처리
문자열을 큐/스택으로 처리할 때 (예: 괄호 검사, 후위 표기법 계산기 같은 문제).
Deque<String> stack = new ArrayDeque<>();
stack.push("(");
stack.peek(); // 맨 위 확인 (꺼내지 않음)
stack.pop(); // 꺼내기4. Deque<Character> — 괄호 짝 맞추기 같은 문제
문자 단위로 스택을 쓸 때 (괄호 검사 문제의 정석 패턴).
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(c);
} else if (c == ')') {
if (stack.isEmpty()) return false;
stack.pop();
}
}
return stack.isEmpty();빈도 순으로 정리하면
| 자료형 | 사용 빈도 | 주요 용도 |
|---|---|---|
Deque<Integer> | ⭐⭐⭐⭐⭐ | BFS, 일반 큐/스택, 숫자 처리 |
Deque<int[]> | ⭐⭐⭐⭐ | 2D 격자 BFS/DFS (좌표 쌍) |
Deque<String> | ⭐⭐⭐ | 문자열 단위 스택/큐 |
Deque<Character> | ⭐⭐⭐ | 괄호 검사 등 문자 단위 처리 |
스택으로 쓸지 큐로 쓸지에 따른 메서드 선택
Deque는 양쪽(앞/뒤) 다 추가/삭제가 가능해서, 스택처럼 쓸지 큐처럼 쓸지에 따라 메서드를 다르게 선택합니다.
// 스택처럼 쓰기 (LIFO - 마지막에 넣은 게 먼저 나옴)
deque.push(1); // = addFirst
deque.pop(); // = removeFirst
deque.peek(); // = peekFirst
// 큐처럼 쓰기 (FIFO - 먼저 넣은 게 먼저 나옴)
deque.offer(1); // = addLast
deque.poll(); // = pollFirst
deque.peek(); // = peekFirst코딩테스트 한정으로 가장 추천하는 조합: BFS 문제는 Deque<Integer> 또는 Deque<int[]>로 큐(offer/poll) 쓰고, 괄호/스택 문제는 Deque<Character> 또는 Deque<Integer>로 스택(push/pop) 쓰는 패턴이 거의 정형화되어 있어요.
