덱(Deque)

Deque

자바에서 Deque는 java.util.Deque를 import하여 사용할 수 있으며, 자바의 Collection 인터페이스를 상속받은 인터페이스이다. 즉, 자바 컬렉션 프레임워크 중 하나이다. 자바에서 Deque를 사용할 때는 인터페이스이기 때문에 아래 코드와 같이 구현체로 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스를 생성해서 사용한다.

Deque<Integer> D = new ArrayDeque<>();
Deque<Integer> D = new LinkedBlockingDeque<>();
Deque<Integer> D = new ConcurrentLinkedDeque<>();
Deque<Integer> D = new LinkedList<>();

Deque 개념

Deque(덱 혹은 데크)은 Double Ended Queue의 줄임말로 큐의 양쪽으로 요소의 삽입과 삭제를 수행할 수 있는 자료구조이다. (큐의 경우는 한쪽으로만 요소의 삽입과 삭제가 가능했다.)

Deque은 양쪽 중 어느쪽으로 입력하고 출력하느냐에 따라서 스택(Stack)으로 사용할 수 있고, 큐(Queue)로도 사용할 수 있다. 즉, 덱은 스택과 큐를 합친걸로도 볼 수 있다. 특히 한쪽으로만 입력 가능하도록 설정한 덱을 스크롤(scroll)이라고 하며, 한쪽으로만 출력가능하도록 설정한 덱을 셀프(shelf)라고 한다.

Deque에는 다음과 같은 메서드가 있다.

• addFirst() : 맨 처음에 데이터 추가
• addLast() : 맨 마지막에 데이터 추가
• removeFirst() : 맨 처음에 데이터 삭제
• removeLast() : 맨 마지막에 데이터 삭제
• peekFirst() : 맨 처음에 데이터 조회
• peekLast() : 맨 마지막에 데이터 조회
• isEmpty() : 큐가 비어있는지 체크

Queue와 마친가지로 addFirst(), offerFirst()과 같은 동일한 기능의 메서드를 지원한다. 둘의 차이점은 예외를 발생시킬 것인지 아닌지에 있다.

addFirst() vs offerFirst()

add()	offer()
값 추가 성공시 true 반환	값 추가 성공시 true 반환
덱이 꽉 찬 경우 IllegalStateException 발생	값 추가 실패시 false 반환

removeFirst() vs pollFirst()

remove()	poll()
삭제된 데이터 반환	삭제된 데이터 반환
덱이 비어있는 경우 NoSuchElementException 발생	덱이 비어있는 경우 null 반환

getFirst() vs peekFirst()

getFirst()	peekFirst()
덱의 맨 앞에 있는 데이터 반환	덱의 맨 앞에 있는 데이터 반환
덱이 비어있는 경우 NoSuchElementException 발생	덱이 비어있는 경우 null 반환

결국 문제가 있는 상황에서 Exception을 발생시키는지(addFirst, removeFirst, getFirst), 아니면 그냥 null 혹은 false를 반환시키는지(offerFirst, pollFirst, peekFirst)에 차이가 있다.

Deque 활용 예시

• 원형 덱을 활용한 알고리즘
  • 덱은 원형 형태로 구현될 수 있는데, 이는 알고리즘에서 순환적인 작업을 수행해야 할 때 유용하다.
• 문서 편집 프로그램의 Undo/Redo
  • 문서 편집 프로그램에서 덱은 사용자의 작업 이력을 관리하는 데 활용된다. 사용자가 작업을 실행하거나 취소할 때마다 덱에 해당 작업을 추가하고 제거함으로써 Undo와 Redo 기능을 구현할 수 있다.

Deque 사용하기

public class Main {
    public static void main(String[] args) throws IOException {
        Deque<Integer> D = new ArrayDeque<>();
        D.addFirst(1);
        D.addFirst(2);
        D.addLast(3);
        D.addLast(4);
        System.out.println(D.getFirst()); //2
        System.out.println(D.getLast()); //4

        D.removeFirst();
        D.removeLast();
        System.out.println(D.getFirst()); //1
        System.out.println(D.getLast()); //3
    }
}

Reference

• https://soft.plusblog.co.kr/24
• https://newcodingman.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-deque