[자료구조] 원형 큐 Circular Queue

원형 큐(Circular Queue)란 선형 큐의 단점을 보완하기 위한 자료구조이다.

rear이 가리키는 포인터가 배열의 마지막 인덱스를 가리키고 있을 때 앞쪽에서 Dequeue로 발생한 배열의
빈 공간을 활용할 수 없는 선형 큐의 단점을 보완해준다.

단점으로는 선형 큐와는 다르게 Maximum Size에 의해 Overflow가 발생할 수 있다는 점이다.
원형 큐의 핵심은 index % Maximum Size로 front, rear의 index를 조정하는 것이다.

원형 큐를 구현하는 방법은 일반적으로 배열로 구현하는 방법이 있고, 그 방법으로 파이썬 알고리즘 인터뷰 를 참고하며 구현했다.

isEmtpy, isFull의 마지막 조건이 도저히 생각이 안났다..

LeetCode 622번 문제이다.

class MyCircularQueue:

    def __init__(self, k: int):
        self.max_size = k
        self.array = [None] * k
        self.front_idx = 0
        self.rear_idx = 0

    def enQueue(self, value: int) -> bool:
        if self.array[self.rear_idx] is None:
            self.array[self.rear_idx] = value
            self.rear_idx = (self.rear_idx + 1) % self.max_size
            return True
        else:
            return False

    def deQueue(self) -> bool:
        if self.array[self.front_idx] is None:
            return False
        else:
            self.array[self.front_idx] = None
            self.front_idx = (self.front_idx + 1) % self.max_size
            return True

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

    def Rear(self) -> int:
        if self.array[self.rear_idx - 1] is None:
            return -1
        else:
            return self.array[self.rear_idx - 1]

    def isEmpty(self) -> bool:
        if ((self.front_idx == self.rear_idx) and (self.array[self.front_idx] is None)):
            return True
        return False

    def isFull(self) -> bool:
        if ((self.front_idx == self.rear_idx) and (self.array[self.front_idx] is not None)):
            return True
        return False

        # Your MyCircularQueue object will be instantiated and called as such:
        # obj = MyCircularQueue(k)
        # param_1 = obj.enQueue(value)
        # param_2 = obj.deQueue()
        # param_3 = obj.Front()
        # param_4 = obj.Rear()
        # param_5 = obj.isEmpty()
        # param_6 = obj.isFull()

---

Reference

• 파이썬 알고리즘 인터뷰