Circular Queue (or Ring Buffer)

Circular Queue (or Ring Buffer)

원형큐, 환형큐, 링버퍼 등으로 불리고, 일반적인 Queue와 마찬가지로 FIFO 구조를 지니는데 정해진 개수의 저장공간을 만들고 front(head)와 rear(tail)의 위치를 원형으로 옮겨가며 사용하기 때문에 불필요한 데이터의 이동이 발생하지 않고 큐가 가득찬다면 더이상 enqueue할 수 없다.

Circular Queue

1. __init__(self, capacity)
   • self.capacity 👉🏻 queue의 원하는 크기
   • self.queue = [None] * capacity 👉🏻 크기만큼 빈데이터를 미리 만들어 둔다.
   • self.tail = -1 👉🏻 데이터 삽입위치로 -1로 만들어서 enqueue시 rear +1로 0부터 들어가게 만들어준다.
   • self.head = 0 👉🏻 데이터 삭제위치
   • self.size = 0 👉🏻 해당 사이즈가 capacity와 같다면 원형큐가 가득 찬것이다.
2. Enqueue(self, item) - 삽입
   • self.size == self.capacity 일 경우, 에러를 내보낸다.
   • self.tail 위치를 +1하는데 queue의 크기보다 커지면 안되기 때문에 % self.capacity로 나머지를 이용한다.
   • self.queue[self.tail]의 위치에 item을 삽입하고, self.size도 +1 늘려준다.
3. Dequeue(self) - 삭제
   • self.size == 0이라면 삭제할게 없기 때문에 에러를 내보낸다.
   • deq = self.queue[self.head] 로 내보낼 데이터를 변수로 반환해줘두 된다.
   • self.queue[self.head] = None으로 None으로 데이터를 변경해준다.
   • self.front = (self.front + 1) % self.capacity로 항상 큐의 크기보다 커지지 않게 만들어준다.
   • self.size -= 1 로 사이즈를 줄여준다.
4. front(self)
   • 현재 front위치에 있는 아이템을 보여준다.
   • queue가 비었다면 에러를 내보낸다.
5. rear(eslf)
   • 현재 rear위치에 있는 아이템을 보여준다.
   • queue가 비었다면 에러를 내보낸다.
6. isEmpty(self)
   • size를 확인하여 0이면 True아니라면 False를 반환한다.
7. isFull(self)
   • size == capacity와 같다면 True 아니라면 False를 반환한다.

Circular Queue 구현

class MyCircularQueue:
    def __init__(self, k: int):
        self.capacity = k
        self.queue = [None] * self.capacity
        self.tail = -1
        self.head = 0
        self.size = 0

    def enQueue(self, value: int) -> bool:
        if self.size == self.capacity:
            print("Error: Queue is Full")
            return False
        else:
            self.tail = (self.tail + 1) % self.capacity
            self.queue[self.tail] = value
            self.size += 1
            return True

    def deQueue(self) -> bool:
        if self.size == 0:
            print("Error: Queue is Empty")
            return False
        else:
            # deq = self.queue[self.head]
            self.queue[self.head] = None
            self.head = (self.head + 1) % self.capacity
            self.size -= 1
            return True # deq

    def front(self) -> int:
        if self.queue[self.head] == None:
            return -1
        else:
            findHead = self.queue[self.head]
            return findHead

    def rear(self) -> int:
        if self.queue[self.tail] == None:
            return -1
        else:
            findTail = self.queue[self.tail]
            return findTail

    def isEmpty(self) -> bool:
        empty = False
        if self.size == 0:
            empty = True
        return empty

    def isFull(self) -> bool:
        full = False
        if self.size == self.capacity:
            full = True
        return full

ringBuffer = MyCircularQueue(5)

Reference

https://towardsdatascience.com/circular-queue-or-ring-buffer-92c7b0193326