덱

덱

• 양쪽에서 삽입과 삭제가 가능한 자료구조
  • Deque: Doubly-ended Queue
  • Stack과 Queue를 합친 상태

배열을 이용한 덱

class Deque {
    int[] arr;
    int front = 0;
    int rear = 0;

    Deque(int size) {
        arr = new int[size+1];
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        return (this.rear + 1) % arr.length == front;
    }

    public void addFirst(int data) {
        if (isFull()) {
            System.out.println("Deque is Full!");
            return;
        }

        arr[front] = data;
        front = (front - 1 + arr.length) % arr.length;
    }

    public void addLast(int data) {
        if (isFull()) {
            System.out.println("Deque is Full!");
            return;
        }

        rear = (rear + 1) % arr.length;
        arr[rear] = data;
    }

    public Integer removeFirst() {
        if (isEmpty()) {
            System.out.println("Deque is Empty!");
            return null;
        }

        front = (front + 1) % arr.length;
        return arr[front];
    }

    public Integer removeLast() {
        if (isEmpty()) {
            System.out.println("Deque is Empty!");
            return null;
        }

        int data = arr[rear];
        rear = (rear - 1 + arr.length) % arr.length;
    }

    public void printDeque() {
        int start = (front + 1) % arr.length;
        int end = (rear + 1) % arr.length;

        for (int i = start; i != end; i = (i + 1) % arr.length) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

리스트를 이용한 덱

class Deque {
    ArrayList list;

    Deque() {
        this.list = new ArrayList();
    }

    public boolean isEmpty() {
        if (list.size() == 0) {
            return true;
        }

        return false;
    }

    public void addFirst(int data) {
        list.add(0, data);
    }

    public void addLast(int data) {
        list.add(data);
    }

    public Integer removeFirst() {
        if (isEmpty()) {
            System.out.println("Deque is empty!");
            return null;
        }

        int data = (int) list.get(0);
        list.remove(0);
        return data;
    }

    public Integer removeLast() {
        if (isEmpty()) {
            System.out.println("Deque is empty!");
            return null;
        }

        int data = (int) list.get(list.size() - 1);
        list.remove(list.size() - 1);
        return data;
    }

    public void printDeque() {
        System.out.println(list);
    }
}