파이썬으로 구현하는 원형 큐(Circular Queue)

원형 큐(Circular Queue)란?

배열로 구현 된 선형 큐(Linear Queue)의 경우 데이터의 삽입/삭제 시 데이터들을 앞으로/뒤로 당겨주는 과정이 필요해 최악의 경우 O(n)의 시간복잡도를 가지게 된다. 이러한 선형 큐의 단점을 극복한 구조가 원형 큐이다

 

0. 멤버 변수&초기화

먼저 원형 큐 클래스의 멤버 변수(member variable)화 초기화하는 과정을 살펴보자

class CircleQueue:

    rear = 0
    front = 0
    MAX_SIZE = 100
    queue = list()
    
    def __init__(self):
    	self.rear = 0
        self.front = 0
        self.queue = [0 for i in range(self.MAXSIZE)]

 

1. 공백 상태

원형큐가 비워져 있는 경우 rear == front 이다

def is_empty(self):
	if self.rear == self.front:
    	return True
    return False

 

2. 포화 상태

앞에서, 공백 상태를 front == rear로 구분하기 때문에 포화상태의 경우 위의 사진처럼 한 칸이 비어있다.

따라서 배열에 한 칸을 비움으로써 공백 상태와 포화 상태를 구분하기로 한다

def is_full(self):
	if (self.rear+1)%self.MAX_SIZE == self.front:
    	return True
    return False

 

 

 

3. 데이터 삽입

rear에서 삽입이 이루어지므로, front는 값의 변경이 없고 rear += 1을 하며 데이터를 삽입한다

def enqueue(self, x):
	if is_full():
    	print("ERROR: FULL")
        return
    self.rear = (self.rear+1)%(self.MAX_SIZE)
    self.queue[self.rear] = x

 

4. 데이터 삭제

큐는 선입선출(FIFO) 구조로, 앞에서 삭제가 이루어져야 한다. 따라서 rear는 값의 변경이 없고 front += 1을 하며 데이터를 삭제한다

def dequeue(self):
	if is_empty():
    	print("ERROR: EMPTY")
        return
    self.front = (self.front +1) % MAX_SIZE
    return self.queue[self.front]

 

Optional. (Print 함수)

추가로, 현재 큐에 저장된 요소를 출력해주는 함수는 아래와 같다

def queue_print(self):
	i = self.front
    if is_empty():
    	print("EMPTY QUEUE")
        return
    while True:
    	i = (i+1) % self.MAX_SIZE
        print(self.queue[i], ' ')
        if i == self.rear:
        	break