[Python 자료구조] Circular Queue (링버퍼 큐)

💡 Circular Queue

번거로운 데이터 이동을 발생시키지 않고 주어진 공간을 활용하여, 디큐할 때 배열 안의 원소를 옮기지 않는 것이 Circular Queue 이다.

큐는 한쪽 끝에서만 데이터를 넣을 수 있고 다른 한쪽 끝에서만 데이터를 뺄 수 있는 구조를 가지고있다.

 

Circular 에서 사용되는 용어로는 2가지가 있다.

프런트(front) : 맨 앞 원소의 인덱스 

리어(rear) : 맨 끝 원소 뒤의 인덱스 ( 다음 큐 데이터가 저장되는 위치 )

 

💡 추가 설명

Queue 자료구조의 특성상 한쪽 방향에선 데이터가 들어가고, 한쪽 방향에서는 데이터가 나가면서, 

저장된 데이터들을 한 칸씩 모두 이동해야 하는 단점이 있다.

Linked List 를 통해 큐를 구현한다면 이런 한계점을 극복할 수 있다.

 

 

 

인큐와 디큐를 수행하면 front 와 rear 의 값이 변하게 되는데, 3개의 데이터 11, 42, 35 는 que[6], [7], [0] 에 저장된다. 

여기서 front 의 값은 6 이고 rear 의 값은 1이다.

 

👆 인큐

14를 인큐한 circular queue 이다. 

que[rear] 즉, [1] 에 14 를 저장하고 rear 값을 1 증가시켜 2 로 만든다.

 

👇 디큐

 

11을 디큐한 circular queue 이다.

맨 앞 원소인 que[front], 즉 que[6] 의 값인 11을 꺼내고 front 을 1 증가시켜 7로 만든다.

 

 

 

💡 코드

class CircularQueue:
    
    def __init__(self, maxSize):
        self.queue = []
        self.maxSize = maxSize 
        self.head = 0 # 큐의 시작
        self.tail = 0 # 큐의 끝
        
    # 큐 원소 추가
    def enqueue(self, data):
        size = self.size()
        
        if size == (self.maxSize - 1):
            print ("Queue is Full ")
            return None
        else:
            self.queue.append(data)
            self.tail = (self.tail+1) % self.maxSize
            return True
    
    # 큐 원소 삭제
    def dequeue(self):
        size = self.size()
        
        if size == 0:
            print ("Queue is Empty ")
            return None
        else:
            data = self.queue[self.head]
            self.head = (self.head+1) % self.maxSize
            return data
        
    # 큐의 크기 찾기
    def size(self):
        if self.tail >= self.head:
            qSize = self.tail - self.head
        else:
            qSize = self.maxSize - (self.head - self.tail)
        return qSize
    
size = input("Circular Queue input size :: ")
q = CircularQueue(int(size))

print(q.enqueue(10))
print(q.enqueue(20))
print(q.enqueue(30))
print(q.enqueue(40))
print(q.enqueue(50))
print(q.enqueue(70))
print(q.enqueue(80))
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())

 

💡 실행 결과