환형 큐 (Circular Queues)

큐(Queue)의 활용

• 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 (asynchronously) 일어나는 경우
  • producer가 물건을 만들고 consumer가 처음 만들어 진 것부터 사용하는 경우
• 자료를 생성하는 작업이 여러 곳에서 일어나는 경우
  • producer 여러명이 각각 물건을 만들어서 쌓으면 consumer가 처음 만들어 진 것부터 사용하는 경우
• 자료를 일어나는 작업이 여러 곳에서 일어나는 경우
  • 물건을 사용하는 consumer이 여러명 인 경우
• 자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 일어나는 경우
  • producer, consumer 둘다 여러명인 경우
• 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우

환형 큐 (Circular Queue)

• 정해진 개수의 저장 공간을 빙 돌려가며 이용하는 큐
• rear: 데이터를 집어 넣는 부분
• front: 데이터를 꺼내는 부분
• 큐가 가득 차면, 더이상 원소를 넣을 수 없다. (큐 길이를 기억하고 있어야 편하다.)

환형 큐의 추상적 자료구조 구현

연산의 정의

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

배열로 구현한 환형 큐

• 정해진 길이 n (예에서는 6)의 리스트를 확보해 두고 시작

  예시
  Q.enqueue(A) # rear: A
  Q.enqueue(B) # rear: B
  Q.enqueue(C) # rear: C
  Q.enqueue(D) # rear: D
  r1 = Q.dequeue() # front: A, r1: A
  r2 = Q.dequeue() # front: B, r2: B
  Q.enqueue(E) # rear: E
  Q.enqueue(F) # rear: F
  Q.enqueue(G) # rear: G
  r3 = Q.dequeue() # front: C, r3: C

• front와 rear를 적절히 계산하여 배열을 환형으로 재활용

• 배열로 구현한 환형 큐

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.ifFull():
    	raise IndexError('Queue full')
    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]