큐 level 2 (환형 큐, Circular Queue)

1) 환형 큐(Circular Queue)

  - 컴퓨터 시스템 내에서 이용할 수 있는 자원이 한정적 → 큐의 길이를 한정하여 사용

  - 배열로 큐 구현 시 길이에 비례한 시간복잡도를 가진 연산이 있음

  - 위 두 문제 포함 큐 구현시 발생하는 문제들을 보완하기 위해 환형 큐(Circular Queue)를 사용

  - 환형 큐(Circular Queue) → 정해진 개수의 저장 공간을 돌려가며 이

  - Fornt : dequeue가 이뤄지는 index / rear : enqueue가 발생 index          * 초기 상태 : front == rear

 

2) 환형 큐 자료구조 구현

  ① 배열로 구현한 환형 큐

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

 

  ② 배열로 구현한 환형 큐 연산

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():
            # IndexError('Queue full') exception으로 처리
            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]