덱(Deque)이란?

Double Ended Queue 의 약자로 이전 단원에서 배운 Queue는 자료의 꼬리에서는 삽입, 머리에서는 삭제만 일어났지만 (FIFO 구조) 덱은 Head와 Tail 모두에서 삽입 삭제가 일어난다.

덱의 성질

큐의 성질과 같다. 단, 원소의 추가와 제거가 Head와 Taid에서 모두 일어난다는 것이 다른 점.

1. 원소의 추가가 O(1)
2. 원소의 제거가 O(1)
3. 제알 앞/뒤 원소의 확인이 O(1)
4. 제일 앞/뒤 가 아닌 원소들의 확인/ 변경이 불가능.

구현

배열을 통한 구현

class ArrDeque {
    private int[] deque;
    private int head;
    private int tail;
    private int capacity;

    public ArrDeque(int capacity) {
        this.capacity = capacity;
        deque = new int[capacity];
        head = capacity / 2;
        tail = capacity / 2;
    }

    public void push_front(int data) {
        if (head == 0) {
            System.out.println("Deque is full at the front");
            return;
        }
        deque[--head] = data;
    }

    public void push_back(int data) {
        if (tail == capacity) {
            System.out.println("Deque is full at the back");
            return;
        }
        deque[tail++] = data;
    }

    public int pop_front() {
        if (isEmpty()) {
            return -1;
        }
        return deque[head++];
    }

    public int pop_back() {
        if (isEmpty()) {
            return -1;
        }
        return deque[--tail];
    }

    public int front() {
        if (isEmpty()) {
            return -1;
        }
        return deque[head];
    }

    public int back() {
        if (isEmpty()) {
            return -1;
        }
        return deque[tail - 1];
    }

    public int size() {
        return tail - head;
    }

    public int empty() {
        return isEmpty() ? 1 : 0;
    }

    private boolean isEmpty() {
        return tail == head;
    }
}

이전에 구현했던 Queue와 구조가 비슷하지만 다른 점이 있다. 바로 Head와 Tail의 초기값이다.

// Queue
class ArrQueue {

  private int[] Queue; // 원소를 담을 배열 1개
  private int head = 0;
  private int tail = 0;

  public ArrQueue(int capacity) {
    Queue = new int[capacity];
  }
  
  ...
  
}

큐에서는 삽입과 삭제가 한곳에서만 일어나므로 Head와 Tail의 index를 0부터 잡고 시작해도 된다.

하지만 덱에서는 여의봉처럼 양쪽으로 확장되어야 하므로 capacity의 중간부터 시작해야한다.

// Deque
public ArrDeque(int capacity) {
        this.capacity = capacity;
        deque = new int[capacity];
        head = capacity / 2;
        tail = capacity / 2;
}