알고리즘-자료구조-덱

개요

• Double Ended Queue를 의미한다.
• 덱(Deque)는 데이터를 앞(front)와 뒤(rear) 양쪽에서 자유롭게 삽입과 삭제가 가능한 자료구조이다.

특징

• 기본 기능기능 설명

  addFirst(x)	앞에 요소 추가
  addLast(x)	뒤에 요소 추가
  removeFirst()	앞에 요소 제거
  removeLast()	뒤에 요소 제거
  peekFirst()	앞 요소 확인
  peekLast()	뒤 요소 확인

사용법

• Java에서 Deque는 ArrayDeque 또는 LinkedList로 구현하여 사용한다.
• Stack이나 Queue보다 더 유연한 구조를 가지고 있다.

import java.util.LinkedList;
import java.util.Deque;

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

        deque.addFirst("A");
        deque.addLast("B");
        deque.addLast("C");

        System.out.println(deque.removeFirst()); // A
        System.out.println(deque.removeLast());   // C
    }
}

사례

• 스택처럼 사용: addLast, removeLast 사용
• 큐처럼 사용: addLast, removeFirst 사용
• 슬라이딩 윈도우 최적화: 특정 범위 내 최대/최소값을 빠르게 찾을 때 사용
• 회전 캐시 / 양방향 탐색: 앞뒤로 자유롭게 접근 가능한 작업에 적합

정리

• 스택과 큐를 모두 포함하는 확장된(앞,뒤) 자료구조이다.
• 양쪽에서 자유롭게 삽입과 삭제가 필요한 경우에 사용한다.

참고

• Java에서 Stack은 레거시 클래스이고 ArrayDeque는 스택/큐보다 훨씬 빠르고 가볍기에 공식적으로도 Deque의 사용을 권장한다.
• 무조건 Deque를 사용할 필요는 없고 의도가 명확할 때는 stack이나 queue를 그대로 쓰는것이 좋을때도 있다.