2.큐에 비해 원형큐가 가지는 장단점

간단하게 결론부터 말하자면 

원형 큐의 장점은 처음과 끝이 연결되어 있는 형태로, 
데이터가 배열의 끝에 다다르면 다시 처음으로 돌아올 수 있어 이미 사용했던 부분도 재사용이 가능하다는 점이다.
또한, 선형 큐보다 메모리를 낭비하지 않는 다는 점이다.

원형 큐의 단점은 원형 큐는 배열이 꽉차있는지, 비어있는지를 구분하기 위하여 한 칸의 공백은 무조건 있어야 한다는 점이다.

 

선형 큐(Queue)는, 이미 사용한 영역인 front의 앞부분에 대해서 다시 활용을 못하기 때문에 메모리를 낭비한다는 단점이 있었다.
그리고 큐가 다 찼을 경우 데이터들을 앞쪽으로 이동시켜 사용하는 방법이 있지만 남아있는 모든 데이터를 다 이동시켜야 한다는 불편한 작업을 수행해야 하기 때문에 그리 효율적으로 동작하지 못한다.

이런 문제를 해결하고자 나온 큐가 바로 원형 큐이다.

 

#원형 큐

 - '정해진' 개수의 저장 공간을 빙 돌려가며 이용

 - 큐가 가득 차면 더이상 원소를 넣을 수 없음

 

 

#연산의 정의

• size() : 현재 큐에 들어 있는 데이터 원소의 수를 구함
• isEmpty() : 현재 큐가 비어 있는지를 판단
• isFull() : 큐에 데이터 원소가 꼭 차 있는지를 판단
• qneueue(x) : 데이터 원소 x를 큐에 추가
• dequeue() : 큐의 맨 앞에 저장된 데이터 원소를 제거(또한, 반환)
• peek() : 큐의 맨 앞에 저장된 데이터 원소를 반환(제거하지 않음)

class CircularQueue:

#큐 초기화
    def __init__(self, n):
        self.maxCount = n
        self.data = [None] * n
        self.count = 0
        self.front = -1
        self.rear = -1

 

    # 현재 큐 길이를 반환
    def size(self):
        return self.count

 

    # 큐가 비어있는지 
    def isEmpty(self):
        return self.count == 0

 

    # 큐가 꽉 차있는지
    def isFull(self):
        return self.count == self.maxCount

 

# 데이터 원소 추가
    def enqueue(self, x):
        if self.isFull():
            raise IndexError('Queue full')
        
        self.rear = (self.rear + 1) % self.maxCount
        self.data[self.rear] = x
        self.count += 1

 

    #데이터 원소 제거
    def dequeue(self):
        if self.isEmpty():
            raise IndexError('Queue empty')

        self.front = (self.front + 1) % self.maxCount
        x = self.data[self.front]
        self.count -= 1
        return x

 

    # 큐의 맨 앞 원소 반환
    def peek(self):
        if self.isEmpty():
            raise IndexError('Queue empty')
        return self.data[(self.front + 1) % self.maxCount]