파이썬에서 Circular Queue 표현하기

시험공부를 하면서 Array를 활용한 Queue의 예시로 신기한게 있어서 들고왔습니다.

바로 이친구!! Circular Queue라는 친구인데요!!
Array를 통해 원형 모양의 Queue를 표현합니다

first의 index는 first element의 바로 이전에 위치하고,
rear은 last element의 위치로 정의합니다.

front <- (front+1) % MAX_QSIZE
rear <- (rear + 1) % MAX_QSIZE

위와 같은 index 구조가 나오는데요,
다음과 같은 그림을 보여줍니다.

항상 한 칸은 vacant한 상태로 두고 사용합니다.
크기는 파이썬에서 사용하는 Array의 특성상 MAX_QSIZE로 제한되어 있다는 특징을 가지고 있습니다.

empty state는 front == rear 일 때 비어있다고 표현하고,
full state는 front == (rear+1) % MAX_QSIZE 일 때 꽉 차있다고 표현을 합니다.

이를 클래스로 표현한다면 다음과 같습니다.

class ArrayQueue : # Circular Queue Class
    _CAPACITY = 10 # Default Capacity (real: _CAPACITY-1)
    
    def __init__(self):
        self.data = [None]*ArrayQueue._CAPACITY
        self.front = 0
        self.rear = 0
        
    def is_empty(self):
        return self.front == self.rear
    
    def is_full(self):
        return self.front == (self.rear+1)%ArrayQueue._CAPACITY
    
    def clear(self):
        self.front = self.rear
        
    def peek(self):
        if self.is_empty():
            return None
        else :
            return self.data[(self.front+1)%ArrayQueue._CAPACITY]    
        
    def enqueue(self, item):
        if self.is_full():
            raise Exception("Queue is full")
        else :
            self.rear = (self.rear+1)%ArrayQueue._CAPACITY
            self.data[self.rear] = item
            
    def dequeue(self):
        if self.is_empty():
            return None
        else :
            self.front = (self.front+1)%ArrayQueue._CAPACITY
            return self.data[self.front]
             
    def size(self):
        return (self.rear-self.front + ArrayQueue._CAPACITY)%ArrayQueue._CAPACITY
    
        print(out)

특징적인 점이라면 element의 수는 아까 말씀드렸던 것처럼 Array 크기보다 1개 작고
항상 연산시에 %MAX_QSIZE가 뒤에 붙어있는 모습을 볼 수 있습니다.

Linked List로 표현할 수 있는 방법도 있답니다!!
이를 도식화하면 다음과 같아요 :)

코드로 표현해볼까요?

class SinglyLinkedQueue :
    def __init__(self):
        self.front = None
        self.tail = None
        self._size = 0 
        
    def size(self):
        return self._size
        
    def is_empty(self):
        return self.front == None
    
    def clear(self):
        self.front = None
        self.tail = None
        self._size = 0
    
    def peek(self):
        if self.front == None:
            return None
        else :
            return self.front.data
        
    def enqueue(self, item):
        node = Node(item)
        
        if self.is_empty():
            self.front = node
            self.tail = node
            self._size += 1
        else :
            self.tail.next = node
            self.tail = node
            self._size += 1
            
    def dequeue(self):
        if self.is_empty():
            return None
        else :
            item = self.front.data
            if self.front == self.tail :
                self.front = None
                self.tail = None
                self._size -= 1
            else :
                self.front = self.front.next
                self._size -= 1
            return item
        
    def display(self):
        if self.is_empty() :
            print(None)
        else :
            node = self.front
            print(node.data, end=' ')
            
            while True:
                if node == self.tail:
                    break
                node = node.next
                print(node.data, end=' ')

이전 Array 방식과는 다르계 지속적으로 size를 초기화해주고 link를 새로 연결해주는 모습을 보실 수 있습니다!!

한 줄씩 읽다보면 조금 화나기도 하지만 열심히 공부해봅시다 ,,,🥺