큐의 기본 원리

큐는 선형 데이터 구조 중 하나로, 삽입과 삭제가 양 끝에서 이루어지는 특성을 가집니다. 한쪽 끝(후단)에서 요소를 추가하고, 다른 쪽 끝(전단)에서 요소를 제거하는 방식을 따릅니다. 이는 선입선출(First In First Out, FIFO) 원칙에 기반하며, 가장 먼저 들어온 항목이 가장 먼저 처리되는 구조입니다.

이러한 특성 덕분에 큐는 작업 스케줄링, 메시지 전달, 버퍼링 등 다양한 시스템에서 활용됩니다.

큐의 구현 방법

큐는 배열 또는 연결 리스트로 구현할 수 있습니다.

배열 기반 큐 (순차 큐)

배열을 사용하면 두 개의 인덱스 포인터를 통해 전단과 후단을 관리합니다. 후단 포인터는 다음 삽입 위치를 가리키며, 전단 포인터는 현재 첫 번째 요소를 가리킵니다. 하지만 일반적인 순차 큐는 공간 낭비 문제가 발생할 수 있으며, 용량 초과 시 재할당이 필요합니다.

원형 큐 (Circular Queue)

이 문제를 해결하기 위해 원형 큐가 도입되었습니다. 배열의 끝이 시작점과 연결되어 순환 구조를 형성하여, 전체 저장 공간을 효율적으로 활용할 수 있습니다.

연결 리스트 기반 큐 (링크드 큐)

노드 기반의 연결 리스트를 사용하면 동적 크기 조절이 가능하며, 삽입/삭제 연산의 시간 복잡도는 O(1)입니다. 전단 포인터는 헤드 노드를, 후단 포인터는 테일 노드를 유지합니다.

기본 큐 클래스 구현

class SimpleQueue:
    def __init__(self):
        self._data = []

    def enqueue(self, value):
        self._data.append(value)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("큐가 비어 있습니다")
        return self._data.pop(0)

    def is_empty(self):
        return len(self._data) == 0

    def size(self):
        return len(self._data)

양방향 큐 (Deque) 구현

양방향 큐는 전단과 후단 모두에서 삽입 및 삭제가 가능한 큐입니다. 이를 통해 스택과 큐의 특성을 동시에 제공합니다.

class Deque:
    def __init__(self):
        self._items = []

    def add_front(self, item):
        self._items.insert(0, item)

    def add_rear(self, item):
        self._items.append(item)

    def remove_front(self):
        return self._items.pop(0)

    def remove_rear(self):
        return self._items.pop()

    def is_empty(self):
        return len(self._items) == 0

    def size(self):
        return len(self._items)

우선순위 큐 (Priority Queue)

우선순위 큐는 각 요소에 우선순위를 부여하여, 가장 높은 우선순위의 항목부터 처리됩니다. 동일한 우선순위인 경우 삽입 순서에 따라 처리됩니다.

이 구조는 힙(최소 힙 또는 최대 힙)으로 구현되며, 파이썬의 heapq 모듈을 활용하면 간편하게 구현할 수 있습니다.

import heapq

class PriorityQueue:
    def __init__(self):
        self._heap = []
        self._counter = 0

    def push(self, item, priority):
        heapq.heappush(self._heap, (priority, self._counter, item))
        self._counter += 1

    def pop(self):
        if not self._heap:
            raise IndexError("우선순위 큐가 비어 있습니다")
        _, _, item = heapq.heappop(self._heap)
        return item

    def is_empty(self):
        return len(self._heap) == 0

파이썬 내장 큐 모듈 사용

파이썬의 queue 모듈은 멀티스레드 환경에서도 안전하게 사용할 수 있는 다양한 큐를 제공합니다.

FIFO 큐 (순서 기반 큐)

import queue

q = queue.Queue()
q.put("task1")
q.put("task2")
q.put("task3")

print(q.get())  # task1
print(q.get())  # task2
print(q.get())  # task3

LIFO 큐 (스택처럼 동작)

import queue

stack_q = queue.LifoQueue()
stack_q.put("A")
stack_q.put("B")
stack_q.put("C")

print(stack_q.get())  # C
print(stack_q.get())  # B
print(stack_q.get())  # A

우선순위 큐 (정렬 기반)

import queue

pq = queue.PriorityQueue()
pq.put((3, "high"))
pq.put((1, "low"))
pq.put((2, "medium"))

print(pq.get())  # (1, 'low')
print(pq.get())  # (2, 'medium')
print(pq.get())  # (3, 'high')

모든 큐는 내부적으로 락을 사용해 동시성 문제를 방지하며, 다중 스레드 환경에서 신뢰성 있게 작동합니다.