[자료구조] 자바 덱(Deque)의 클래스 사용하기

카프카의 소스코드를 보던 중 내부에서 Deque 클래스를 사용한 부분을 보게 되었다. Deque(덱 혹은 데크)은 Double-Ended Queue의 줄임말로 큐의 양쪽으로 엘리먼트의 삽입과 삭제를 수행할 수 있는 자료구조를 의미한다.

 

참고 : 월급쟁이의 경제적 사유

 

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

 

 Java에서의 Deque

 

자바에서의 덱은 인터페이스로 구현되었다. 덱 자료구조의 여러 연산들을 정의한 Deque 인터페이스가 있고 이를 구현한 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스가 있다. 

 

Deque 인터페이스의 메소드는 다음과 같다.

 

 addFirst()

덱의 앞쪽에 엘리먼트를 삽입한다. 용량 제한이 있는 덱의 경우, 용량을 초과하면 예외(Exception)가 발생한다

 offerFirst()

덱의 앞쪽에 엘리먼트를 삽입한다. 정상적으로 엘리먼트가 삽입된 경우 true가 리턴되며, 용량 제한에 걸리는 경우 false를 리턴한다. 

 addLast()

덱의 마지막 쪽에 엘리먼트를 삽입한다. 용량 제한이 있는 덱의 경우, 용량 초과시 예외가 발생한다

 add()

addLast()와 동일

 offerLast()

덱의 마지막 쪽에 엘리먼트를 삽입한다. 정상적으로 엘리먼트가 삽입된 경우 true가 리턴되며, 용량 제한에 걸리는 경우 false를 리턴한다. 

 

 removeFirst()

덱의 앞쪽에서 엘리먼트 하나를 뽑아서 제거한 다음 해당 엘리먼트를 리턴한다. 덱이 비어있으면 예외가 발생한다. 

 pollFirst()

덱의 앞쪽에서 엘리먼트 하나를 뽑아서 제거한 다음 해당 엘리먼트를 리턴한다. 덱이 비어있으면 null 이 리턴된다. 

 removeLast()

덱의 마지막 쪽에서 엘리먼트 하나를 뽑아서 제거한 다음 해당 엘리먼트를 리턴한다. 덱이 비어있으면 예외가 발생한다. 

 pollLast()

덱의 마지막 쪽에서 엘리먼트 하나를 뽑아서 제거한 다음 해당 엘리먼트를 리턴한다. 덱이 비어있으면 null 이 리턴된다. 

 remove()

removeFirst()와 동일

 poll()

pollFirst()와 동일

 

 

 getFirst()

덱의 앞쪽 엘리먼트 하나를 제거하지 않은채 리턴한다. 덱이 비어있으면 예외가 발생한다

 peekFirst()

덱의 앞쪽 엘리먼트 하나를 제거하지 않은채 리턴한다. 덱이 비어있으면 null이 리턴된다. 

 getLast()

덱의 마지막쪽 엘리먼트 하나를 제거하지 않은채 리턴한다. 덱이 비어있으면 예외가 발생한다. 

 peekLast()

덱의 마지막 엘리먼트 하나를 제거하지 않은 채 리턴한다. 덱이 비어있으면 null이 리턴된다. 

 peek()

peekFirst()와 동일

 removeFirstOccurrence(Object o)

덱의 앞쪽에서부터 탐색하여 입력한 Object o와 동일한 첫 엘리먼트를 제거한다. Object o 와 같은 엘리먼트가 없으면 덱에 변경이 발생하지 않는다. 

 removeLastOccurrence(Object o)

덱의 뒤쪽에서부터 탐색하여 입력한 Object o와 동일한 첫 엘리먼트를 제거한다. Object o 와 같은 엘리먼트가 없으면 덱에 변경이 발생하지 않는다. 

 element()

removeFirst()와 동일

 addAll(Collection <? extends E c)

입력 받은 Collection의 모든 데이터를 덱의 뒤쪽에 삽입한다.

 push()

addFirst()와 동일. 덱을 스택으로 사용할 때 쓰임

 pop()

removeFirst()와 동일. 덱을 스택으로 사용할 때 쓰임

 remove(Object o)

removeFirstOccurrence(Object o)와 동일

 contain(Object o)

덱에 Object o와 동일한 엘리먼트가 포함되어 있는지 확인

 size()

덱의 크기 

 iterator()

덱의 앞쪽부터 순차적으로 실행되는 이터레이터(iterator)를 얻어옴

 descendingIterator()

덱의 뒤쪽부터 순차적으로 실행되는 이터레이터(iterator)를 얻어옴

 

 코드 예제

백준의 카드놓기(18115) 문제를 푸는데, 동일한 로직의 코드를 LinkedList로 했을 경우 시간초과가 발생했지만, Deque로 사용한 경우 pass가 되었다.

성능적으로도 Deque가 더 좋은 것 같다.

 LinkedList 활용 코드

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("./input.txt"));

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] ax = new int[N];
        for(int n = 0; n < N; n++) 
            ax[n] = Integer.parseInt(st.nextToken());                  

        LinkedList<Integer> out = new LinkedList<Integer>();
        for(int n = N-1; n >= 0; n--) {
            int cur = N - (n);   // 현재 값 
            if(ax[n] == 1) {
                out.addFirst(cur);
            } else if(ax[n] == 2) {
                if(out.size() < 2) out.add(cur);
                else               out.add(1, cur);
            } else if(ax[n] == 3) {
                out.add(cur);
            }
        }

        for(int n = 0; n < N; n++) {
            bw.write(out.get(n) + " ");
        }

        br.close();
        bw.flush();
        bw.close();
    }   

}

 Deque 활용 코드

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("./input.txt"));

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] ax = new int[N];
        for(int n = 0; n < N; n++) 
            ax[n] = Integer.parseInt(st.nextToken());    

        Deque<Integer> deq = new LinkedList<>();
        for(int n = N-1; n >= 0; n--) {
            if(ax[n] == 1) {
                deq.addFirst(N - (n));
            } else if(ax[n] == 2) {
                Integer first = deq.pollFirst();
                deq.addFirst(N - (n));
                if(first != null) deq.addFirst(first);
            } else if(ax[n] == 3) {
                deq.add(N - (n));                
            }
        }

        for(int n = 0; n < N; n++) {
            bw.write(deq.poll() + " ");
        }

        br.close();
        bw.flush();
        bw.close();
    }   

}