[실용적인 자료구조] 리스트 상속 원형 큐(Circular Queue) 자료구조

파이썬에서 리스트를 상속하여 원형 큐(Circular Queue)를 구현하면, 파이썬 리스트의 기본 기능을 활용하면서 원형 큐의 동작 원리를 추가할 수 있습니다. 이를 통해 리스트의 크기를 고정하고, 끝에 도달하면 다시 처음으로 돌아가는 원형 큐의 특성을 구현할 수 있습니다.

원형 큐의 주요 개념:

1. 크기 제한: 큐의 크기는 고정됩니다. 큐가 가득 차면 더 이상 요소를 추가할 수 없습니다.
2. 순환 구조: rear 포인터가 끝에 도달하면 다시 리스트의 처음으로 이동해 새로운 값을 저장할 수 있습니다.
3. FIFO: 먼저 들어간 데이터가 먼저 나오는 구조로 동작합니다.

파이썬 리스트 상속을 통한 원형 큐 구현

class CircularQueue(list):
    def __init__(self, size):
        """
        고정된 크기의 원형 큐를 초기화
        size: 큐의 최대 크기
        """
        super().__init__([None] * size)  # 고정된 크기의 리스트 생성
        self.size = size  # 큐의 크기
        self.front = -1  # 첫 번째 요소 인덱스
        self.rear = -1   # 마지막 요소 인덱스

    def is_empty(self):
        """큐가 비어 있는지 확인"""
        return self.front == -1

    def is_full(self):
        """큐가 꽉 찼는지 확인"""
        return (self.rear + 1) % self.size == self.front

    def enqueue(self, value):
        """
        큐에 요소 추가
        큐가 꽉 찼으면 OverflowError 발생
        """
        if self.is_full():
            raise OverflowError("Circular Queue is full")

        if self.is_empty():
            self.front = 0  # 첫 번째 요소 추가 시 front를 0으로 설정

        self.rear = (self.rear + 1) % self.size  # rear를 순환시킴
        self[self.rear] = value  # 큐에 요소 추가
        print(f"Enqueued {value} at position {self.rear}")

    def dequeue(self):
        """
        큐에서 요소 제거 후 반환
        큐가 비어 있으면 IndexError 발생
        """
        if self.is_empty():
            raise IndexError("Circular Queue is empty")

        value = self[self.front]
        self[self.front] = None  # 큐에서 요소 제거

        if self.front == self.rear:
            # 큐가 비면 front와 rear를 초기화
            self.front = -1
            self.rear = -1
        else:
            # front 포인터를 순환시킴
            self.front = (self.front + 1) % self.size

        print(f"Dequeued {value} from position {self.front}")
        return value

    def peek(self):
        """
        큐의 첫 번째 요소를 반환
        큐가 비어 있으면 IndexError 발생
        """
        if self.is_empty():
            raise IndexError("Circular Queue is empty")
        return self[self.front]

    def __repr__(self):
        """큐의 현재 상태를 문자열로 표현"""
        return f"CircularQueue({list(self)})"


# 원형 큐 사용 예제
cq = CircularQueue(5)

# 큐에 요소 추가
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.enqueue(40)

print(cq)  # 출력: CircularQueue([10, 20, 30, 40, None])

# 큐에서 요소 제거
cq.dequeue()  # 10 제거
cq.dequeue()  # 20 제거

print(cq)  # 출력: CircularQueue([None, None, 30, 40, None])

# 다시 요소 추가
cq.enqueue(50)
cq.enqueue(60)

print(cq)  # 출력: CircularQueue([60, None, 30, 40, 50])

# 큐가 꽉 차는 상황
try:
    cq.enqueue(70)  # 큐가 가득 찼으므로 오류 발생
except OverflowError as e:
    print(e)  # 출력: Circular Queue is full

# 큐에서 첫 번째 요소 확인 (peek)
print(f"Front of queue: {cq.peek()}")  # 출력: Front of queue: 30

설명

1. 리스트 상속: CircularQueue 클래스는 파이썬의 기본 list를 상속받아 고정된 크기의 큐를 관리합니다.
2. 큐 초기화: __init__에서 큐의 크기를 지정하고 고정된 크기의 리스트를 생성합니다. 리스트를 초기화할 때는 None 값으로 채워둡니다.
3. 포인터 관리:
   • front와 rear는 큐의 첫 번째와 마지막 요소를 가리키는 포인터입니다.
   • enqueue에서는 rear 포인터가 리스트의 끝에 도달하면 처음으로 돌아가고, dequeue에서는 front 포인터가 리스트의 끝에 도달하면 순환합니다.
4. 빈 큐 및 꽉 찬 큐 확인:
   • is_empty()는 front가 -1이면 큐가 비어 있다고 판단합니다.
   • is_full()는 (rear + 1) % size == front 조건을 통해 큐가 꽉 찬 상태임을 확인합니다.
5. 추가/삭제 연산:
   • enqueue는 큐가 가득 차면 OverflowError를 발생시키고, 그렇지 않으면 요소를 추가합니다.
   • dequeue는 큐가 비어 있을 때 IndexError를 발생시키고, 그렇지 않으면 요소를 제거하고 반환합니다.
6. 상태 출력: __repr__()는 큐의 현재 상태를 출력하여 디버깅을 쉽게 할 수 있습니다.

장점

• 리스트의 기본 기능 활용: 파이썬 리스트의 동적 배열 관리 기능을 상속받아 사용하기 때문에, 추가적인 배열 동작을 구현할 필요가 없습니다.
• 원형 구조: 리스트 끝에 도달했을 때 다시 처음으로 돌아가는 원형 구조가 구현되어 메모리 효율성이 높아집니다.

이러한 원형 큐는 제한된 크기의 데이터 구조에서 효율적으로 데이터를 관리하고, 메모리를 고정된 크기로 사용해야 하는 상황에서 유용합니다.