[Algorithm] 환형 큐(Circular Queue)_TIL Day3-2

환형 큐

- 정해진 개수의 저장 공간을 빙 돌려가며 이용하는 자료구조

- 큐가 가득 차면 더 이상 원소를 넣을 수 없음 (큐 길이를 기억해 활용해야 함)

- 저장 공간을 한정하여 공간 낭비를 줄일 수 있음

 

환형 큐 구현해보기

- 연산의 정의

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

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] 



def solution(x):
    return 0