파이썬) 환형 큐(Circuler Queue)

환형 큐란 정해진 개수의 저장 공간을 원형으로 돌려가며 사용하는 큐이다.

 

그림과 같은 환형큐가 있고, 시작점이 A 위치일 때 enqueue(A)를 하면 위와 같이 삽입이 된다.

 

그 후 위와 같은 방향으로 enqueue(B),enqueue(C)를 하면 B,C가 삽입이 된다.

 

큐의 삭제 연산 dequeue()를 실행하면 먼저 삽입된 A는 삭제될 것이다.

 

그 후 연산으로 위와 같은 그림이 되었을 때 데이터를 삽입하는 부분은 rear, 데이터를 꺼내는 부분은 front라는 포인터를 가진다. 환형 큐는 정해진 개수의 저장 공간을 이용하므로 큐가 가득 차있다면 삽입 연산을 실행할 수 없다. 이러한 특성이 반영된 환형 큐의 핵심 연산은 다음과 같다.

 

• size() : 큐에 들어 있는 원소 개수 추출
• isEmpty() : 큐가 비어있는지에 대해 판단
• isFull(): 큐가 꽉 차 있는지에 대한 판단
• enqueue() : 원소 x를 큐에 삽입
• dequeue() : 큐의 맨 앞에 저장된 데이터 원소를 제거
• peek() : 큐의 맨 앞에 저장된 데이터 원소를 참조

기본 큐의 연산에서 isFull()이 추가된 것을 볼 수 있다.

 

환형 큐를 배열로 표현한 코드는 다음과 같다.

class CircularQueue:

    def __init__(self, n):   # 빈 큐를 초기화
        self.maxCount = n    # 인자 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.size() == 0:
            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]

def solution(x):
    return 0

 

self.front, rear를 -1로 초깃값을 설정한 이유는 빈 큐에 삽입할 때와 원소가 하나만 있을 때 삭제하는 경우의 연산을 원활히 하기 위함이다.

 

enqueue()연산을 보면 데이터를 삽입하는 부분인 rear를 한 칸 앞으로 옮기고 그 위치에 원소 x를 넣는다. 이때 (self.rear+1) % self.maxCount를 쓰는데  뒤에 % self.maxCount가 붙는 이유는 rear가 self.maxCount번째에 오게됬다면 이는 큐를 한바퀴 돌았다는 얘기이다. 환형 큐이기 때문에 index가 다시 0으로 돌아오기 때문에 % self.maxCount를 이용하면 한바퀴(또는 그 이상)를 돈 rear를 다시 0~self.maxCount 위치에 놓을 수  있게 된다.

 

dequeue(),peek()도 enqueue()와 비슷한 원리로 코드가 구성되어 있다.