덱(Deque, Double-Ended Queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 선형 자료구조다.
스택(Stack)과 큐(Queue)의 기능을 모두 포함하고 있어 활용도가 매우 높다.
덱의 주요 동작
- Front 삽입/삭제: 큐의 앞부분에서 데이터를 관리한다.
- Rear 삽입/삭제: 큐의 뒷부분에서 데이터를 관리한다.
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeEx {
public static void main(String[] args) {
Deque<Integer> deque = new ArrayDeque<>();
// 1. 후단 삽입 (Queue의 offer와 동일)
deque.addLast(10);
deque.addLast(20);
// 2. 전단 삽입
deque.addFirst(5);
// 현재 상태: [5, 10, 20]
// 3. 전단 삭제 (Queue의 poll과 동일)
System.out.println(deque.removeFirst()); // 5
// 4. 후단 삭제 (Stack의 pop과 동일)
System.out.println(deque.removeLast()); // 20
}
}
구현 방식
- 이중 연결 리스트 (Doubly Linked List): 각 노드가 이전과 다음 노드를 모두 가리키므로 양방향 처리에 최적화되어 있다.
- 원형 배열 (Circular Array): 배열의 시작과 끝을 연결하여 메모리를 효율적으로 사용한다.
자바의ArrayDeque가 이 방식을 채택하고 있다.
활용 사례
- 슬라이딩 윈도우 (Sliding Window): 특정 범위 내의 최댓값이나 최솟값을 효율적으로 찾을 때 사용한다.
- 실행 취소 (Undo) 및 다시 실행 (Redo): 양방향 기록 관리가 필요한 기능에 적합하다.
- 스케줄링 알고리즘: 우선순위에 따라 앞뒤로 작업을 배치해야 하는 경우에 사용한다.
P.S
덱은 상황에 따라 스택이나 큐로 자유롭게 변신할 수 있는 유연한 자료구조다.
특히 자바에서는 Stack 클래스보다 성능이 우수한 ArrayDeque를 사용하는 것이 권장되는 것 같다.
