[WEEK02] 원형 큐, 우선순위 큐

원형 큐 (Circular Queue)

원형 큐 (또는 링 버퍼)는 배열 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조이다. 디큐할 때 배열 안의 원소를 옮기지 않는 큐를 구현할 때 사용된다.

프런트와 리어는 실제 물리적 원소의 순서가 아니라 논리적인 데이터 순서를 의미한다.

• 프런트 (front) : 맨 앞의 원소의 인덱스
• 리어 (rear) : 맨 끝 원소 바로 뒤의 인덱스(다음 인큐되는 데이터가 저장되는 위치)

원형 큐는 기존의 큐와 마찬가지로 FIFO 구조를 지니지만, 마지막 데이터의 위치가 첫번째 데이터의 위치와 연결되어 있다는 점에서 차이가 있다.

 

기존의 큐는 공간이 꽉 차게 되면 더이상 요소를 추가할 수가 없다. dequeue로 앞쪽 요소가 빠져나가 공간이 생겨도 그쪽으로는 추가할 수가 없다. 그래서 앞쪽에 공간이 남아있다면 아래 그림처럼 동그랗게 연결해 앞쪽으로 추가할 수 있도록 재활용 가능한 구조가 바로 원형 큐다.

 

enqueue하여 요소를 삭제할 자리, dequeue하여 요소를 추가할 자리를 따로 저장한다. enqueue()를 하게 되면 rear 포인터가 앞으로 이동하고, dequeue()를 하게 되면 front포인터가 앞으로 이동한다. 이렇게 enqueue와 dequeue를 반복하게 되면 서로 둥글게 연결되어 있기 때문에 두 개의 포인터가 빙글빙글 돌면서 이동하는 구조가 된다.

만약 (처음을 제외하고) rear와 front가 같은 위치를 가르키게 된다면, 여유공간이 없는 상황으로 공간 부족 에러를 발생시킨다.

class CircularQueue:
    def __init__(self, size):
        self.size = size
        self.queue = [None] * size
        self.front = self.rear = -1

    def is_full(self):
        return (self.rear + 1) % self.size == self.front

    def is_empty(self):
        return self.front == -1

    def enqueue(self, value):
        if self.is_full():
            print("큐가 가득 찼습니다.")
            return

        if self.is_empty():
            self.front = self.rear = 0
        else:
            self.rear = (self.rear + 1) % self.size

        self.queue[self.rear] = value
        print(f"{value}가 큐에 추가되었습니다.")

    def dequeue(self):
        if self.is_empty():
            print("큐가 비어 있습니다.")
            return None

        removed_value = self.queue[self.front]
        if self.front == self.rear:  # 큐가 하나의 요소만 남았을 때
            self.front = self.rear = -1
        else:
            self.front = (self.front + 1) % self.size

        print(f"{removed_value}가 큐에서 제거되었습니다.")
        return removed_value

    def peek(self):
        if self.is_empty():
            print("큐가 비어 있습니다.")
            return None
        return self.queue[self.front]

    def display(self):
        if self.is_empty():
            print("큐가 비어 있습니다.")
            return

        idx = self.front
        print("큐의 요소들:")
        while True:
            print(self.queue[idx], end=' ')
            if idx == self.rear:
                break
            idx = (idx + 1) % self.size
        print()

# 사용 예시
cq = CircularQueue(5)
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.display()  # 큐 상태 출력
cq.dequeue()
cq.display()  # 큐 상태 출력
cq.enqueue(40)
cq.enqueue(50)
cq.enqueue(60)  # 큐가 가득 찼을 때
cq.display()  # 큐 상태 출력

---

우선순위 큐 (Priority Queue)

우선순위 큐는 각 요소가 우선순위를 가지며, 높은 우선순위를 가진 요소가 먼저 처리되는 자료구조다. 일반적인 큐(FIFO)와 달리, 우선순위에 따라 요소가 정렬되어 처리된다. 운영체제의 작업 스케줄링, 네트워크 패킷 처리 등 다양한 분야에서 사용된다.

 

우선순위 큐는 주로 힙(Heap) 자료구조를 사용하여 구현되며, Python에서는 heapq 모듈을 활용할 수 있다.

import heapq

class PriorityQueue:
    def __init__(self):
        self.queue = []
    
    def push(self, item, priority):
        heapq.heappush(self.queue, (priority, item))
    
    def pop(self):
        return heapq.heappop(self.queue)[1]
    
    def is_empty(self):
        return len(self.queue) == 0

# 사용 예시
pq = PriorityQueue()
pq.push("task1", 2)
pq.push("task2", 1)
pq.push("task3", 3)
while not pq.is_empty():
    print(pq.pop())  # task2 -> task1 -> task3