Java를 이용한 Circular Deque 구현

이번에는 Java를 이용하여 원형 데크를 구현하는 Design Circular Deque 실습이다.

Design Circular Deque - LeetCode

데크(Deque)는 큐(Queue)와 비슷하지만 양쪽 모두(head, tail)에서 삽입, 삭제 연산이 가능한 자료구조다. 즉 끝이 두 개(double-ended)인 큐이기 때문에 deque라고 한다. 그럼 원형 데크는 이전에 구현했던 원형 큐처럼 제한된 크기로 설정된 데크라고 생각하면 될 것이다.

 

문제에서는 양쪽을 Front, Last(또는 Rear)로 구분하고 있으며 각각 삽입(insert), 삭제(delete), 조회(get) 연산과 포화 상태, 공백 상태를 조회하는 메서드를 구현하는 것을 요구하고 있다. 당연하지만 내장 데크 라이브러리를 사용하면 안 되고 이번에도 역시 배열과 인덱스를 이용하여 구현해보기로 했다.

 

이전에도 원형 큐를 구현했던 적이 있기 때문에 관련 경험으로 미루어 볼 때 원형 자료구조 설계 시 중요한 부분은 현재 인덱스에 값을 삽입하고 인덱스를 이동시킬지, 인덱스를 이동시키고 값을 삽입할지 결정하는 것이다. 이에 따라서 포화, 공백 상태를 확인하거나 값을 조회하는 로직이 달라질 수 있기 때문이다.

이번 설계에서는 값을 조회할 때 현재 인덱스가 가리키는 값을 조회할 수 있도록 인덱스를 이동시킨 후 값을 삽입하는 방법을 선택했다. 설계에서는 Front, Last를 Head, Tail로 명명하였다. 사실 Front가 Head든 Tail이든 상관없이 양쪽 방향으로 삽입만 가능하면 되기 때문에 Head를 왼쪽, Tail을 오른쪽 방향으로 가정하고 진행하였다. 그런데 초기 삽입 상태에는 Head가 Tail보다 뒤에 있는데 왜 그럴까? 이는 인덱스를 이동시킨 후 값을 삽입하기 때문이다. 

그런데 이 경우 head에 값을 삽입하면 왼쪽으로 한 칸 이동해서 head와 tail이 모두 같은 값을 가리키게 된다. 얼핏 생각하면 이해가 안 갈 수도 있지만 원형 데크에서는 값이 하나 삽입됐으면 그 값을 head와 tail 양쪽에서 접근할 수 있어야 한다. 이후 새로운 값이 삽입되면 다른 값을 가리키겠지만 하나밖에 없다면 같은 값을 가리키는 게 맞기 때문이다. 그렇기 때문에 공백 상태에서 삽입 연산을 수행할 때 초기값을 위처럼 설정해두고 head나 tail을 옮기는 방식으로 구현하였다.

위의 그림에서 볼 수 있듯이 tail 쪽에 값을 삽입하면 인덱스가 이동한 뒤 값이 삽입되기 때문에 head와 tail이 왼쪽, 오른쪽 방향으로 정상적으로 이동하게 되는 것을 볼 수 있다.

 

물론 실제로 head, tail의 초기값을 0, -1로 두진 않는다. 이는 데크의 포화 상태를 검사할 때 tail이 가리키는 곳 뒤에 head가 있다면 포화 상태인 걸로 파악하기 때문인데 head는 한 칸 앞(왼쪽)으로 가야 하지만 이미 tail이 가리키고 있는 곳에 값이 들어있기 때문에 추가적인 값을 삽입할 수 없고 tail의 입장에서도 마찬가지기 때문이다. 이는 원형 큐에서도 동일하게 겪었던 고민이었고 그래서 이전처럼 둘 다 -1로 초기화해서 데크 바깥에 인덱스를 두고 삽입 연산 시 인덱스를 초기화해주는 방식으로 공백 상태를 구분하였다.

 

또 하나의 중요한 점은 삽입, 삭제 연산 시 두 포인터가 같은 곳을 가리키고 있다면 모든 요소가 삭제됐다고 판단하고 인덱스를 다시 데크 바깥으로 옮기는 로직이다. 왜 이런 게 필요할까? 이는 값을 처음 삽입했을 때, 즉 값이 하나만 남았을 때 head, tail 인덱스가 이 유일한 값을 가리키게 된다는 점을 생각해 보면 된다.

위의 그림에서 볼 수 있듯이 삭제 연산의 대상이 맨 마지막 값까지 왔을 때는 head와 tail 인덱스가 같은 값을 가리키게 된다. 여기서 Head 쪽이든 Tail 쪽이든 값을 삭제하면 모든 값이 삭제된 상태이므로 인덱스를  데크 바깥으로 옮겨서 초기화시켜야 하는 것이다. 

 

이를 기반으로 구현한 데크는 다음과 같다.

class MyCircularDeque {

    private int[] deque;
    private int head = -1;
    private int tail = -1;
    private int size;
    
    /** Initialize your data structure here. Set the size of the deque to be k. */
    public MyCircularDeque(int k) {
        size = k;
        deque = new int[k];
    }
    
    /** Adds an item at the front of Deque. Return true if the operation is successful. */
    public boolean insertFront(int value) {
        if(isFull()){
            return false;
        }
        if(isEmpty()){
            head = 0;
            tail = size-1;
        }
        
        head = (head - 1 + size) % size;
        deque[head] = value;
        return true;
    }
    
    /** Adds an item at the rear of Deque. Return true if the operation is successful. */
    public boolean insertLast(int value) {
        if(isFull()){
            return false;
        }
        if(isEmpty()){
            head = 0;
            tail = size-1;
        }
        
        tail = (tail + 1 + size) % size;
        deque[tail] = value;
        return true;
    }
    
    /** Deletes an item from the front of Deque. Return true if the operation is successful. */
    public boolean deleteFront() {
        if(isEmpty()){
            return false;
        }
        
        if(head == tail){
            head = -1;
            tail = -1;
        } else {
            head = (head + 1 + size) % size;
        }
        return true;
    }
    
    /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
    public boolean deleteLast() {
        if(isEmpty()){
            return false;
        }
        
        if(head == tail){
            head = -1;
            tail = -1;
        } else {
            tail = (tail - 1 + size) % size;
        }
        return true;
    }
    
    /** Get the front item from the deque. */
    public int getFront() {
        if(isEmpty()) return -1;
        return deque[head];
    }
    
    /** Get the last item from the deque. */
    public int getRear() {
        if(isEmpty()) return -1;
        return deque[tail];
    }
    
    /** Checks whether the circular deque is empty or not. */
    public boolean isEmpty() {
        return head == -1 && tail == -1;
    }
    
    /** Checks whether the circular deque is full or not. */
    public boolean isFull() {
        return (tail + 1 + size) % size == head;
    }
}

까다로운 점도 많았지만 어렵지 않게 구현할 수 있었다.