덱(Deque)

덱(Deque)

Deque이란?

Deque(Double Ended Queue) 라는뜻으로 양쪽끝에서 삽입과 삭제가 전부 가능하다.

Deque의 성질

• 원소의 추가가 O(1)
• 원소의 제거가 O(1)
• 제일 앞/뒤의 원소 확인이 O(1)
• 제일 앞/뒤가 아닌 나머지 원소들의 확인/ 변경이 원칙적으로 불가능

Deque 구현하기

array로 구현한 Queue
head와 tail의 시작점을 중간으로 설정한다.

class Deque {
    private final int MAX = 1000005;
    private final int[] data = new int[2 * MAX + 1];
    private int head = MAX;
    private int tail = MAX;

    boolean offerFirst(int e) {
        data[--head] = e;
        return true;
    }

    boolean offerLast(int e) {
        data[tail++] = e;
        return true;
    }

    int pollFirst() {
        return data[head++];
    }

    int pollLast() {
        return data[--tail];
    }

    int peekFirst() {
        return data[head];
    }

    int peekLast() {
        return data[tail - 1];
    }

    int size() {
        return tail - head;
    }

    boolean isEmpty() {
        return size() == 0;
    }
}

LinkedList로 구현한 Deque

class Deque<E> {
    private Node<E> head;
    private Node<E> tail;
    private int size = 0;

    private static class Node<E> {
        E data;
        Node<E> previous;
        Node<E> next;

        Node(E data) {
            this.data = data;
        }
    }

    boolean offerFirst(E e) {
        Node<E> newNode = new Node<>(e);
        newNode.next = head;
        if (tail == null) {
            tail = newNode;
        } else {
            head.previous = newNode;
        }
        head = newNode;
        size++;
        return true;
    }

    boolean offerLast(E e) {
        Node<E> newNode = new Node<>(e);
        newNode.previous = tail;
        if (head == null) {
            head = newNode;
        } else {
            tail.next = newNode;
        }
        tail = newNode;
        size++;
        return true;
    }

    E pollFirst() {
        E e = head.data;

        Node<E> nextNode = head.next;

        head.data = null;
        head.next = null;


        head = nextNode;
        size--;

        if (size == 0) {
            tail = null;
            head = null;
        }
        return e;
    }

    E pollLast() {
        E e = tail.data;

        Node<E> previousNode = tail.previous;

        tail.data = null;
        tail.previous = null;

        tail = previousNode;
        size--;

        if (size == 0) {
            tail = null;
            head = null;
        }
        return e;
    }

    E peekFirst() {
        Node<E> n = head;
        return n == null ? null : n.data;
    }

    E peekLast() {
        Node<E> n = tail;
        return n == null ? null : n.data;
    }

    int size() {
        return size;
    }

    boolean isEmpty() {
        return size <= 0;
    }
}

java의 Queue에는 offerFirst, offerLast, pollFirst, pollLast, peekFirst, peekLast 외에도
addFirst, addLast, remove, removeLast, getFirst, getLast 등의 메소드가 존재한다.
java의 deque interface의 메소드를 비교하면 아래와 같다.

offer, poll, peek 계열은 예외를 던지지않고
add, remove, get, element 계열은 예외가 발생한다.