큐(Queue)란 무엇인가?
큐는 선입선출(FIFO, First In First Out) 방식으로 동작하는 선형 자료구조입니다. 이름 그대로 큐에 가장 먼저 들어온 요소가 가장 먼저 처리되며, 이후 요소들은 도착한 순서대로 차례차례 처리됩니다.
일상 속 예시로 이해하기
큐 자료구조는 버스 정류장의 줄을 떠올리면 쉽게 이해할 수 있습니다. 버스 정류장에 가장 먼저 도착한 사람이 줄의 맨 앞에 서고, 이후 도착하는 사람들은 차례대로 그 뒤에 줄을 섭니다. 버스가 도착하면 가장 먼저 도착했던 사람이 제일 먼저 버스에 탑승하고, 나머지 사람들도 자신이 도착한 순서대로 탑승하게 됩니다. 이것이 바로 선입선출(FIFO) 방식입니다.
파이썬에서 큐 구현하기
파이썬에서는 리스트(list)와 같은 기본 자료구조를 활용하거나, 표준 라이브러리에서 제공하는 내장 모듈을 사용해 다양한 방식으로 큐를 구현할 수 있습니다. 대표적인 세 가지 방법을 살펴보겠습니다.
방법 1 — 리스트(list)로 구현
리스트를 이용하면 간단히 큐를 만들 수 있습니다. 다만 리스트의 맨 앞에서 요소를 삽입하거나 삭제하는 작업은 O(n) 시간이 걸리기 때문에, 다른 방법에 비해 성능이 떨어진다는 점을 유의해야 합니다.
주요 연산
append() — 큐의 끝에 새로운 요소를 추가합니다.
pop(0) — 큐의 첫 번째 요소를 제거하고 반환합니다.
예제
queue = []
queue.append(1)
queue.append(2)
queue.append(3)
print("초기 큐", queue)
print("큐에서 꺼낸 요소")
print(queue.pop(0))
print(queue.pop(0))
print("요소를 꺼낸 후의 큐", queue)실행 결과
초기 큐 [1, 2, 3] 큐에서 꺼낸 요소 1 2 요소를 꺼낸 후의 큐 [3]
주의할 점은 빈 큐에서 더 이상 요소를 제거하려고 하면 예외가 발생한다는 것입니다.
queue.pop(0) IndexError: pop from empty list
방법 2 — queue.Queue 모듈로 구현
파이썬 내장 모듈인 queue의 Queue 클래스를 사용하면 스레드 환경에서도 안전하게 동작하는 큐를 구현할 수 있습니다. 큐 생성 시 최대 크기를 지정할 수 있으며, 크기를 0으로 설정하면 무제한 큐가 됩니다.
주요 연산
maxsize — 큐에 저장할 수 있는 최대 요소 수
get() — 큐의 첫 번째 요소를 제거하고 반환합니다. 큐가 비어 있다면 요소가 하나라도 생길 때까지 대기합니다.
get_nowait() — 큐의 첫 번째 요소를 제거하고 반환합니다. 큐가 비어 있다면 예외를 발생시킵니다.
put(item) — 큐의 끝에 요소를 추가합니다. 큐가 가득 차 있다면 빈 공간이 생길 때까지 대기합니다.
put_nowait(item) — 큐의 끝에 요소를 추가합니다. 큐가 가득 차 있다면 예외를 발생시킵니다.
full() — 큐가 가득 찼으면 True, 아니면 False를 반환합니다.
empty() — 큐가 비어 있으면 True, 아니면 False를 반환합니다.
qsize() — 큐에 현재 들어 있는 요소의 개수를 반환합니다.
예제
from queue import Queue
q = Queue(maxsize=3)
q.put(1)
q.put(2)
q.put(3)
print("큐가 가득 찼나요?", q.full())
print("큐에서 꺼낸 요소")
print(q.get())
print(q.get())
print("큐에 남은 요소 개수", q.qsize())
print("큐가 비었나요?", q.empty())실행 결과
큐가 가득 찼나요? True 큐에서 꺼낸 요소 1 2 큐에 남은 요소 개수 1 큐가 비었나요? False
방법 3 — collections.deque로 구현
큐를 구현하는 또 다른 방법은 collections 모듈의 deque(덱, Double-Ended Queue)를 사용하는 것입니다. deque는 양방향에서 빠른 삽입과 삭제를 지원하므로, 실무에서 가장 널리 권장되는 방식입니다.
주요 연산
append() — 큐의 끝에 새로운 요소를 추가합니다.
popleft() — 큐의 첫 번째 요소를 제거하고 반환하며, O(1)의 시간 복잡도로 매우 빠르게 동작합니다.
예제
from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
print("초기 큐:", queue)
print("큐에서 꺼낸 요소")
print(queue.popleft())
print(queue.popleft())
print("요소를 꺼낸 후의 큐:", queue)실행 결과
초기 큐: deque([1, 2, 3]) 큐에서 꺼낸 요소 1 2 요소를 꺼낸 후의 큐: deque([3])
빈 deque에 대해 popleft()를 호출하면 IndexError 예외가 발생하므로, 사용 전에 큐가 비어 있는지 확인하는 것이 좋습니다.
마치며
정리하면, 간단한 학습용으로는 리스트를, 멀티스레딩 환경이라면 queue.Queue, 일반적인 상황에서 최고의 성능이 필요하다면 collections.deque를 사용하는 것이 좋습니다. 각 방법의 시간 복잡도와 특성을 고려해 상황에 맞는 구현 방식을 선택하세요.