[JAVA] Deque (데크, 덱) 자료구조 알아보기

 

자바를 활용하다 보면 데이터를 먼저 들어온 순서대로 처리해야 하는 상황과 함께 데이터를 양쪽 끝에서 효율적으로 추가하거나 삭제해야 하는 경우가 있습니다. 이때 사용할 수 있는 것이 덱(Deque)입니다.

 

이번 포스팅에서는 덱(Deque)에 대해서 알아보겠습니다.

 

Deque 덱이란 ❓

 

덱(Deque)은 자바에서 제공하는 자료구조 중 하나로, 양 끝에서 삽입과 삭제가 모두 가능한 더블 엔드 큐(Double Ended Queue)의 줄임말의선형 자료구조입니다.

 

• 큐(Queue)에서는 FIFO(First-In-First-Out) 방식으로 동작
• 스택(Stack)에서는 LIFO(Last-In-First-Out) 방식으로 동작

 

덱은 큐(Queue)와 스택(Stack)의 특징을 모두 가지고 있어서 양쪽 끝에서 빠르게 데이터를 추가하거나 삭제할 수 있으며, 다양한 상황에서 유연하게 사용할 수 있습니다.

 

Deque의 메서드

삽입/추가 메서드

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

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

        // addFirst 메서드를 사용하여 요소 추가
        deque.addFirst(1);
        deque.addFirst(2);
        deque.addFirst(3);

        // addLast 메서드를 사용하여 요소 추가
        deque.addLast(4);
        deque.addLast(5);

        // Deque 출력
        System.out.println("Deque after insertions: " + deque);
    }
}

 

실행 결과

Deque after insertions: [3, 2, 1, 4, 5]

 

• addFirst(E e)
  •  덱의 맨 앞에 요소 추가
• addLast(E e)
  •  덱의 맨 뒤에 요소 추가
• offerFirst(E e)
  •  덱의 맨 앞에 요소 추가, 공간이 부족할 경우 false 반환
• offerLast(E e)
  •  덱의 맨 뒤에 요소 추가, 공간이 부족할 경우 false 반환

삭제 메서드

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

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

        // 요소 추가
        deque.addFirst(1);
        deque.addLast(2);
        deque.addFirst(3);
        deque.addLast(4);

        // removeFirst 메서드를 사용하여 요소 제거
        int removedFirst = deque.removeFirst();
        System.out.println("Removed first element: " + removedFirst);

        // removeLast 메서드를 사용하여 요소 제거
        int removedLast = deque.removeLast();
        System.out.println("Removed last element: " + removedLast);

        // Deque 출력
        System.out.println("Deque after removals: " + deque);
    }
}

 

실행 결과

Removed first element: 3
Removed last element: 4
Deque after removals: [1, 2]

 

• removeFirst()
  •  덱의 맨 앞 요소 제거, 덱이 비어있을 경우 예외 발생
• removeLast()
  •  덱의 맨 뒤 요소 제거, 덱이 비어있을 경우 예외 발생
• pollFirst()
  •  덱의 맨 앞 요소 제거, 덱이 비어있을 경우 null 반환
• pollLast()
  •  덱의 맨 뒤 요소 제거, 덱이 비어있을 경우 null 반환

접근 메서드

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

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

        // 요소 추가
        deque.addFirst(1);
        deque.addLast(2);
        deque.addFirst(3);
        deque.addLast(4);

        // getFirst 메서드를 사용하여 맨 앞 요소 접근
        int firstElement = deque.getFirst();
        System.out.println("First element: " + firstElement);

        // getLast 메서드를 사용하여 맨 뒤 요소 접근
        int lastElement = deque.getLast();
        System.out.println("Last element: " + lastElement);

        // Deque 출력
        System.out.println("Deque: " + deque);
    }
}

 

실행 결과

First element: 3
Last element: 4
Deque: [3, 1, 2, 4]

 

• getFirst()
  •  덱의 맨 앞 요소 반환, 덱이 비어있을 경우 예외 발생
• getLast()
  •  덱의 맨 뒤 요소 반환, 덱이 비어있을 경우 예외 발생
• peekFirst()
  • 덱의 맨 앞 요소 반환, 덱이 비어있을 경우 null 반환
• peekLast()
  • 덱의 맨 뒤 요소 반환, 덱이 비어있을 경우 null 반환

기타 메서드

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

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

        // 요소 추가
        deque.addFirst(1);
        deque.addLast(2);
        deque.addFirst(3);
        deque.addLast(4);

        // size 메서드를 사용하여 덱의 크기 확인
        System.out.println("Size of deque: " + deque.size());

        // isEmpty 메서드를 사용하여 덱이 비어있는지 확인
        System.out.println("Is deque empty? " + deque.isEmpty());

        // Deque 출력
        System.out.println("Deque: " + deque);
    }
}

 

실행 결과

Size of deque: 4
Is deque empty? false
Deque: [3, 1, 2, 4]

 

• size()
  • 덱에 포함된 요소의 수 반환
• isEmpty()
  • 덱이 비어있는지 여부 반환
• iterator()
  • 덱의 요소를 반복하는 Iterator 반환

 

 

ArrayDeque & LinkedList

ArrayDeque와 LinkedList는 자바에서 제공하는 두 가지 주요 덱(deque) 구현체입니다.

 

ArrayDeque (배열 기반 덱)

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

public class ArrayDequeExample {
    public static void main(String[] args) {
        // ArrayDeque 생성
        Deque<Integer> arrayDeque = new ArrayDeque<>();

        // 요소 추가: addFirst(), addLast(), offerFirst(), offerLast()
        arrayDeque.addFirst(1);
        arrayDeque.addLast(2);
        arrayDeque.offerFirst(3);
        arrayDeque.offerLast(4);

        // 출력
        System.out.println("ArrayDeque: " + arrayDeque); // [3, 1, 2, 4]

        // 요소 삭제: removeFirst(), removeLast(), pollFirst(), pollLast()
        arrayDeque.removeFirst();
        arrayDeque.pollLast();

        // 출력
        System.out.println("ArrayDeque after removal: " + arrayDeque); // [1, 2]
    }
}

 

실행 결과 

ArrayDeque: [3, 1, 2, 4]
ArrayDeque after removal: [1, 2]

 

• 구현 방식
  •  내부적으로 배열을 사용하여 구현된 덱입니다.
• 저장 방식
  •  배열의 크기가 자동으로 조절되며, 가변 크기로 관리됩니다.
• 시간 복잡도
  •  인덱스를 사용하여 O(1)의 시간 복잡도로 요소를 추가하거나 제거할 수 있습니다.
• 장점
  • 메모리 접근이 배열 기반으로 연속적이어서 캐시 효율성이 높을 수 있습니다.
  • 빠른 접근과 삽입/삭제 연산을 지원합니다.
• 단점
  • 요소를 삽입하거나 삭제할 때 배열 크기를 조정해야 하는 경우가 있어 비용이 발생할 수 있습니다.

LinkedList (연결 리스트 기반 덱)

import java.util.Deque;
import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // LinkedList 생성
        Deque<Integer> linkedList = new LinkedList<>();

        // 요소 추가: addFirst(), addLast(), offerFirst(), offerLast()
        linkedList.addFirst(1);
        linkedList.addLast(2);
        linkedList.offerFirst(3);
        linkedList.offerLast(4);

        // 출력
        System.out.println("LinkedList: " + linkedList); // [3, 1, 2, 4]

        // 요소 삭제: removeFirst(), removeLast(), pollFirst(), pollLast()
        linkedList.removeFirst();
        linkedList.pollLast();

        // 출력
        System.out.println("LinkedList after removal: " + linkedList); // [1, 2]
    }
}

 

실행 결과

 

LinkedList: [3, 1, 2, 4]
LinkedList after removal: [1, 2]

 

• 구현 방식
  •  노드들이 링크로 연결되어 구현된 덱입니다.
• 저장 방식
  •  각 노드는 데이터와 다음 노드를 가리키는 링크를 가지고 있습니다.
• 시간 복잡도
  •  양쪽 끝에서의 삽입/삭제 연산은 O(1)의 시간 복잡도를 가지며, 중간에 삽입/삭제는 O(n)입니다.
• 장점:
  • 중간 삽입/삭제가 자주 일어나는 경우에 유리합니다.
  • 동적으로 크기가 조정되어 메모리를 효율적으로 사용할 수 있습니다.
• 단점:
  • 메모리 할당과 노드 간의 링크 관리가 필요하여 추가적인 메모리 소비가 발생할 수 있습니다.
  • 배열에 비해 캐시 효율성이 낮을 수 있습니다.

 

따라서 선택기준 은 다음과 같습니다.

• ArrayDeque: 요소의 추가나 삭제가 빈번하게 일어나고, 메모리 접근 시간이 중요할 때 유리합니다.
• LinkedList: 중간 삽입/삭제가 많이 발생하거나 덱의 크기가 동적으로 변할 때 유리합니다.