Python으로 구현하는 자료구조 : Queue (2) Circular Queue

이번 포스팅에서는 자료구조 큐(Queue) 중에 Circular Queue(환형큐)에 대해 살펴보고

파이썬으로 Circular Queue를 구현하여 삽입(enqueue), 삭제(dequeue)하는 코드를 짜보도록 하겠습니다.

---

# Circular Queue란

Queue 자료구조의 특성상 한쪽 방향에선 데이터가 들어가고 한쪽 방향에서는 데이터가 나가면서 뒤에 저장된 데이터들을 한 칸씩 모두 이동해야 하는 한계가 있습니다. 물론 Linked List를 통해 큐를 구현한다면 이러한 한계점을 극복할 수는 있지만 리스트를 사용해 Queue를 구현하고자 한다면 Circular Queue를 만들어 한계를 극복할 수 있습니다.

Circular Queue는 번거로운 데이터 이동을 발생시키지 않고 주어진 공간을 활용할 수 있다는 장점이 있습니다. 다만 처음에 생성한 리스트의 크기를 기준으로 환형이 일어나기 때문에 enqueue가 많이 발생하지 않아 쓰지 않는 공간에 대한 낭비가 발생할 수도 있으며, 큐로 활용되는 리스트의 크기를 늘려야 할 경우 큐의 원소의 순서를 유지하면서 크기를 늘려야 하기 때문에 크기 조정이 어렵습니다.

# Circular Queue 구현하기

#파이썬 코드 - 리스트 사용

 
class CircularQueue():
 
    def __init__(self, max=5):
        self.max = max
        self.queue = [None]*self.max
        self.size = self.front = 0
        self.rear = None
 
 
    def is_empty(self):
        return self.size == 0
 
 
    def is_full(self):
 
        if self.rear == None:
            return False
        return self.next_index(self.rear) == self.front
 
 
    def next_index(self, idx):
        return (idx + 1) % self.max
 
 
    def enqueue(self, data):
        if self.is_full():
            raise Exception("Queue is Full")
 
        # 시작 index를 0으로 한다
        if self.rear == None:
            self.rear = 0
        else:
            self.rear = self.next_index(self.rear)
 
        self.queue[self.rear] = data
        self.size += 1
        return self.queue[self.rear]
 
 
    def deque(self):
        if self.is_empty():
            raise Exception('Queue is empty')
        self.queue[self.front] = None
        self.front = self.next_index(self.front)
        return self.queue[self.front]
 
 
    def display(self):
        print(self.queue)
 
 
if __name__ == "__main__":
    cq = CircularQueue()
    cq.display()  # [None, None, None, None, None]
    print(cq.enqueue(1))
    print(cq.enqueue(2))
    print(cq.enqueue(3))
    print(cq.enqueue(4))
    cq.display()  # [1, 2, 3, 4, None]
    print(cq.deque())
    print(cq.deque())
    cq.display()  # [None, None, 3, 4, None]
    print(cq.enqueue(5))
    print(cq.enqueue(6))
    cq.display()  # [6, None, 3, 4, 5]

# 파이썬 코드 - Linked list 사용