230208 Deque, Double Ended Queue

양쪽 끝에서 삽입/삭제가 가능한 자료구조

자바에서 Deque 인터페이스는 java.util 패키지에서 제공

구현 클래스는 LinkedList, ArrayDeque 등

• LinkedList 클래스는 링크드 리스트 기반으로 구현되어 빠른 중간 삽입/삭제 속도를 제공하지만, 느린 인덱스 기반 접근 속도

• ArrayDeque 클래스는 배열 기반으로 구현되어 빠른 인덱스 기반 접근 속도를 제공하지만, 느린 중간 삽입/삭제 속도

• 즉, 사용하는 용도에 따라 LinkedList와 ArrayDeque 중 적합한 것을 선택하여 사용

예시

아래 코드는 ArrayDeque를 사용하여 Deque에 정수 값을 삽입하고, 양쪽 끝에서 삭제하는 예시

import java.util.ArrayDeque;

public class DequeExample {
    public static void main(String[] args) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        
        // 양쪽 끝에서 삽입
        deque.addFirst(10);
        deque.addLast(20);
        
        // 양쪽 끝에서 삭제
        int first = deque.removeFirst();
        int last = deque.removeLast();
        
        System.out.println("First Element: " + first);
        System.out.println("Last Element: " + last);
    }
}

// 실행 결과:
// First Element: 10
// Last Element: 20