[LeetCode#641] Design Circular Deque

❒ Description

---

제목	Design Circular Deque
링크	https://leetcode.com/problems/design-circular-deque/description/
자료구조	선형 (배열 / 이중 연결 리스트)
시간복잡도	O(1)

이번 문제는 이중 연결 리스트로 Circular-Deque를 구현하는 문제였다.

근데 사실 이중 연결 리스트로  Circular-Deque를 구현하면 원형의 이점을 살릴 수 없다.

실제로 원형의 이점을 살리기 위해선 이 문제를 연결리스트가 아닌 배열로 풀이해야 한다.

따라서 이번 문제는 이중 연결 리스트와 배열 모두 구현 해볼 것이다.

 

 

 

❒ Solution

---

1. 이중 연결 리스트 (Doubly-Linked List)

public class MyCircularDeque {

    public static class ListNode {
        ListNode next;
        ListNode prev;
        int val;

        public ListNode(int val) {
            this.val = val;
        }
    }

    int currentSize;
    int size;
    ListNode head;
    ListNode tail;


    public MyCircularDeque(int k) {
        this.head = null;
        this.tail = null;
        this.currentSize = 0;
        this.size = k;
    }

    public boolean insertFront(int value) {
        if (isFull()) {
            return false;
        }
        ListNode newNode = new ListNode(value);
        currentSize++;
        if(isEmpty()){
            head=tail=newNode;
            return true;
        }
        newNode.next = head;
        head.prev = newNode;
        head = newNode;
        return true;
    }

    public boolean insertLast(int value) {
        if (isFull()) {
            return false;
        }
        ListNode newNode = new ListNode(value);
        currentSize++;
        if (isEmpty()) {
            head=tail=newNode;
            return true;
        }
        newNode.prev = tail;
        tail.next = newNode;
        tail = newNode;
        return true;
    }

    public boolean deleteFront() {
        if(isEmpty()) {
            return false;
        }
        currentSize--;
        if (head == tail) {
            head = tail = null;
            return true;
        }
        head = head.next;
        head.prev = null;
        return true;
    }

    public boolean deleteLast() {
        if (isEmpty()) {
            return false;
        }
        currentSize--;
        if (head == tail) {
            head = tail = null;
            return true;
        }
        tail = tail.prev;
        tail.next = null;
        return true;
    }

    public int getFront() {
        if(isEmpty()) {
            return -1;
        }
        return head.val;
    }

    public int getRear() {
        if(isEmpty()) {
            return -1;
        }
        return tail.val;
    }

    public boolean isEmpty() {
        return head == null || tail == null;
    }

    public boolean isFull() {
        return currentSize == size;
    }
}

 

 

2. 배열 (Array)

public class MyCircularDeque {
    int front = -1;
    int rear = -1;
    int size;
    int[] cq;

    public MyCircularDeque(int k) {
        this.size = k;
        this.cq = new int[k];
    }

    public boolean insertFront(int value) {
        if (isFull()) {
            return false;
        }    
        if (isEmpty()) {
            front = 0;
            rear = 0;
            cq[front] = value;
        } else if (front == 0) {
            front = size - 1;
            cq[front] = value;
        } else {
            front--;
            cq[front] = value;
        }
        return true;
    }

    public boolean insertLast(int value) {
        if (isFull()) {
            return false;
        }
        if (isEmpty()) {
            front = 0;
            rear = 0;
            cq[rear] = value;
        } else if (rear == size - 1) {
            rear = 0;
            cq[rear] = value;
        } else {
            rear++;
            cq[rear] = value;
        }
        return true;
    }

    public boolean deleteFront() {
        if (isEmpty()) {
            return false;
        }
        if (rear == front) {
            front = -1;
            rear = -1;
        } else if (front == size - 1) {
            front = 0;
        } else {
            front ++;
        }
        return true;
    }

    public boolean deleteLast() {
        if (isEmpty()) {
            return false;
        }
        if (front == rear) {
            front = -1;
            rear = -1;
        } else if (rear == 0) {
            rear = size - 1;
        } else {
            rear--;
        }
        return true;
    }

    public int getFront() {
        if (isEmpty())
            return -1;
        return cq[front];
    }

    public int getRear() {
        if (isEmpty())
            return -1;
        return cq[rear];
    }

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

    public boolean isFull() {
        return front == (rear + 1) % size;
    }
}

배열을 통한 Circular-DQ는 inner static 클래스도 필요 없었고, 훨씬 simple 한 느낌이였다.

메소드 별로 코드 분석을 해보자.

 

1. insertFront(value) 

public boolean insertFront(int value) {
    if (isEmpty()) {
    	front = 0;
        rear = 0;
        cq[front] = value;
    } else if (front == 0) {
    	front = size - 1;
        cq[front] = value;
    } else {
    	front--;
        cq[front] = value;
    }
    return true;
}

 

Q가 비어있는 경우 front와 rear를 각각 +1 해준다. 이 경우 front와 bear는 같은 인덱스를 바라 본다.

Q[0]이 이미 front 인 경우에는 front를 마지막 index로 옮겨 줘야한다. 따라서 front에 `size - 1`을 할당한다.

그 외의 경우 front에서 -1을 해준단.

 

2. insertFront(value) 

public boolean insertLast(int value) {
    if (isEmpty()) {
    	front = 0;
      	rear = 0;
        cq[rear] = value;
    } else if (rear == size - 1) {
   		rear = 0;
        cq[rear] = value;
    } else {
    	rear++;
        cq[rear] = value;
    }
}

 

`rear == size - 1` 즉, rear가 마지막 인덱스를 가리키고 있을 땐 index 0으로 변경해줘야 한다.

 

3. isFull()

public boolena isFull() {
    return front == (rear + 1) % size;
}

rear가 갈 수 있는 다음 위치가 front와 동일하다면 Q가 가득찼다고 간주한다.