Deque - Java

Deque

• Deque(Deque = Double Ended Queue, 양방향 큐) 는 양쪽 끝(front, rear) 모두에서 삽입과 삭제가 가능한 자료구조입니다.
• Java에서는 Deque 인터페이스를 제공하며, 일반적으로 LinkedList나 ArrayDeque로 구현합니다.

구현체 비교

항목	LinkedList	ArrayDeque
구조	노드 기반 (이중 연결 리스트)	배열 기반 (원형 배열 구조)
삽입/삭제 속도	양쪽 끝 삽입/삭제 빠름 (O(1))	양쪽 끝 삽입/삭제 빠름 (O(1))
중간 접근/수정	느림 (O(n))	불가능(중간 인덱스 접근 지원 안 함)
메모리 사용	각 노드마다 추가 메모리(포인터 2개) 필요	배열 크기만큼 메모리 연속 확보 필요
성능	많은 삽입/삭제 작업에 유리	빠른 삽입/삭제 + 메모리 효율성 높음 (캐시 친화적)
null 허용	가능 (null 요소 저장 가능)	불가능 (null 저장 시 예외 발생)
초기 크기 설정	필요 없음	필요 없음 (자동 확장하지만, 내부적으로 배열 복사가 일어남)
용도 추천	데이터 삽입/삭제 빈번 + null 허용이 필요한 경우	빠른 양쪽 작업 + null 없이 높은 성능이 필요한 경우

주요 특징

자료구조	노드 기반(LinkedList) 또는 배열 기반(ArrayDeque)
크기 조정	동적으로 조정 가능 (LinkedList는 노드 추가, ArrayDeque는 배열 확장)
접근 속도	양쪽 끝에 대해 빠른 접근 (O(1))
삽입/삭제 속도	양쪽 끝 삽입/삭제 모두 빠름 (O(1))
중복 허용	O (같은 값을 여러 번 저장 가능)
null 허용	구현체에 따라 다름 (LinkedList는 허용, ArrayDeque는 허용하지 않음)

대표 메서드

package structure.deque;

import java.util.Deque;

public class DequeClass {

    private final Deque<Integer> deque;

    public DequeClass(Deque<Integer> deque) {
        this.deque = deque;
    }

    // 덱의 뒤(rear)에 값을 추가합니다.
    // 시간 복잡도: O(1)
    // 예외 발생: NullPointerException - deque가 null인 경우
    public Deque<Integer> offer(int value) {
        this.deque.offer(value);
        return this.deque;
    }

    // 덱의 앞(front)에 값을 추가합니다.
    // 시간 복잡도: O(1)
    // 예외 발생: NullPointerException - deque가 null인 경우
    public Deque<Integer> offerFirst(int value) {
        this.deque.offerFirst(value);
        return this.deque;
    }

    // 덱의 뒤(rear)에 값을 추가합니다.
    // 시간 복잡도: O(1)
    // 예외 발생: NullPointerException - deque가 null인 경우
    public Deque<Integer> offerLast(int value) {
        this.deque.offerLast(value);
        return this.deque;
    }

    // 덱의 앞(front) 요소를 제거하고 반환합니다.
    // 시간 복잡도: O(1)
    // 예외 발생: NullPointerException - deque가 null인 경우
    public Integer poll() {
        return this.deque.poll();
    }

    // 덱의 앞(front) 요소를 제거하고 반환합니다.
    // 시간 복잡도: O(1)
    // 예외 발생: NullPointerException - deque가 null인 경우
    public Integer pollFirst() {
        return this.deque.pollFirst();
    }

    // 덱의 뒤(rear) 요소를 제거하고 반환합니다.
    // 시간 복잡도: O(1)
    // 예외 발생: NullPointerException - deque가 null인 경우
    public Integer pollLast() {
        return this.deque.pollLast();
    }

    // 덱의 앞(front) 요소를 반환합니다(제거하지 않음).
    // 시간 복잡도: O(1)
    // 예외 발생: NullPointerException - deque가 null인 경우
    public Integer peek() {
        return this.deque.peek();
    }

    // 덱의 앞(front) 요소를 반환합니다(제거하지 않음).
    // 시간 복잡도: O(1)
    // 예외 발생: NullPointerException - deque가 null인 경우
    public Integer peekFirst() {
        return this.deque.peekFirst();
    }

    // 덱의 뒤(rear) 요소를 반환합니다(제거하지 않음).
    // 시간 복잡도: O(1)
    // 예외 발생: NullPointerException - deque가 null인 경우
    public Integer peekLast() {
        return this.deque.peekLast();
    }

    // 덱의 모든 요소를 제거합니다.
    // 시간 복잡도: O(1)
    // 예외 발생: NullPointerException - deque가 null인 경우
    public void clear() {
        this.deque.clear();
    }

    // 덱이 비어 있는지 확인합니다.
    // 시간 복잡도: O(1)
    // 예외 발생: NullPointerException - deque가 null인 경우
    public boolean isEmpty() {
        return this.deque.isEmpty();
    }

    // 덱의 요소 개수를 반환합니다.
    // 시간 복잡도: O(1)
    // 예외 발생: NullPointerException - deque가 null인 경우
    public int size() {
        return this.deque.size();
    }

    // 덱에 지정된 값이 포함되어 있는지 확인합니다.
    // 시간 복잡도: O(n) (덱을 순차적으로 검색)
    // 예외 발생: NullPointerException - deque가 null인 경우
    public boolean contains(int value) {
        return this.deque.contains(value);
    }
}