덱

이윤설·2024년 4월 1일

Deque

Deque는 Queue를 상속하는 인터페이스이다.
Deque의 구현체 클래스는 두 개가 있으며, 아래와 같이 구현할 수 있다.

Deque<> deque = new LinkedList<>();
Deque<> deque = new ArrayDeque<>();

어떤 것으로 구현하면 좋을지를 정리하자면,
Deque의 중간 삽입,삭제가 빈번한 경우 -> LinkedList
양 끝 삽입/삭제 및 요소를 접근하는 경우가 빈번한 경우 -> ArrayDeque

개인적인 생각으로, 코딩테스트에서 값을 중간에 삽입,삭제를 자주 하는 경우는 잘 못봤기 때문에 보통 ArrayDeque를 사용하는 것 같다.

어떤 한 유저가 ArrayDeque와 LinkedList로 구현한 Queue(Deque 아니긴 하지만 같은 맥락에서 보면)에 데이터를 삽입 및 삭제 시 걸리는 시간을 측정 및 비교하였다.

테스트 결과, 데이터의 크기가 커질수록 LinkedList로 구현한 Queue의 실행시간이 더 커졌다.
이유는 위 표에서도 알 수 있듯이, 캐시 효율성과 메모리 사용량이 비교적 높기 때문이다. 따라서 모바일 애플리케이션처럼 메모리 제한이 엄격한 환경에서는 ArrayDeque를 사용하는 것이 좋다고 한다!

출처) https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist

아무튼 다시 Deque로 돌아와서 Deque는 Stack과 Queue를 합친 것이라고 보면 된다.
즉, LIFO와 FIFO를 둘 다 허용하는 자료구조이다.

Deque의 장단점은 위와 같다.

Deque 시간 복잡도

양 끝 요소

중간 요소

ArrayDeque는 인덱스를 기반으로 중간 요소에 조회하기 때문에 O(1)이다.
시간복잡도는 거의 동일하지만, 위에서도 얘기했듯이 실제 실행시간 자체는
일반적인 경우 ArrayDeque가 빠른 편이다.

제출코드


public class 덱 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int repetition = Integer.parseInt(br.readLine());

        Deque<Integer> deque = new ArrayDeque();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < repetition; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String input = st.nextToken();

            switch (input) {
                case "push_front":
                    pushFront(deque, Integer.parseInt(st.nextToken()));
                    break;

                case "push_back":
                    pushBack(deque, Integer.parseInt(st.nextToken()));
                    break;

                case "pop_front":
                    int num1 = popFront(deque);
                    sb.append(num1).append('\n');
                    break;

                case "pop_back":
                    int num2 = popBack(deque);
                    sb.append(num2).append('\n');
                    break;

                case "size":
                    int num3 = size(deque);
                    sb.append(num3).append('\n');
                    break;

                case "empty":
                    int num4 = empty(deque);
                    sb.append(num4).append('\n');
                    break;

                case "front":
                    int num5 = front(deque);
                    sb.append(num5).append('\n');
                    break;

                case "back":
                    int num6 = back(deque);
                    sb.append(num6).append('\n');
                    break;
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }

    static void pushFront(Deque<Integer> deque, int input) {
        deque.offerFirst(input);
    }

    static void pushBack(Deque<Integer> deque, int input) {
        deque.offerLast(input);
    }

    static int popFront(Deque<Integer> deque) {
        Integer frontNum = deque.pollFirst();
        if (frontNum == null) {
            return -1;
        }
        return frontNum;
    }

    static int popBack(Deque<Integer> deque) {
        Integer lastNum = deque.pollLast();
        if (lastNum == null) {
            return -1;
        }
        return lastNum;
    }


    static int size(Deque<Integer> deque) {
        int size = deque.size();
        return size;
    }

    static int empty(Deque<Integer> deque) {
        if (deque.isEmpty()) {
            return 1;
        } else {
            return 0;
        }
    }

    static int front(Deque<Integer> deque) {
        if (deque.isEmpty()) {
            return -1;
        } else {
            return deque.peekFirst();
        }
    }

    static int back(Deque<Integer> deque) {
        if (deque.isEmpty()) {
            return -1;
        } else {
            return deque.peekLast();
        }
    }
}

배운점

switch case가 if-else보다 빠르다.
삼항 연산자와 if-else 간 속도 차이는 없다.
메소드를 생성하는 것과 그냥 실행하고자 하는 코드를 작성하는 것의 실행 속도 차이는 없다고 봐도 된다.
현대의 컴파일러와 최적화 기술은 메소드 호출의 오버헤드를 상당히 줄여주며,
최적화를 통해 메소드 호출을 전혀 하지 않는 것처럼 도와준다.
switch{case("문자열")} 의 경우 equals()와 같은 개념이다. 즉 문자열이 완전히 동일해야 실행된다.
ex) switch case("hello") -> 사용자 입력값이 "hello!" 이면 조건문 실행조건 충족 X
Token을 사용하지 않는다면 아래 코드를 startsWith()로 대체할 수 있다.

// StringTokenizer
switch (input) {
    case "push_front":
    pushFront(deque, Integer.parseInt(st.nextToken()));
    break;

// String 
String input = br.readLine();
if (input.startsWith("push_front")) {
   int num = Integer.parseInt(input.substring(11)); 
   // "push_front " 이후의 문자열을 숫자로 변환
   // 만약 switch case처럼 똑같은 문자열을 매칭해야 한다면 equals()를 사용하면 됨
   deque.addFirst(num);