[자바 알고리즘 인터뷰] 10장 데크, 우선순위 큐 (1) 원형 데크 디자인

데크

- Double-Ended-Queue의 줄임말로, 글자 그대로 양쪽 끝을 모두 추출할 수 있는, 큐를 일반화한 형태의 추상 자료형(ADT)이다. 

- 양쪽에서 삽입과 삭제를 모두 처리할 수 있으며, 스택과 큐의 특징을 모두 갖고 있다. 

- 이중 연결 리스트(Doubly Linked List)로 구현 

 

출처: 자바 알고리즘 인터뷰 with 코틀린 저자: 박상길 <책만>

 

- 양쪽으로 head와 tail이라는 이름의 두 포인터를 갖고 있다가 새로운 아이템이 추가될 때마다 앞쪽 또는 뒤쪽으로 연결해주기만 하면 된다. 

 

- 자바에서 데크를 구현하는 Deque 자료형은 Queue와 마찬가지로 인터페이스이며, Queue를 확장해 정의되어 있다 ,

- 실제 구현은 LinkedList 또는 ArrayDeque로 할 수 있다. 

 

//데크 선언
Deque<Integer> deque = new LinkedList<>();

 

 

https://leetcode.com/problems/design-circular-deque/description/

 

- 다음 연산을 제공하는 원형 데크를 디자인 하라 

 

MyCircularDeque(k) : 데크 크기를 k로 지정하는 생성자 

insertFront() : 데크 처음에 아이템을 추가하고 성공할 경우 true를 리턴

insertLast() : 데크 마지막에 아이템을 추가하고 성공할 경우 true를 리턴

deleteFront() : 데크 처음에 아이템을 삭제하고 성공할 경우 true를 리턴

deleteLast() : 데크 마지막에 아이템을 삭제하고 성공할 경우 true를 리턴

getFront() : 데크의 첫 번째 아이템을 가져온다. 데크가 비어 있다면 -1을 리턴

getRear() : 데크의 마지막 아이템을 가져온다. 데크가 비어 있다면 -1을 리턴

isEmpty() : 데크가 비어 있는지 여부를 판별

isFull() : 데크가 가득 차 있는지 여부를 판별 

 

 

풀이 1) 이중 연결 리스트를 이용한 데크 구현 

 

 

1) 이중 연결 리스트를 사용할 클래스 정의 

 

- 문제 풀이 클래스의 중첩 클래스(Nested Class)로 선언과 초기화 

- 전체 큐의 크기를 k로 바독, 현재 큐의 크기는 len으로 정해서 매번 계산한다. 

- 2개의 연결 리스트를 미리 선언하고 서로 연결한 상태에서 시작 

 

    //이중 연결 리스트로 사용할 클래스 선언
    static class DoublyLinkedList {
        //왼쪽으로 연결할 이중 연결 리스트
        DoublyLinkedList left;
        //오른쪽으로 연결할 이중 연결 리스트 
        DoublyLinkedList right;
        int val;

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

    int len; //현재 큐의 크기
    int k; //전체 큐의 크기
    DoublyLinkedList head; //이중 연결 리스트 head 노드
    DoublyLinkedList tail; //이중 연결 리스트 tail 노드

 

 

2) insertFront

 

- 만약 큐가 꽉 차 있다면 false를 리턴하고 종료 

- head의 바로 오른쪽에 노드를 삽입하고 이중으로 연결한다. 

- 그렇게 해서 head는 맨 앞을, tail은 맨 뒤를 유지하며 중간에 노드가 삽입되고 삭제되는 구조를 띤다. 

 

public boolean insertFront(int value) {
    //꽉 차 있으면 진행하지 않음
    if(isFull())
        return false;
    DoublyLinkedList node = new DoublyLinkedList(value);

    //신규 노드는 head 바로 오른쪽에 삽입
    node.right = head.right;
    node.left = head;
    head.right.left = node;
    head.right = node;
    len++;
    return true;
}

 

 

 

3) insertLast

 

- 맨 뒤에 노드를 추가할 때는 tail의 바로 왼쪽에 노드를 삽입하고 마찬가지로 이중으로 연결한다, 

- 그러면서 tail은 다시 맨 뒤로 간다. 

 

public boolean insertLast(int value) {
     //꽉 차 있으면 진행하지 않음
     if(isFull())
         return false;
     DoublyLinkedList node = new DoublyLinkedList(value);

     //신규 노드는 tail 바로 왼쪽에 삽입
     node.left = tail.left;
     node.right = tail;
     tail.left.right = node;
     tail.left = node;
     len++;
     return true;
 }

 

 

 

class MyCircularDeque {
    //이중 연결 리스트로 사용할 클래스 선언
    static class DoublyLinkedList {
        //왼쪽으로 연결할 이중 연결 리스트
        DoublyLinkedList left;
        //오른쪽으로 연결할 이중 연결 리스트 
        DoublyLinkedList right;
        int val;

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

    int len; //현재 큐의 크기
    int k; //전체 큐의 크기
    DoublyLinkedList head; //이중 연결 리스트 head 노드
    DoublyLinkedList tail; //이중 연결 리스트 tail 노드 

    public MyCircularDeque(int k) {
        //이중 연결 리스트 2개 생성 
        head = new DoublyLinkedList(0);
        tail = new DoublyLinkedList(0);

        //서로 연결
        head.right = tail;
        tail.left = head;

        //전체 큐의 크기 지정
        this.k = k;

        //현재 큐의 크기 지정
        this.len = 0;
    }
    
    public boolean insertFront(int value) {
        //꽉 차 있으면 진행하지 않음
        if(isFull())
            return false;
        DoublyLinkedList node = new DoublyLinkedList(value);

        //신규 노드는 head 바로 오른쪽에 삽입
        node.right = head.right;
        node.left = head;
        head.right.left = node;
        head.right = node;
        len++;
        return true;
    }
    
    public boolean insertLast(int value) {
        //꽉 차 있으면 진행하지 않음
        if(isFull())
            return false;
        DoublyLinkedList node = new DoublyLinkedList(value);

        //신규 노드는 tail 바로 왼쪽에 삽입
        node.left = tail.left;
        node.right = tail;
        tail.left.right = node;
        tail.left = node;
        len++;
        return true;
    }
    
    public boolean deleteFront() {
        //텅 비어 있다면 진행하지 않음
        if(isEmpty())
            return false;
        //head 바로 오른쪽 노드를 연결에서 끊음
        head.right.right.left = head;
        head.right = head.right.right;
        len--;
        return true;
    }
    
    public boolean deleteLast() {
        //텅 비어 있다면 진행하지 않음
        if(isEmpty())
            return false;
        //tail 바로 왼쪽 노드를 연결에서 끊음
        tail.left.left.right = tail;
        tail.left = tail.left.left;
        len--;
        return true;
    }
    
    public int getFront() {
        //맨 앞(head 오른쪽)의 값을 가져온다.
        return (isEmpty())?-1:head.right.val;
    }
    
    public int getRear() {
        //맨 뒤(tail 왼쪽)의 값을 가져온다.
        return (isEmpty())?-1:tail.left.val;
    }
    
    public boolean isEmpty() {
        //현재 큐의 크기가 0이면 비어 있음
        return len == 0;
    }
    
    public boolean isFull() {
        //현재 큐의 크기가 처음 선언한 큐의 크기와 일치하면 꽉 차 있음
        return len == k;
    }
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 */

5밀리초