622. Design Circular Queue

Circle Queue(원형 큐)를 구현해보자

 

원형 큐는 일반적인 큐와 다르게 끝나는 지점이 다시 시작으로 이어져서 기존 큐의 단점을 극복가능하다.

(기본 큐는 지나온 지점을 다시 재활용이 불가능하다.)

 

구현 방법에는 일반적으로는 front와 rear, 두 포인터를 가지고 구현을 한다. 

또한, 배열에 특별한 값(None)을 사용해서 현재 사용중인지 아닌지 구분한다. 

 

class MyCircularQueue:
    def __init__(self, k: int):
        self.front = 0
        self.rear = 0
        self.queue = [None] * k
        self.len = k
    def enQueue(self, value: int) -> bool:
        # rear 지점에 None일 경우에는 비어 있는 상태
        if self.queue[self.rear] is None:
            self.queue[self.rear] = value
            self.rear = (self.rear + 1) % self.len
            return True
        else: # Queue의 rear지점이 None이 아니면 오류 생긴것
            return False

    def deQueue(self) -> bool:
        # enQueue와는 반대로 front 지점이 None이면 저장상태가 아님
        if self.queue[self.front] is None:
            return False
        else:
            # front의 지점은 None으로 만든다
            self.queue[self.front] = None
            self.front = (self.front + 1) % self.len
            return True

    def Front(self) -> int:
        return -1 if self.queue[self.front] is None else self.queue[self.front]

    def Rear(self) -> int:
        # rear는 enQueue에서 +1을 먼저 하므로 Rear()를 호출할때는 -1을 해준다.
        return -1 if self.queue[self.rear-1] is None else self.queue[self.rear-1]

    def isEmpty(self) -> bool:
        return self.front == self.rear and self.queue[self.front] is None

    def isFull(self) -> bool:
        return self.front == self.rear and self.queue[self.front] is not None