[Python 자료구조] 환형 큐(Circular Queue)

(A 24-byte keyboard circular buffer, wikipedia)

 

 #환형 큐

 - '정해진' 개수의 저장 공간을 빙 돌려가며 이용

 - 큐가 가득 차면 더이상 원소를 넣을 수 없음

 

 

#연산의 정의

• size() : 현재 큐에 들어 있는 데이터 원소의 수를 구함
• isEmpty() : 현재 큐가 비어 있는지를 판단
• isFull() : 큐에 데이터 원소가 꼭 차 있는지를 판단
• qneueue(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():
            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]