[자료구조] 원형 큐, 환형 큐 (Circular Queue)

1. 큐 (Queue)

큐는 이렇게 선입선출(FIFO) 구조이다.

연산 과정에는

- enqueue : 큐에 데이터를 넣는 작업
- dequeue : 큐에서 데이터를 꺼내는 작업
- front : 데이터를 꺼내는 부분에 데이터를 반환
- rear : 데이터를 넣는 부분에 데이터를 반환

이런 개념들이 등장 한다. 

1. 쉽게 이해를 위해 예제를 살펴 보겠다.

우리가 줄 서있는 대기열을 생각하면 쉽다.

티켓 매표소에 이렇게 줄을 서 있다고 가정해보자.

줄을 제일 먼저 선 A가 먼저 표를 사고, 제일 나중에 선 E까지 모두 순서대로 표를 살 수 있을 것이다.

이렇게 

근데 여기서 F가 등장해서 줄을 선다.

그럼 이때 rear는 새로 추가된 맨 뒤의 F로 된다.

이 F를 추가하는 작업을 enqueue 라고 하고, F 추가할 위치를 나타내는 포인터가 rear가 되는 것이다.

이제 A가 매표가 끝나서 줄을 벗어났다.

그럼 front는 그 다음 순서였던 B가 되는 거고, 이렇게 삭제하는 작업을dequeue라고 한다 이때 dequeue의 결과값은 A이다.

front는 꺼낼 위치를 나타내는 포인터가 되는 것이다.

 

2. 큐의 한계점

큐를 이렇게 추가를 다 했다고 치자.

이때는 front가 고정된 상태에서 계속 rear만 바뀌었다.

그럼 이제 삭제를 어떻게 할 것인가!

1. front 고정 방법

보면 앞에서 부터 꺼내고 쭉쭉쭉 앞으로 가는데 이때, 계속 정렬이 이뤄지는 것이다.

 

2. Rear고정 방법

Front의 포인터 값이 증가하며 정렬 필요 없이 삭제를 착착 해나갔다.

그러나 문제의 상황은 Rear가 배열의 끝에 있을때 -> 이때는 배열이 꽉 차있는 상태로 인식하게 된다. 

실상은 앞에 다 비어있는데..

이를 해결 하기 위해 원형 큐가 사용된다.

 

2. 원형 큐, 환형 큐 (Circular Queue)

위의 문제에서 이제 front와 rear의 max 인덱스를 배열의 크기로 지정하고, 그 사이에서 계속 순회하게 만든 것이다.

그러니깐 Rear가 6 크기의 배열에서 사용된다면 rear가 인덱스 5(0,1,2,3,4,5)에서 이동해야할 때에

인덱스 0 으로 변경되는 것이다. 

front도 같은 메커니즘이다.

원형 큐의 상태이다 

초기 이후의 세팅은 buffer를 하나 두고 포화상태를 유지하는 것이 좋다고 한다.

 

3. python 코드로 구현

class CircularQueue:

    def __init__(self, n):
        self.maxCount = n
        self.data = [None] * n
        self.count = 0
        self.front = -1
        self.rear = -1


    def size(self):
        return self.count

    def isEmpty(self):
        return self.count == 0

    def isFull(self):
        return self.count == self.maxCount

    def enqueue(self, x):
        if self.isFull():
            raise IndexError('Queue full')
        self.rear = (self.rear+1)%self.maxCount // 배열 길이 만큼 순회
        self.data[self.rear] = x
        self.count += 1

    def dequeue(self):
        if self.isEmpty():
            raise IndexError('Queue empty')
        self.front = (self.front+1)%self.maxCount // 배열 길이 만큼 순회
        x = self.data[self.front]
        self.count -= 1
        return x

    def peek(self):
        if self.isEmpty():
            raise IndexError('Queue empty')
        // front 변수의 값을 변경하지 않고 출력하기 위해 dequeue()를 불러오지 않고 이렇게 직접조회
        return self.data[(self.front+1) % self.maxCount] 

def solution(x):
    return 0