원형 큐(Circular Queue) 동작원리 (배열 구현, 특징)

큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO) 방식의 자료구조입니다. 하지만 일반적인 선형 큐(Linear Queue)를 배열로 구현할 경우, 데이터가 삭제된 앞쪽 공간을 재사용하지 못해 메모리가 낭비되거나, 실제로는 공간이 남았음에도 꽉 찼다고 인식하는 '거짓 오버플로우(False Overflow)' 문제가 발생합니다. 이를 해결하기 위해 고안된 것이 바로 원형 큐(Circular Queue)입니다. 원형 큐는 배열의 끝과 시작을 논리적으로 연결하여 메모리 효율성을 극대화한 구조로, 네트워크 버퍼나 CPU 스케줄링 등 제한된 자원을 효율적으로 관리해야 하는 시스템에서 핵심적인 역할을 수행합니다.

1. 원형 큐(Circular Queue)의 핵심 원리와 구조

원형 큐는 물리적으로는 선형 배열이지만, 논리적으로는 배열의 마지막 인덱스가 첫 번째 인덱스와 연결된 링(Ring) 형태를 띱니다. 이를 통해 선형 큐의 단점인 '앞쪽 공간 낭비'를 완벽하게 해결합니다.

1-1. 투 포인터(Two Pointers)와 회전

원형 큐를 제어하기 위해서는 두 개의 포인터가 필요합니다.

Front (머리): 첫 번째 데이터의 바로 앞 인덱스(또는 첫 데이터)를 가리키며, 삭제(Dequeue) 연산 시 이동합니다.
Rear (꼬리): 마지막 데이터의 인덱스를 가리키며, 삽입(Enqueue) 연산 시 이동합니다.

1-2. 모듈러 연산(Modulo Operation)의 마법

원형 큐 구현의 핵심은 나머지 연산자(%)입니다. 인덱스가 배열의 크기(Capacity)를 넘어설 때 다시 0으로 돌아오게 만들기 위해 다음 공식을 사용합니다.

인덱스 이동 공식: (Current_Index + 1) % MAX_SIZE

이 공식을 통해 Rear나 Front가 배열의 끝에 도달했을 때, 다음 위치를 자동으로 배열의 시작점(0)으로 지정할 수 있습니다.

2. 상태 판별: 공백(Empty)과 포화(Full)의 구분

원형 큐 구현 시 가장 중요한 기술적 이슈는 "큐가 비었는지, 꽉 찼는지 어떻게 구분할 것인가?"입니다. 단순히 Front == Rear 조건만으로는 이 두 상태를 구분할 수 없습니다.

2-1. 더미(Dummy) 공간 활용

가장 일반적인 해결책은 배열의 한 칸을 비워두는 것입니다. 이를 통해 두 상태를 명확히 구분할 수 있습니다.

공백 상태 (Empty): Front == Rear (초기 상태)
포화 상태 (Full): (Rear + 1) % MAX_SIZE == Front (Rear의 다음 칸이 Front일 때)

한 칸을 사용하지 못하는 아주 작은 메모리 손실이 발생하지만, 상태 판별 로직이 O(1)로 매우 간단해지고 안정성이 높아집니다.

3. 파이썬(Python)을 이용한 배열 기반 구현

다음은 리스트(배열)를 사용하여 원형 큐의 핵심 로직을 구현한 예제입니다. 모듈러 연산을 통해 인덱스가 순환하는 과정을 확인하십시오.


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

    def is_empty(self):
        return self.front == self.rear

    def is_full(self):
        # Rear의 다음 위치가 Front라면 꽉 찬 상태
        return (self.rear + 1) % self.capacity == self.front

    def enqueue(self, item):
        if self.is_full():
            print("Queue is Full (Overflow)")
            return
        
        # Rear를 먼저 이동시키고 데이터 저장
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = item

    def dequeue(self):
        if self.is_empty():
            print("Queue is Empty (Underflow)")
            return None
            
        # Front를 이동시키고 해당 위치의 데이터 반환
        self.front = (self.front + 1) % self.capacity
        item = self.queue[self.front]
        self.queue[self.front] = None  # (선택) 데이터 초기화
        return item

# 사용 예시 (크기 5인 큐 -> 실제 데이터는 4개 저장 가능)
cq = CircularQueue(5)
cq.enqueue(10)
cq.enqueue(20)
print(cq.dequeue())  # 10 출력

[핵심 요약 : 원형 큐(Circular Queue)]
1. 해결 과제: 선형 큐의 '거짓 오버플로우' 문제를 해결하여 메모리를 재사용합니다.
2. 핵심 로직: (Index + 1) % Size 모듈러 연산을 통해 인덱스를 순환시킵니다.
3. 구현 팁: 공백과 포화 상태를 명확히 구분하기 위해 보통 배열의 한 칸을 비워두는 방식을 사용합니다.

kguidebook0001 님의 블로그