덱(deque)의 정의와 구현

덱(deque)의 정의

• 덱 또는 데큐(deque)는 양 방향에서 모두 데이터의 삽입과 삭제가 일어나는 자료구조이다.
• 양 방향에서 데이터의 삽입 삭제가 발생하기 때문에 데큐는 양방향 연결 리스트로 구현하는 것이 효율이 좋다.

 

 

덱(deque)의 연산과 구현

• 위에도 말했듯 덱은 양방향 연결 리스트로 구현하는 것이 효율적이다. 해당 자료구조는 이미 이전에 큐를 구현하며 같이 구현하였다.
• 큐에서 데이터의 삽입이 tail에서 이루어졌고 삭제가 head에서 이루어졌다. 덱을 구현하기 위해서는 tail에서의 데이터 삭제와 head에서의 데이터 삽입을 추가적으로 구현하기만 하면 된다.

class Node{
    int data;
    Node prev;
    Node next;

    Node(int data){
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

class Deque{
    Node head;
    Node tail;
    int length;

    Deque(){
        head = new Node(-1);
        head.next = null;
        head.prev = null;

        tail = new Node(-1);
        tail.next = null;
        tail.prev = null;

        length = 0;
    }

    public void addFirst(int data){
       
    }

    public void addLast(int data){
        Node newNode = new Node(data);

        if (tail.prev == null){
            head.next = newNode;
            newNode.prev = head;
            newNode.next = tail;
            tail.prev = newNode;
        } else{
            newNode.next = tail;
            newNode.prev = tail.prev;
            tail.prev.next = newNode;
            tail.prev = newNode;
        }

        length++;
    }

    public int removeFirst(){
        int ret = -1;

        if (head.next == null || head.next == tail){
            return -1;
        }

        ret = head.next.data;
        head.next.next.prev = head;
        head.next = head.next.next;

        length--;

        return ret;
    }

    public int removeLast(){
        
    }

    public int peekFirst(){
        return head.next.data;
    }

    public int peekLast(){
        return tail.prev.data;
    }

    public int getLength(){
        return this.length;
    }

    public boolean isEmpty(){
        return this.length == 0;
    }

    public String toString(){
        StringBuilder sb = new StringBuilder();

        Node start = head.next;
        while(start.next != null){
            sb.append(start.data);
            sb.append(" ");
            start = start.next;
        }

        return sb.toString();
    }
}

• 위 코드는 이전에 구현했던 큐에서 몇 가지 연산만 추가한 것이다.

 

 

덱(deque)의 head 삽입 연산

• head에 삽입하는 것은 연결 리스트의 처음에 데이터를 삽입하는것과 동일하다.
• 새로운 노드의 prev를 head로, next를 head.next로 설정하고, head.next의 prev와 head.next를 새로운 노드로 설정하면 끝난다.
• 이전 큐에서  tail에 삽입하는 연산을 생각해 보면 tail이 head로 바뀐것과 그로 인해 prev와 next가 서로 바뀐것이 끝이다.

public void addFirst(int data){
    Node newNode = new Node(data);

    if (head.next == null){
        head.next = newNode;
        newNode.prev = head;
        newNode.next = tail;
        tail.prev = newNode;
    } else{
        newNode.next = head.next;
        head.next.prev = newNode;
        head.next = newNode;
        newNode.prev = head;
    }

    length++;
}

• 덱이 비어있을경우, tail에도 설정하는 것이 필요하므로 그 부분을 따로 if를 통해 처리하였다.

 

 

덱(deque)의 tail 삭제 연산

• tail 삭제 연산은 연결 리스트의 맨 마지막 요소를 삭제하는것과 동치이다.
• 이 경우 tail.prev의 이전 노드 prev의 next를 tail을 가리키도록 하고, tail.prev를 tail.prev.prev로 바꾸어주면 손쉽게 해결된다.
• 물론 덱이 비어있을 경우에 연산이 바로 끝나도록 처리해주어야 한다.

public int removeLast(){
    int ret = -1;

    if (tail.prev == null || tail.prev == head){
        return -1;
    }

    ret = tail.prev.data;
    tail.prev.prev.next = tail;
    tail.prev = tail.prev.prev;

    length--;

    return ret;
}

 

 

 

정리

• 이렇게 연결 리스트의 구현에서부터 시작하여 이를 응용한 자료구조인 스택, 큐, 덱의 구현까지 끝마쳤다.
• 해당 자료구조는 테스트에서 직접적으로 쓰이기보단 알고리즘의 구현에 자주 사용된다. 만약 테스트에 이러한 유형의 문제가 출제된다면 데이터의 삽입 삭제가 어떻게 돌아가는지에 대해 고민해보아야 할 것이다.
• 덱의 전체적인 코드는 다음과 같다.

class Node{
    int data;
    Node prev;
    Node next;

    Node(int data){
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

class DoubleLinkedList{
    Node head;
    Node tail;
    int length;

    DoubleLinkedList(){
        head = new Node(-1);
        head.next = null;
        head.prev = null;

        tail = new Node(-1);
        tail.next = null;
        tail.prev = null;

        length = 0;
    }

    public void addFirst(int data){
        Node newNode = new Node(data);

        if (head.next == null){
            head.next = newNode;
            newNode.prev = head;
            newNode.next = tail;
            tail.prev = newNode;
        } else{
            newNode.next = head.next;
            head.next.prev = newNode;
            head.next = newNode;
            newNode.prev = head;
        }

        length++;
    }

    public void addLast(int data){
        Node newNode = new Node(data);

        if (tail.prev == null){
            head.next = newNode;
            newNode.prev = head;
            newNode.next = tail;
            tail.prev = newNode;
        } else{
            newNode.next = tail;
            newNode.prev = tail.prev;
            tail.prev.next = newNode;
            tail.prev = newNode;
        }

        length++;
    }

    public int removeFirst(){
        int ret = -1;

        if (head.next == null || head.next == tail){
            return -1;
        }

        ret = head.next.data;
        head.next.next.prev = head;
        head.next = head.next.next;

        length--;

        return ret;
    }

    public int removeLast(){
        int ret = -1;

        if (tail.prev == null || tail.prev == head){
            return -1;
        }

        ret = tail.prev.data;
        tail.prev.prev.next = tail;
        tail.prev = tail.prev.prev;

        length--;

        return ret;
    }

    public int peekFirst(){
        return head.next.data;
    }

    public int peekLast(){
        return tail.prev.data;
    }

    public int getLength(){
        return this.length;
    }

    public boolean isEmpty(){
        return this.length == 0;
    }

    public String toString(){
        StringBuilder sb = new StringBuilder();

        Node start = head.next;
        while(start.next != null){
            sb.append(start.data);
            sb.append(" ");
            start = start.next;
        }

        return sb.toString();
    }
}