환형 큐(Circular Queues)

환형 큐란?

정해진 개수의 저장 공간을 빙 돌려가며 이용하는 큐이다.

환형 큐에선 front로 데이터를 빼고, rear로 데이터를 입력하는 위치를 가진다.

입력과 출력을 따로 관리함으로써 항상 정렬을 하지 않아도 된다.

밑의 예시에서는 Head가 front, Tail이 rear이다.

 

출처 : https://intrepidgeeks.com/tutorial/circular-queue-or-ring-buffer

 

환형 큐가 지원하는 연산 목록

• size() - 현재 큐에 들어 있는 데이터 원소의 수를 구한다.
• isEmpty() - 현재 큐가 비어 있는지를 판단한다.
• isFull() - 큐에 데이터 원소가 꽉 차 있는지 판단한다.
• enqueue(x) - 데이터 원소 x를 큐에 추가한다.
• dequeue() - 큐의 맨 앞에 저장된 데이터 원소를 제거하면서 반환한다.
• peek() - 큐의 맨 앞에 저장된 데이터 원소를 반환한다.

 

배열을 이용한 환형큐 파이썬 구현

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():
        	reaise IndexError('Queue full')
        self.rear = (self.rear+1) % self.maxCount
        slef.data[self.rear] = x
        self.count += 1
        
    def dequeue(self):
    	if self.isEmpty():
        	raise IndexError('Queue empty')        
        self.front = (self.front+1) % self.amxCount
        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)]

1. __init__
   1. maxCount : 큐의 크기
   2. data  : 큐의 실제 데이터 값
   3. count : 큐에 들어있는 개수
   4. front와 rear에 -1을 준 이유는 데이터를 조금더 쉽게 넣고 빼기 위함이다. (배열은 0부터 시작)
2. enqueue와 dequeue
   1. self.rear+1 % self.maxCount 또는 self.front+1 % self.maxCount을 준 것은 큐의 마지막까지 꽉차면 다시 처음부터 큐에 데이터가 돌 수 있게 하기 위해서이다.