2.2 자료구조 큐(queue) - 원형 큐

원형 큐(Circle queue): 기존의 큐는 프론트 값이 계속 증가되면서 공간을 잡아먹는 문제가 있음, 원형큐는 연결리스트를이용하여 공간의 낭비 없이 큐를 구현한 것이다.

 

원형큐의 동작과정은 다음 그림과 같다.

 

 

 

원형 큐의 연산은 다음 표와 같다.

연산	설명
enQueue	큐에 데이터 삽입
deQueue	큐에 데이터 삭제
peek	front 가르키는 데이터 확인
isEmpty	큐가 비어있는지 확인
isFull	큐가 꽉 차있는지 확인

 

 

다음은 파이썬을 이용한 원형큐 구현 소스코드이다.

class CircleQueue:
    def __init__(self, size):
        self.data = [None] * size
        self.size = size
        self.count = self.rear = self.front = 0

    #데이터 삽입
    def enQueue(self, value):
        if self.isFull():
            return False
        self.rear = (self.rear % self.size)
        self.data[self.rear] = value
        self.rear = (self.rear + 1) self.size
        self.count +=1

    #데이터 삭제
    def deQueue(self):
        if self.isEmpty():
            return #큐가 비어있을시 예외 처리
        else:
            self.front = (self.front % self.size)
            self.data[self.front] = None
            self.front = (self.front + 1) self.size
            self.count -= 1

    #front가 가르키는 데이터 확인
    def peek(self):
        if self.isEmpty():
            return  # 큐가 비어있을시 예외 처리
        else:
            return self.data[self.front]

    def isEmpty(self):
        if self.front == self.rear:
            return not self.data

    def isFull(self) -> bool:
        return self.size == self.count

queue = CircleQueue(10)     #큐 생성
print(queue.isEmpty())      #큐가 비어있는지 확인
queue.enQueue(1)            #큐에 1 삽입
queue.enQueue(2)            #큐에 2 삽입
queue.enQueue(3)            #큐에 3 삽입
print(queue.data)           #큐 상태 확인
queue.deQueue()             #큐에 가장 먼저들어온 1삭제
print(queue.data)           #큐 상태 확인
queue.enQueue((4))          #큐에 4 삽입
print(queue.data)           #큐 상태 확인
print(queue.isEmpty())      #큐가 비어있는지 확인
print(queue.isFull())       #큐가 꽉 찾는지 확인