Python의 대기열 구현

큐는 항목을 선입선출(FIFO) 순서로 저장합니다. 새 항목은 뒤에 넣고, 앞에 있는 항목부터 꺼냅니다. Python에서는 이 동작을 여러 방식으로 구현할 수 있습니다. 이 가이드에서는 리스트와 연결 리스트로 큐를 구현한 다음, 표준 라이브러리의 collections.deque를 사용하는 방법을 살펴봅니다.

큐 동작 방식과 기본 연산

앞은 다음에 나갈 항목이 있는 곳이고, 뒤는 새 항목이 들어오는 곳입니다. 예를 들어 큐에 1, 2, 3이 있으면 1이 앞에, 3이 뒤에 있습니다. 4를 넣으면 큐는 1, 2, 3, 4가 됩니다. 한 번 꺼내면 1이 반환되고 2, 3, 4가 남습니다.

다음은 뒤에 항목을 넣고 앞에서 꺼내는 간단한 실행 코드입니다. 제공된 패킷에는 이 코드 조각의 실행 결과가 없으므로, 출력 결과를 제시하지 않습니다.

이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.

queue = []
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)
removed = queue.pop(0)
print(removed)
print(queue)

유용한 큐 인터페이스에는 네 가지 연산이 있습니다. enqueue는 항목을 추가하고, dequeue는 앞의 항목을 꺼내 반환합니다. 비어 있는지 확인하는 연산은 항목이 남아 있는지 알려 주고, 길이 연산은 항목 수를 알려 줍니다. 아래 구현은 빈 큐에서 dequeue를 호출하면 (False, None)을 반환하고, 성공하면 (True, item)을 반환합니다. 성공 여부를 별도로 반환하면 실제 항목인 None과 큐가 비어 있는 경우를 구분할 수 있습니다.

Python 리스트로 큐 구현하기

리스트는 간결한 학습용 예제를 만드는 데 적합합니다. 항목은 리스트 끝에 추가하고, 첫 항목은 pop(0)으로 제거합니다. 코드가 단순하다는 장점이 있지만, 앞 항목을 제거할 때 나머지 항목이 이동하므로 큐가 커질수록 dequeue에 선형 시간이 걸립니다. 이 예제는 None을 포함한 모든 Python 객체를 지원합니다.

다음 예제를 실행해 보세요.

이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.

class ListQueue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.items:
            return False, None
        return True, self.items.pop(0)

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

    def __len__(self):
        return len(self.items)


queue = ListQueue()
queue.enqueue("first")
queue.enqueue("second")
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())

헤드 인덱스를 사용하는 리스트는 항목을 제거할 때마다 나머지를 이동하는 일을 피할 수 있지만, 리스트를 압축할 때까지 제거된 항목을 보관합니다. 이 방식에는 논리적인 큐 위치와 리스트 인덱스를 대응시키고, 저장 공간을 안전하게 초기화하거나 압축하기 위한 추가 관리가 필요합니다. 일반적인 FIFO 용도에는 collections.deque가 대체로 더 명확한 선택입니다.

연결 리스트로 큐 구현하기

단일 연결 큐는 각 항목을 노드에 저장하며, 노드의 next 참조는 뒤쪽을 향합니다. 앞과 뒤 양쪽의 참조를 유지하세요. enqueue는 rear 뒤에 새 노드를 연결하고, dequeue는 front를 다음 노드로 옮깁니다. 마지막 노드가 빠져나가면 rear도 비워야 합니다. 그러지 않으면 다음 enqueue에서 더 이상 유효하지 않은 노드에 항목을 연결하려 할 수 있습니다. 이 구현에서 enqueue와 dequeue는 상수 시간이 걸리고, 길이를 구할 때는 노드를 세므로 선형 시간이 걸립니다.

이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class LinkedQueue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, item):
        node = Node(item)
        if self.rear is None:
            self.front = self.rear = node
        else:
            self.rear.next = node
            self.rear = node

    def dequeue(self):
        if self.front is None:
            return False, None
        item = self.front.value
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return True, item

    def is_empty(self):
        return self.front is None

    def __len__(self):
        count = 0
        current = self.front
        while current is not None:
            count += 1
            current = current.next
        return count


queue = LinkedQueue()
queue.enqueue(10)
queue.enqueue(20)
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())

불변 조건은 큐가 비어 있을 때에만 두 참조가 모두 None이라는 것입니다. 큐에 항목이 있으면 front는 다음에 제거할 항목을 가리키고 rear.next는 None입니다. 이 조건을 유지하면 항목이 하나만 남은 경우와 큐가 비워진 뒤 다시 사용하는 경우를 모두 처리할 수 있습니다.

큐에 collections.deque 사용하기

일반적인 FIFO 작업에는 Python의 collections.deque가 실용적인 기본 선택입니다. 오른쪽 끝에 추가하고 popleft()로 왼쪽 끝에서 제거합니다. 양 끝 연산 모두 효율적으로 수행되도록 설계되어 있으며, len()과 참·거짓 확인을 사용하면 나머지 인터페이스도 간결하게 만들 수 있습니다. 빈 deque에서 popleft()를 호출하면 IndexError가 발생하므로, 이 래퍼는 먼저 큐가 비었는지 확인하고 다른 예제와 같은 성공 여부 값을 반환합니다.

이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.

from collections import deque


class DequeQueue:
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.items:
            return False, None
        return True, self.items.popleft()

    def is_empty(self):
        return not self.items

    def __len__(self):
        return len(self.items)


queue = DequeQueue()
queue.enqueue("first")
queue.enqueue("second")
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())

deque는 collections 모듈이 제공하는 클래스입니다. 여기서는 공개 인터페이스만 사용하면 됩니다. 내부 표현에 관한 가정에 의존하지 마세요. 용량을 제한하거나 생산자 스레드와 소비자 스레드 사이의 조정이 필요하다면, Python의 queue 모듈에 있는 용도별 큐 클래스를 고려하세요.

구현 방식 비교

연결 리스트의 시간 비용은 큐가 front와 rear를 모두 저장한다고 가정합니다. 길이 정보를 따로 저장하지 않으므로 길이를 셀 때는 각 노드를 방문해야 합니다. 별도 카운터를 두면 길이를 상수 시간에 구할 수 있지만, 모든 연산에서 갱신해야 하는 불변 조건이 하나 더 생깁니다. 대부분의 프로그램에서는 collections.deque를 선택하세요. 큐가 아주 작거나 앞에서 항목을 반복해 제거하지 않는다면 리스트를 사용하고, 자료 구조를 학습하거나 노드 단위의 동작이 특별히 필요한 경우에는 연결 리스트를 구현해 보세요.