Circular_Queue(환형 큐) 개념 및 구현

Circular Queue를 알기 위해 Queue부터 먼저 짚고 가자. Queue는 자료구조의 일종으로 어떠한 데이터 집합의 원소들을 Linearly 차례대로 배치한다고 가정했을 때, 선입 선출 방식을 따르는 자료 구조를 의미한다. 이때 Queue는 크기가 정해져있지 않으나,(원소가 큐에 들어가거나 빠질 때마다, Queue의 사이즈가 변하므로..) Circular Queue 개념을 도입하면, Queue의 성질인 선입선출 Rule도 지키면서 Queue의 크기를 고정시킬 수 있다. 아래 그림과 같이, 둥근 환형으로 Queue를 만들고, Queue의 원리대로 원소를 넣고 뺄 수 있는 것이다. 여기서 원소가 들어가는 지점(index)을 Rear, 원소가 빠지는 지점을 Front라고 한다. 

Circular Queue를 올바르게 사용하기 위해선 아래와 같은 추가 규칙이 필요하다.

1. 정해진 Circular Queue 의 크기를 초과하며 원소를 넣을 수 없다.

2. Circular Queue의 마지막 idx를 초과해서 다음으로 넘어가면, 다시 0 번 째 idx 로 Cyclic하게 순환한다.  

이러한 규칙을 숙지하고, Circular Queue를 python의 빌트인 list로 구현하면 아래와 같다. 

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 isFull():
        	raise IndexError("idx error")
        self.rear = (self.rear+1) % self.maxCount
        self.data[self.rear] = x
        self.count += 1
    
    def dequeue(self):
    	if self.count == 0:
        	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")
        return self.data[(self.front+1)%self.maxCount]