[자바 알고리즘 인터뷰] 9장 스택,큐 (6) 원형 큐 디자인

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

 

 

 

 

- 원형 큐를 디자인하라, 큐가 비어 있다면 -1을 리턴하며, 해당 원형 큐의 사용 예는 다음과 같다. 

 

 

풀이 1) 배열을 이용한 풀이

 

 

- 원형큐(Circular Queue)는 FIFO 구조를 지닌다는 점에서 기존 큐와 동일하다. 

- 그러나 마지막 위치가 시작 위치와 연결되는 원형 구조를 띠기 때문에, 링 버퍼(Ring Buffer)라고 부른다. 

 

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

 

- 기존의 큐는 공간이 꽉 차면 더 이상 엘리먼트를 추가할 수 없다. 

- 심지어 앞쪽에 엘리먼트들이 deQueue()로 모두 빠져서 충분한 공간이 남게 돼도 그 쪽으로는 추가할 수 있는 방법이 없다. 

 

- 그러나 원형 큐는 앞쪽에 공간이 남아 있다면 동그랗게 연결해 앞쪽으로 추가할 수 있도록 재활용이 가능하다. 

 

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

 

- 동작원리는 투 포인터와도 비슷하다.

- 마지막 위치와 시작 위치를 연결하는 원형 구조를 만들고, 엘리먼트의 시작점과 끝점을 따라 투 포인터가 움직인다. 

 

- enQueue()를 하게 되면 rear 포인터가 앞으로 이동하고, deQueue()를 하게 되면 front 포인터가 앞으로 이동한다. 

 

- 이렇게 enQueue()와 deQueue()를 반복하게 되면 서로 동그랗게 연결되어 있기 때문에 투 포인터가 빙글빙글 돌면서 이동하는 구조가 된다. 

 

- 만약 front 포인터와 rear 포인터가 같은 위치에서 서로 만나게 되면 그때는 여유 공간이 하나도 없다는 뜻이므로 공간 부족 에러를 발생시킨다. 

 

- 배열로 원형 큐 구현 

 

 

1) 초기화 

 

int q[];
int front =0, rear = -1, len = 0;

public MyCircularQueue(int k) {
    //k 크기의 원형 큐로 사용할 배열 선언
    this.q = new int[k];
}

 

- 큐의 크기 k를 입력값으로 받아 front 포인터는 0, rear 포인터는 한 칸 더 뒤인 -1에서 시작한다. 

 

2) enQueue

 

public boolean enQueue(int value) {
 //꽉 차 있지 않다면 삽입 진행
 if(!this.isFull())
 {
     //rear 포인터 한 칸 앞으로 이동, 최대 크기를 초과하면 나머지 위치로 이동
     this.rear = (this.rear+1)%this.q.length;
     //rear 위치에 값 삽입
     this.q[rear] = value;
     //현재 큐의 크기 계산
     this.len++;
     return true;
 }
 else
 {
     return false;
 }

 

- rear 포인터를 한 칸 앞으로 이동하고 해당 위치에 값을 넣는다. 

- 초깃값을 -1로 지정했기 때문에 맨 처음에는 인덱스 0에 현재 값을 넣게 된다. 

- 전체 길이만큼 모듈로 연산을 하여 포인터의 위치가 전체 길이를 벗어나지 않게 한다. 

 

 

3) deQueue

public boolean deQueue() {
 //텅 비어 있지 않다면 삭제 진행 
 if(!this.isEmpty())
 {
     //front 포인터 한 칸 앞으로 이동, 최대 크기를 초과하면 나머지 위치로 이동
     this.front = (this.front+1)%this.q.length;
     //현재 큐의 크기 계산
     this.len--;
     return true;
 }
 else
 {
     return false;
 }
}

 

- 먼저 !this.isEmpty()로 비어 있지 않은지 학인하고 front 포인터를 한 칸 앞으로 이동한다.

- 마찬가지로 모듈로 연산으로 최대 길이를 넘지 않도록 한다. 

- 현재 큐의 크기를 하나 줄인다. 

- 이렇게 하면 기존의 값은 남아 있으나 이미 포인터는 한 칸 앞으로 이동한 상태이기 때문에 그 값은 더 이상 쓰이지 않는다. 

- 나중에 rear 포인터가 한 바퀴 돌아서 그 위치를 가리키고, 새로운 값이 들어오면 자연스럽게 업데이트 될 것이다. 

 

 

class MyCircularQueue {
    int q[];
    int front =0, rear = -1, len = 0;

    public MyCircularQueue(int k) {
        //k 크기의 원형 큐로 사용할 배열 선언
        this.q = new int[k];
    }
    
    public boolean enQueue(int value) {
        //꽉 차 있지 않다면 삽입 진행
        if(!this.isFull())
        {
            //rear 포인터 한 칸 앞으로 이동, 최대 크기를 초과하면 나머지 위치로 이동
            this.rear = (this.rear+1)%this.q.length;
            //rear 위치에 값 삽입
            this.q[rear] = value;
            //현재 큐의 크기 계산
            this.len++;
            return true;
        }
        else
        {
            return false;
        }
    }
    
    public boolean deQueue() {
        //텅 비어 있지 않다면 삭제 진행 
        if(!this.isEmpty())
        {
            //front 포인터 한 칸 앞으로 이동, 최대 크기를 초과하면 나머지 위치로 이동
            this.front = (this.front+1)%this.q.length;
            //현재 큐의 크기 계산
            this.len--;
            return true;
        }
        else
        {
            return false;
        }
    }
    
    public int Front() {
        //맨 앞의 값을 가져온다. 
        return (this.isEmpty())?-1 : this.q[this.front];
    }
    
    public int Rear() {
        //맨 뒤의 값을 가져온다. 
        return (this.isEmpty())?-1:this.q[this.rear];
    }
    
    public boolean isEmpty() {
        //현재 큐의 크기가 0이면 비어 있음
        return this.len == 0;
    }
    
    public boolean isFull() {
        //현재 큐의 크기가 전체 큐의 크기와 일치하면 꽉 차 있음
        return this.len == this.q.length;
    }
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue obj = new MyCircularQueue(k);
 * boolean param_1 = obj.enQueue(value);
 * boolean param_2 = obj.deQueue();
 * int param_3 = obj.Front();
 * int param_4 = obj.Rear();
 * boolean param_5 = obj.isEmpty();
 * boolean param_6 = obj.isFull();
 */

4 밀리초