[자료구조] Circular Queue(원형 큐)(Python)

* 개요

Circular Queue(원형 큐)는 큐의 변형된 구조로서, 데이터를 넣는 부분(rear)과 데이터를 빼는 부분(front)을 포인터로 지정함으로써,enqueue와 dequeue를 하는 형태의 자료구조이다. 원형 큐에서 정해둔 큐의 크기보다 더 큰 경우(큐가 가득 찬 경우), 큐가 비어있을 경우에 포인터가 같은 위치를 지정하기 때문에 이를 해결하기 위해 한 공간을 비워놓는다.(None or Null)

 

* 파이썬으로 구현한 원형 큐

원형 큐를 리스트로 구현하였다.

MAX_SIZE = 5

class CircularQueue:
    def __init__(self):
        self.front = 0
        self.rear = 0
        self.queue = [None] * MAX_SIZE

    def enqueue(self, data):
        if self.isFull():
            print("원형 큐가 꽉 찼음.")

        else:
            self.rear = (self.rear + 1) % MAX_SIZE
            self.queue[self.rear] = data

    def dequeue(self):
        dequeue_data = None

        if self.isEmpty():
            print("원형 큐가 비어있음.")

        else:
            self.front = (self.front + 1) & MAX_SIZE
            dequeue_data = self.queue[self.front]

        return dequeue_data

    def clear(self) :
        self.front = self.rear
    
    def peek(self):
        peek_data = None

        if self.isEmpty():
            print("원형 큐가 비어있음.")

        else:
            peek_data = self.queue[(self.front + 1) % MAX_SIZE]

        return peek_data

    def isEmpty(self):
        is_empty = False

        if self.front == self.rear:
            is_empty = True

        return is_empty

    def isFull(self):
        is_full = False

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

        return is_full

    def printQueue(self):
        if self.front < self.rear :
            print(self.queue[self.front + 1 : self.rear + 1])
                
        else :
            print(self.queue[self.front + 1 : MAX_SIZE] + self.queue[0 : self.rear + 1])

원형 큐의 크기(MAX_SIZE)를 5의 상수로 지정하였다.

__init__()은 원형 큐의 초기화 부분으로서 데이터를 추출하는 front, 데이터를 삽입하는 rear 부분을 모두 0으로 선언한다. 그 후, queue에 MAX_SIZE만큼 None을 대입하여 리스트를 선언한다.

enqueue()는 삽입 함수로, 원형 큐가 꽉 찼는지 여부를 확인하고, 큐가 가득 차지 않았다면

(rear의 인덱스 + 1)  % MAX_SIZE 연산한 것을 rear에 대입한다. 그 후 변경된 rear 인덱스에 데이터를 추가해주면 된다.

dequeue()는 삭제 함수로, 원형 큐가 비어있는지 여부를 확인하고, 큐가 비어있지 않다면

(front의 인덱스 + 1) % MAX_SIZE 연산한 것을 front에 대입한다. 그 후 변경된 front 인덱스의 데이터를 반환한다.

clear()는 큐를 초기화하는 함수로, front의 인덱스를 rear의 인덱스로 바꿔준다. 이렇게 된다면 front == rear가 성립이 되고, 원형 큐의 기존의 인덱스에 새로운 데이터를 삽입할 수 있게 된다.

peek()는 큐의 front 인덱스의 데이터를 반환하는 함수로, 인덱스 변경은 이루어지지 않는다.

isEmpty() 함수는 큐가 비어있는지의 여부를 확인하는 함수로, front와 rear가 같다면 비어있는 것으로 간주한다.

isFull()함수는 큐가 데이터로 꽉 차 있는지의 여부를 확인하는 함수이다. 만약 front의 인덱스와 (rear + 1) % MAX_SIZE가 같다면 가득 찬 것으로 간주한다.

printQueue() 함수는 큐의 데이터를 출력하는 함수이다. 만약 front의 인덱스가 rear의 인덱스보다 작다면, front + 1의 인덱스부터 rear의 인덱스까지의 데이터를 출력한다. 그러나 front의 인덱스가 rear의 인덱스보다 크거나 같다면(초기화하였을 경우(clear) 또는 데이터 삽입과 삭제가 전혀 이루어지지 않은 초기 상태의 경우(init)), front + 1의 인덱스부터 MAX_SIZE 이전의 데이터 + 큐의 0 인덱스부터 rear의 인덱스의 데이터까지 출력한다.