Circular Queue

---

• 원형 큐(Circular Queue) 또는 환형 큐 또는 링버퍼(Ring Buffer)라고 부른다.
• 큐와 마찬가지로 FIFO 구조를 지닌다는 점에서 기존의 큐와 동일
• Queue 자료구조의 특성상 한쪽 방향에선 데이터가 들어가고 한쪽 방향에서는 데이터가 나가면서 뒤에 남아있는 데이터들을 한 칸씩 모두 이동해야 하는 한계가 있는데 이를 극복하기 위해 리스트를 사용해 Circul Queue를 만들어 한계를 극복 가능합니다.

https://www.geeksforgeeks.org/circular-queue-set-1-introduction-array-implementation/

Python으로 Circular Queue 구현

---

class CircularQueue:

    # 해당 배열의 크기를 인자로 받아 초기화
    def __init__(self, k):
        self.q = [None] * k
        self.len = k
        self.front = 0
        self.rear = 0

    # 삽입 메소드
    def enQueue(self, value):
        if self.q[self.rear] is None:
            self.q[self.rear] = value   # rear 포인터에 입력받은 인자를 넣는다.
            self.rear = (self.rear + 1) % self.len  # 전체길이로 나머지연산을 하여 포인터가 전체기리를 넘지 못하게 이동시킨다.
            return True
        else:
            return False

    # 추출 메소드
    def deQueue(self):
        if self.q[self.front] is not None:
            result = self.q[self.front]     # result 변수에 배열의 첫번째 요소를 답는다.
            self.q[self.front] = None   # 배열의 첫번쨰요소를 삭제
            self.front = (self.front + 1) % self.len
            return result     # result 변수 리턴
        else:
            return False

    # 배열의 첫번째 요소 출력
    def pr_front(self):
        return False if self.q[self.front] is None else self.q[self.front]

    # 배열의 마지막 요소 출력
    def pr_rear(self):
        return False if self.q[self.rear] is None else self.q[self.rear]

    # 배열이 비어있는지 확인
    def is_empty(self):
        return self.q[self.front] == None and self.q[self.rear] == None

    # 배열이 꽉 차있는지 확인
    def is_full(self):
        return None not in self.q


queue = CircularQueue(3)
queue.enQueue(1)
queue.enQueue(2)
queue.enQueue(3)
print(queue.deQueue())
print(queue.deQueue())
print(queue.deQueue())
print(queue.is_empty())
print(queue.is_full())

### OutPut

# 1
# 2
# 3
# True
# False

• 큐에는 원래 pr_rear()연산이 없지만 두개의 포인터를 사용해서 (self.front, self.rear) 연산을 할 수 있엇다.