[자료구조] (5) Deque(덱)이란 무엇인가?

Deque(덱) 정의

• Deque(Double-Ended Queue)는 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조다.
• 스택(한쪽 입출력), 큐(한쪽 입력/한쪽 출력)과 다르게 덱은 양쪽 모두 입출력이 가능하다.

덱의 주요 연산

addFirst(item)	앞쪽에 데이터 삽입
addLast(item)	뒤쪽에 데이터 삽입
removeFirst()	앞쪽 데이터 삭제
removeLast()	뒤쪽 데이터 삭제
peekFirst()	앞쪽 데이터 조회
peekLast()	뒤쪽 데이터 조회

덱의 구현 방법

• 배열 기반(ArrayDeque)
  • 빠른 인덱스 접근 가능
  • 공간이 꽉 차면 크기 확장(리사이즈) 필요
• 연결 리스트 기반(LinkedListDeque)
  • 삽입/삭제가 O(1)로 빠름
  • 메모리 사용량이 많음 (노드 구조)

덱의 사용 사례

• 회문(팰린드롬) 검사
  • 앞과 뒤를 동시에 비교할 때 유용
• 슬라이딩 윈도우 최댓값 문제
  • 윈도우 범위 내 최대값을 빠르게 찾을 때 사용
• 캐시 구현(LRU Cache)
  • 가장 오래된 항목을 앞에서 제거

덱 vs 스택/큐 비교

자료구조	삽입/삭제	방향 특징
스택	한쪽 끝(Top)만	LIFO
큐	앞 삭제, 뒤 삽입	FIFO
덱	양쪽 삽입/삭제	유연한 입출력

Java 코드

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeExample {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();

        deque.addFirst(1); // 앞에 삽입
        deque.addLast(2);  // 뒤에 삽입
        System.out.println(deque.peekFirst()); // 1
        System.out.println(deque.peekLast());  // 2

        deque.removeFirst(); // 앞에서 제거
        deque.removeLast();  // 뒤에서 제거
    }
}