Deque

Deque란

Deque(데크)란 Double Ended Queue의 줄임말로, 양쪽 끝에서 삽입과 삭제가 모두 가능한 선형 자료구조를 의미합니다. 즉, 스택과 큐를 합쳐 놓은 것과 같은 형태를 가지고 있습니다.

Deque는 배열(Array)과 연결 리스트(Linked List)를 이용해 구현할 수 있습니다. 이 중 배열로 구현된 Deque는 원형 배열을 이용하여 구현하는 것이 일반적입니다. 데크에서 가장 중요한 점은 삽입과 삭제 연산이 양쪽 끝에서 모두 O(1)의 시간 복잡도를 가진다는 것입니다.

Deque의 연산

1. addFirst(E e): Deque의 맨 앞에 요소를 추가합니다.
2. addLast(E e): Deque의 맨 뒤에 요소를 추가합니다.
3. offerFirst(E e): Deque의 맨 앞에 요소를 추가하고, 만약 Deque가 꽉 찬 경우 false를 반환합니다.
4. offerLast(E e): Deque의 맨 뒤에 요소를 추가하고, 만약 Deque가 꽉 찬 경우 false를 반환합니다.
5. removeFirst(): Deque의 맨 앞의 요소를 제거하고 반환합니다.
6. removeLast(): Deque의 맨 뒤의 요소를 제거하고 반환합니다.
7. pollFirst(): Deque의 맨 앞의 요소를 제거하고 반환합니다. 만약 Deque가 비어있는 경우 null을 반환합니다.
8. pollLast(): Deque의 맨 뒤의 요소를 제거하고 반환합니다. 만약 Deque가 비어있는 경우 null을 반환합니다.
   9.getFirst(): Deque의 맨 앞의 요소를 반환합니다. 만약 Deque가 비어있는 경우 NoSuchElementException이 발생합니다.
9. getLast(): Deque의 맨 뒤의 요소를 반환합니다. 만약 Deque가 비어있는 경우 NoSuchElementException이 발생합니다.
10. peekFirst(): Deque의 맨 앞의 요소를 반환합니다. 만약 Deque가 비어있는 경우 null을 반환합니다.
11. peekLast(): Deque의 맨 뒤의 요소를 반환합니다. 만약 Deque가 비어있는 경우 null을 반환합니다.
12. removeFirstOccurrence(Object o): Deque에서 주어진 요소와 일치하는 첫 번째 요소를 제거합니다. 만약 요소가 발견되지 않으면 Deque를 변경하지 않습니다.
13. removeLastOccurrence(Object o): Deque에서 주어진 요소와 일치하는 마지막 요소를 제거합니다. 만약 요소가 발견되지 않으면 Deque를 변경하지 않습니다.
14. add(E e): Deque의 맨 뒤에 요소를 추가합니다.
15. offer(E e): Deque의 맨 뒤에 요소를 추가하고, 만약 Deque가 꽉 찬 경우 false를 반환합니다.
16. remove(): Deque의 맨 앞의 요소를 제거하고 반환합니다.
17. poll(): Deque의 맨 앞의 요소를 제거하고 반환합니다. 만약 Deque가 비어있는 경우 null을 반환합니다.
18. element(): Deque의 맨 앞의 요소를 반환합니다. 만약 Deque가 비어있는 경우 NoSuchElementException이 발생합니다.
19. peek(): Deque의 맨 앞의 요소를 반환합니다. 만약 Deque가 비어있는 경우 null을 반환합니다.
20. push(E e): Deque의 맨 앞에 요소를 추가합니다.
21. pop(): Deque의 맨 앞의 요소를 제거하고 반환합니다. 만약 Deque가 비어있는 경우 NoSuchElementException이 발생합니다.

Deque의 활용

1. 슬라이딩 윈도우(Sliding Window) 문제 해결
   슬라이딩 윈도우란, 배열이나 연속된 데이터에서 일정 범위의 부분집합을 연속적으로 탐색하는 방법을 의미합니다. 이때 Deque를 이용하면 O(n)의 시간 복잡도로 슬라이딩 윈도우 문제를 해결할 수 있습니다.

2. 매치 메이킹(Match Making) 시스템에서 매칭 대기열 관리
   온라인 게임에서 매치 메이킹 시스템은 여러 사용자를 매칭하여 게임을 시작할 수 있는 상태로 만듭니다. 이때 Deque를 사용하여 매칭 대기열을 관리하면, 매칭 대기열에서 매칭이 되지 않은 사용자를 쉽게 제거하고 새로운 사용자를 추가할 수 있습니다.

3. 브라우저의 뒤로 가기, 앞으로 가기 기능 구현
   브라우저의 뒤로 가기, 앞으로 가기 기능은 방문한 페이지들을 스택(Stack)에 저장하여 관리합니다. 이때 Deque를 사용하여 스택을 구현하면, 뒤로 가기, 앞으로 가기를 O(1)의 시간 복잡도로 처리할 수 있습니다.

Deque의 구현

Java에서 Deque를 구현하는 방법은 크게 2가지가 있습니다.

1. ArrayDeque
2. LinkedList

ArrayDeque는 내부적으로 배열을 사용하여 Deque를 구현하고, LinkedList는 내부적으로 연결 리스트를 사용하여 Deque를 구현합니다.

1. ArrayDeque
   ArrayDeque는 내부적으로 배열을 사용하여 구현되며, 인덱스로 직접 요소에 접근하므로 특정 인덱스의 요소를 조회하는 것이 O(1)의 시간 복잡도를 가집니다. 이러한 이유로 ArrayDeque는 큐나 스택 같이 많은 요소를 추가하거나 삭제하는 연산을 수행할 때 더 빠른 성능을 보입니다.

import java.util.ArrayDeque;

public class ArrayDequeExample {
    public static void main(String[] args) {
        // create a new ArrayDeque
        ArrayDeque<String> deque = new ArrayDeque<>();

        // add elements to the deque
        deque.addFirst("One");
        deque.addLast("Two");
        deque.offerFirst("Three");
        deque.offerLast("Four");

        // print the deque
        System.out.println("Deque: " + deque);

        // remove elements from the deque
        deque.removeFirst();
        deque.removeLast();

        // print the deque after removing elements
        System.out.println("Deque after removing elements: " + deque);
    }
}

2. LinkedList
   반면에 LinkedList는 내부적으로 링크드 리스트를 사용하여 구현되며, 요소를 저장할 때마다 노드 객체를 생성하고 참조를 저장하기 때문에 공간을 많이 차지합니다. LinkedList에서는 특정 인덱스의 요소를 조회하기 위해서는 링크드 리스트를 탐색해야 하므로 조회 연산이 O(n)의 시간 복잡도를 가집니다. 하지만 중간에 요소를 추가하거나 삭제하는 작업은 O(1)의 시간 복잡도를 가집니다.

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // create a new LinkedList
        LinkedList<String> deque = new LinkedList<>();

        // add elements to the deque
        deque.addFirst("One");
        deque.addLast("Two");
        deque.offerFirst("Three");
        deque.offerLast("Four");

        // print the deque
        System.out.println("Deque: " + deque);

        // remove elements from the deque
        deque.removeFirst();
        deque.removeLast();

        // print the deque after removing elements
        System.out.println("Deque after removing elements: " + deque);
    }
}

Deque를 구현할 때, 요소 추가와 삭제가 자주 일어나는 경우 ArrayDeque를 사용하면 좋고, 요소 조회가 더 많이 일어나는 경우 LinkedList를 사용하는 것이 좋습니다.

ArrayDeque와 LinkedList

ArrayDeque에서 맨 마지막 요소를 pop으로 삭제하고 반환하면 해당 공간은 비어 있지만, 배열의 크기는 줄어들지 않습니다. ArrayDeque 내부에서는 삭제된 위치에 null 값을 저장하여 해당 요소가 더 이상 사용되지 않도록 표시하는 방식으로 요소를 제거합니다.

ArrayDeque는 내부적으로 Array(고정 크기)을 사용하지만, 배열의 크기를 동적으로 조절할 수 있습니다. 따라서, 요소를 추가할 때 배열이 꽉 차면 더 큰 배열을 만들어 기존 요소를 복사하고, 요소를 삭제할 때 배열의 크기가 사용 중인 요소의 수보다 크면 배열의 크기를 줄이는 등 동적인 크기 조절이 가능합니다.

이와 다르게 LinkedList는 removeFirst(), removeLast() 메소드를 사용해서 맨 앞이나 뒤의 요소를 제거하여 반환하고 난 후 해당 노드가 가비지 컬렉션에 의해 메모리에서 제거됩니다. 새로운 요소를 추가할 때는 새로운 노드를 생성하고 이전 노드와 연결하는 과정을 거칩니다.

정리하자면 ArrayDeque는 고정 길이인 Array를 통해 구현됐기 때문에 크기가 변해야 할 때는 새로운 Array를 생성하고 원소를 넣는 과정이 필요하고 LinkedList는 작업하고자 하는 요소가 존재하는 노드를 생성하거나 제거하고, 생성한 후에는 이전 노드와 연결하는 과정이 있고, 제거할때는 가바지 컬렉션이 해당 노드를 제거하게 됩니다.