Deque 자료 구조

"Deque" 는 "Double Ended Queue"의 약자로, 이 이름에서 알수 있듯이, Deque는 양쪽 끝에서 요소를 추가하거나 제거할 수 있다. Deque는 일반적인 큐(Queue)와 스택(Stack)의 기능을 모두 포함하고 있어, 매우 유연한 자료 구조이다.

• offerFirst() : 앞에 추가한다.
• offerLast() : 뒤에 추가한다.
• pollFirst() : 앞에서 꺼낸다.
• pollLast() : 뒤에서 꺼낸다.

 

Deque의 대표적인 구현체는 ArrayDeque, LinkedList가 있다.

 

 

package collection.deque;

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

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

        //데이터 추가
        deque.offerFirst(1);
        System.out.println(deque);
        deque.offerFirst(2);
        System.out.println(deque);
        deque.offerLast(3);
        System.out.println(deque);
        deque.offerLast(4);
        System.out.println(deque);

        //다음에 꺼낼 데이터 확인(꺼내지 않고 조회만)
        System.out.println("deque.peekFirst() = " + deque.peekFirst());
        System.out.println("deque.peekLast() = " + deque.peekLast());

        //데이터 꺼내기
        System.out.println("deque.pollFirst() = " + deque.pollFirst());
        System.out.println("deque.pollFirst() = " + deque.pollFirst());
        System.out.println("deque.pollLast() = " + deque.pollLast());
    }
}

 

실행 결과

[1]
[2, 1]
[2, 1, 3]
[2, 1, 3, 4]
deque.peekFirst() = 2
deque.peekLast() = 4
deque.pollFirst() = 2
deque.pollFirst() = 1
deque.pollLast() = 4

 

입력 순서는 다음과 같다.

• 앞으로 1을 추가한다. [1]
• 앞으로 2를 추가한다 [2,1] (앞으로 2를 추가했으므로 기존에 있던 1이 뒤로 밀려난다)
• 뒤로 3을 추가한다 [2,1,3]
• 뒤로 4를 추가한다 [2,1,3,4]

앞에서 2번 꺼내면 2,1이 꺼내진다. 다음으로 뒤에서 2번 꺼내면 4,3이 꺼내진다.

 

 

Deque 구현체와 성능 테스트

Deque의 대표적인 구현체는 ArrayDeque와 LinkedList가 있다. 이 둘 중에 ArrayDeque가 모든 면에서 더 빠르다.

 

둘의 차이는 ArrayList vs LinkedList의 차이와 비슷한데, 작동 원리가 하나는 배열을 하나는 동적 노드 링크를 사용하기 때문이다.

ArrayDeque는 추가로 특별한 원형 큐 자료 구조를 사용하는데, 덕분에 앞, 뒤 입력 모두 O(1)의 성능을 제공한다. 물론 LinkedList도 앞 뒤 입력 모두 O(1)의 성능을 제공한다.

이론적으로 LinkedList가 삽입 삭제가 자주 발생할 때 더 효율적이 수 있지만, 현대 컴퓨터 시스템의 메모리 접근 패턴, CPU캐시 최적화 등을 고려할 때 배열을 사용하는 ArrayDeque가 실제 사용 환경에서 더 나은 성능을 보여주는 경우가 많다.