[자료구조]덱/Dequeue(데크) Doubly-ended Queue

덱(Dequeue)은 Doubly-ended Queue의 약자로서 양쪽 끝에서 추가, 삭제가 가능한 선형 구조 형태의 자료구조다.

데큐, 데크라고도 하며 스택과 큐의 장점을 모아서 만들어진 형태를 보인다.

추가, 삭제가 되는 부분의 명칭을 Front, Rear라고 칭한다.

Dequeue의 기본 흐름은 아래 그림과 같다.

- 입력과 출력은 양 방향으로 가능하다.
- 입력과 출력의 순서를 마음대로 정할 수 있다.
- Enqueue(입력) 및 Dequeue(삭제)의 실행 속도는 O(1)이다.

---

덱에는 제약조건을 걸어 사용 목적을 달리하는 구조 또한 있다.

바로 Scroll과 Shelf다.

- Scroll : 입력제한 덱

입력을 한곳에만 제한을 주는 덱
(삭제는 양방향에서 가능)

- Shelf : 출력(삭제)제한 덱

출력을 한곳에만 제한을 주는 덱
(가는 양방향 가능)

이렇게 큐에 대한 구조를 알아봤고

특징을 정리하자면

데이터를 양쪽에 삽입, 삭제가 가능하다.
데이터 입력 순서와 상관없이 출력 순서를 조절 가능하다.
스택과 큐의 장점을 모은 자료구조로 볼 수 있다.

public static void main(String[] args) {
        Deque<String> test = new ArrayDeque<>();
        test.offer("1");
        test.offer("2");
        test.offer("3");
        
        test.offerFirst("firstTest");
        test.offerLast("rearTest");
       
        System.out.println(test.pollFirst());
        System.out.println(test.pollLast());

    }

위 코드와 같이 자바에서 사용이 가능하다.

기본적으로  offerFirst 메서드가 디폴트로 이뤄져있으며
직접 offerFirst, offerLast를 통해 앞에 넣을지 뒤에 넣을지 통제가 가능하다.
이 외에도  poll 또한 First와 Last를 통해 방향 통제가 가능하다.

특이한점은 큐와 같이 pop과 add,push가 있으나

offer나 poll사용이 좀 더 용이하다 이유는 값이 없거나 용량을 초과하더라도 null에 대해 문제가 발생하지 않기 때문이다.