환형 큐(Circular Queue)

1 환형 큐(Circular Queue)란?

• 정해진 개수의 저장 공간을 빙 돌려가며 이용한다
• 배열로 큐를 구현했을 때처럼 dequeue 후 생기는 문제를 보완하기 위해 사용된다
• 큐가 가득 차면 더이상 원소를 넣을 수 없다 → 큐 길이를 기억하고 있어야 함
  

2 환형 큐 연산의 정의

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

3 배열로 구현한 환형 큐

3.1 환형 큐의 동작

1. 정해진 길이 n의 리스트 확보, Q = Queue()

2. Q.enqueue(A)

3. Q.enqueue(B) Q.euqueue(C) Q.euqueue(D)

4. r1 = Q.dequeue() (=A)

5. r2 = Q.dequeue()

6. Q.enqueue(F)

   → 큐가 full인 상태가 아니다

7. Q.enqueue(G)

   dequeue해 무효해진 값을 덮어쓴다

   rear가 0번 인덱스를 갖도록 한다

8. r3 = Q.dequeue()

구현할 때, 마지막 인덱스에 도달하더라도 다음에는 0으로 옮겨질 수 있도록 해야 한다

3.2 구현 코드

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')
        return self.data[(self.front+1)%self.maxCount]