[알고리즘] Leetcode_641_Design_Circular_Deque

Problem

Solve

class MyCircularDeque {
    int[] cirDeque;
    int front, rear, size;
    public MyCircularDeque(int k) {
        cirDeque = new int[k];
        size = k;      
        front = -1;
        rear = -1;  
    }
    //인덱스 이동 후 추가
    public boolean insertFront(int value) {
        if(isFull()) return false;
        if(isEmpty()) {
            front = 0;
            rear = size-1;
        }

        front = (front-1+size)%size;
        cirDeque[front] = value;
        return true;
    }
    
    public boolean insertLast(int value) {
        if(isFull()) return false;

        if(isEmpty()) {
            front = 0;
            rear = size-1;
        }

        rear = (rear+1) % size;
        cirDeque[rear] = value;
        return true;
    }
    
    public boolean deleteFront() {
        if(isEmpty()) return false;
        
        if(front == rear){
            front = -1;
            rear = -1;
        }else{
            front = (front+1+size)%size;
        }
        
        return true;

    }
    
    public boolean deleteLast() {
        if(isEmpty()) return false;

         if(front == rear){
            front = -1;
            rear = -1;
        }else{
            rear = (rear-1+size) % size;
        }
        return true;
    }
    
    public int getFront() {
        
        return isEmpty() ? -1 : cirDeque[front];
    }
    
    public int getRear() {
        return isEmpty() ? -1 : cirDeque[rear];
    }
    
    public boolean isEmpty() {
        return front == -1 && rear == -1;
    }
    
    public boolean isFull() {
        return (front-1+size)%size == rear;
    }
}

덱은 앞으로도 뒤로도 모두 추가하고 삭제할 수 있는 기능이 있다.
그래서 front, rear 인덱스를 지정하고 이동시킨 후에 추가하도록 했다.
초기값은 모두 -1로 두되, 추가를 할 적에 비어있다면 front=0, rear=size-1 로 지정 후에 다시 인덱스를 이동시켜 값을 입력시켜주었다.

원형이라 직선 배열의 그림으로는 이해가 잘 되지 않을 수도 있지만 쉽게 말하자면front는 앞으로 전진하면서 , rear 는 뒤로 후진하는 느낌이다. 여기서, 전진할 경우 -1씩 빼주는데 음수가 나올 경우를 대비하여 size 만큼 다시 더해준다.

삭제할 때도 마찬가지로 왔던 길을 다시 되돌아간다는 느낌으로 해준다.
다만, front==rear 처럼 같은 인덱스를 가리키는 경우가 있는데 이는 삭제할 값이 하나뿐이라는 것이기 때문에 삭제 후에 front와 rear 를 초기값 -1 으로 설정해면 비어있다는 의미가 된다.

원형덱이 다 차있는 경우에는 다음으로 추가시킬 front나 rear의 인덱스가 rear나 front 일 경우이다. 쉽게 말하자면 앞뒤로 front, rear 인덱스가 있는 경우다.

항상 말로도 쉽지 않은 풀이를 코드로 설명하기에도 벅차서 힘들다.
더구나 덱도 큐에서 변형되어 생각하기에 조금 어려운데 원형덱이라니 ...
곧 멋지게 Node 를 이용해서 해보고 싶다... 곧...