[자료구조] 원형 큐(Circular Queue) 개념 및 코드

 

 

이번 포스팅에선 큐의 변형인 원형 큐(Circular Queue)에 대해 알아보겠습니다.

큐에 대한 사전 지식이 없다면 이해가 어려울 수 있으니, 미리 개념을 습득하고 오시길 바랍니다.

 

 

[큐(Queue) 개념 이해하기]

https://mengu.tistory.com/30?category=931463 

[자료구조] 큐(Queue) 개념 및 코드 구현

 

 

 

목차

📃 원형 큐(Circular Queue) 정의 및 원리

📃 원형 큐 구현

📃 활용 예시

 

 

 

원형 큐(Circular Queue) 정의 및 원리

 

📌 정의

 

큐는 배열로 구현된 선형의 형태를 가집니다. 데이터 삽입/삭제 시 데이터들을 앞 혹은 뒤로 당겨주는 과정이 필요하며, 이는 불필요한 시간 낭비를 불러일으킵니다. 이 단점을 극복하기 위해 고안된 것이 원형 큐입니다. 원형 큐는 선형 형태가 아닌, 말 그대로 원형 형태를 가집니다. 

 

 

 

 

📌 원리

 

rear는 큐의 뒷단이며, front는 큐의 앞단입니다. 원형 큐도 FIFO 방식을 따릅니다.

(0) 원형 큐의 크기를 사전에 정하고, 빈 리스트를 정의합니다.

(1) 리스트에 데이터를 삽입하면, rear는 1로 옮겨집니다.

(2) 리스트에 데이터를 삽입하면, rear는 2로 옮겨집니다.

(3) 리스트에서 데이터를 denqueue() 해주면, front가 1로 옮겨지며, 1에 저장되어 있는 데이터가 반환됩니다.

만약 원형 큐에 데이터가 꽉 차면 어떻게 될까요? 더 이상 새로운 데이터를 넣지 못합니다.

 

 

 

 

 

 

원형 큐 구현

원형 큐 구현은 해당 블로그를 참고했습니다.

 

 

📌 class와 init 함수

 

먼저 원형 큐 사이즈를 정의하고, class를 선언합니다.

멤버 변수는 front(앞단), rear(뒷단), items(데이터 리스트) 등을 선언하고, 동시에 front/rear를 0으로 초기화합니다.

MAX_QSIZE = 8
class CircularQueue :
    def __init__(self):
        self.front = 0
        self.rear = 0
        self.items = [None] * MAX_QSIZE

 

[원형 큐 초기화 상태]

 

 

 

 

📌 isEmpty()

 

원형 큐가 비어있는지 확인합니다.

간단하게 front와 rear의 수가 같으면 원형 큐가 비어있다고 결론 내립니다.

def isEmpty(self):
	return self.front == self.rear

 

 

 

📌 isFull()

 

원형 큐가 차있는지 확인하는 함수입니다.

rear+1을 큐의 최대 사이즈로 나누었을 때 front와 같다면, 원형 큐가 가득 차있다고 결론 내립니다. 

def isFull(self):
	return self.front == (self.rear+1)%MAX_QSIZE

 

* 예시) 현재 rear가 7이고, front가 0이라고 하겠습니다. 현재 원형 큐는 가득 차 있는 상태입니다. rear+1은 8이며, 원형 큐의 최대 사이즈 또한 8입니다. (rear+1)% MAX_QSIZE는 0이 나올 것이며, front는 0이기에 원형 큐가 가득 차있다고 결론 내릴 수 있습니다.

 

 

 

 

 

📌 enqueue()

 

원형 큐가 가득 차있지 않다면, 데이터 삽입을 진행합니다. rear의 위치를 한 칸 옮겨주고, 본래 rear 자리에 데이터를 넣어줍니다.

def enqueue(self, item):
    if not self.isFull():
        self.rear = (self.rear+1)%MAX_QSIZE
        self.items[self.rear] = item

 

* 예시) 현재 rear가 1이고, front가 0이라고 하겠습니다. enqueue를 하면 (self.rear+1)%MAX_QSIZE = 2가 됩니다. 이에 따라 rear는 한 칸 옮기고, 기존의 rear 자리에 데이터가 들어가는 형태입니다.

 

 

 

 

 

📌 dequeue()

 

원형 큐가 비어있지 않다면, front를 한칸 옮깁니다. 동시에 front에 저장되어 있던 데이터를 반환합니다.

def dequeue(self):
    if not self.isEmpty():
        self.front = (self.front+1)%MAX_QSIZE
        return self.items[self.front]

 

 

 

📌 peek()

 

원형 큐가 비어있지 않다면, front의 다음 칸에 있는 데이터를 반환합니다.

def peek(self):
    if not self.isEmpty():
       return self.items[(self.front+1)%MAX_QSIZE]

 

* 예시) 현재 rear가 4, front가 0입니다. 데이터가 4개 삽입되어 있는 상태입니다. 여기서 peek() 함수를 실행할 경우, (self.front+1)%MAX_QSIZE=2가 되고, 1 위치의 데이터를 반환합니다.

 

 

 

📌 clear()

 

clear() 함수는 원형 큐를 초기화하는 함수입니다. front와 rear를 같은 위치로 놓으면 초기화됩니다. 이제까지 저장해놓은 데이터는 어떻게 되는 것이냐라는 의문이 들 수 있습니다. 

def clear(self):
    self.front = self.rear

 

* 예시) 상황을 가정해보겠습니다. rear=4, front=2입니다. front를 rear와 같은 숫자로 초기화하면, self.items[front]에는 어떤 데이터도 들어있지 않을 것입니다. 이 상태에서 dequeue를 한다면 어떻게 될까요? 당연히 isEmpty() 함수가 원형 큐는 비어있다고 결론내릴 것입니다. enqueue를 한다면? self.items[front] 자리에 데이터가 하나 들어가고, rear는 한 칸 옮겨집니다. 즉, 기존 리스트에 데이터가 있어도, rear와 front만 같게 하면 원형 큐는 초기화된 것처럼 사용할 수 있습니다.

 

 

 

 

 

📌 __len__()

 

__len__() 함수는 원형 큐의 길이를 반환합니다. rear=4, front=2라고 가정하고 계산해보겠습니다. self.rear - self.front + MAX_QSIZE는 10입니다. 10을 8로 나누면 나머지는 2가 됩니다. 2가 원형 큐의 길이가 되겠습니다.

def __len__(self):
    return (self.rear-self.front + MAX_QSIZE)%MAX_QSIZE

 

 

 

📌 전체 코드

 

원형 큐를 구현한 전체 코드입니다.

MAX_QSIZE = 10
class CircularQueue :
    def __init__(self):
        self.front = 0
        self.rear = 0
        self.items = [None] * MAX_QSIZE
    
    def isEmpty(self):
        return self.front == self.rear
    
    def isFull(self):
        return self.front == (self.rear+1)%MAX_QSIZE
    
    def enqueue(self, item):
        if not self.isFull():
            self.rear = (self.rear+1)%MAX_QSIZE
            self.items[self.rear] = item
    
    def dequeue(self):
        if not self.isEmpty():
            self.front = (self.front+1)%MAX_QSIZE
            return self.items[self.front]
    
    def peek(self):
        if not self.isEmpty():
            return self.items[(self.front+1)%MAX_QSIZE]
 
    def clear(self):
        self.front = self.rear
    
    def __len__(self):
        return (self.rear-self.front + MAX_QSIZE)%MAX_QSIZE

 

 

 

 

 

활용 예시

 

📌 enqueue()

MAX_QSIZE = 20    
circular = CircularQueue()

for i in range(20):
    circular.enqueue(i)

print(f'원형 큐의 길이 : {circular.__len__()}')



=> 원형 큐의 길이 : 19

 

 

 

📌 dequeue()

for i in range(20):
    circular.dequeue()
    
print(f'원형 큐의 길이 : {circular.__len__()}')


더 이상의 데이터가 남아있지 않습니다.
원형 큐의 길이 : 0

 

 

📌 clear()

for i in range(20):
    circular.enqueue(i)

print(f'원형 큐의 길이 : {circular.__len__()}')

circular.clear()
    
print(f'원형 큐의 길이 : {circular.__len__()}')  



원형 큐의 길이 : 19
원형 큐의 길이 : 0