Python의 큐(queue) 자료 구조
이 레슨에서는 collections.deque로 먼저 들어온 것이 먼저 나가는 효율적인 큐를 구현합니다.
소개
어떤 문제를 해결하나요
인쇄 작업, 고객 문의, 프로그램끼리 주고받는 메시지는 도착한 순서대로 처리해야 합니다. 큐는 그 순서를 지켜 줍니다. Python에서는 큐에 알맞은 도구를 고르면 항목이 수백만 개여도 빠르게 동작합니다.
일상 속 비유
큐는 매표소 앞에 선 줄과 같습니다. 새로 온 사람은 맨 뒤에 서고, 맨 앞에 선 사람부터 표를 삽니다. 아무도 새치기를 하지 않으므로 모두 도착한 순서대로 차례가 옵니다.
deque(["first", "second"])🚶🚶 이미 기다리고 있는 두 사람queue.append("third")🚶 새로 온 사람이 맨 뒤에 서기queue.popleft()🎫 맨 앞 사람이 표를 삼list(queue)👀 아직 기다리고 있는 사람들큐는 선입선출(FIFO, 먼저 넣은 것이 먼저 나옴) 방식의 컬렉션입니다. 항목은 뒤에 넣고 앞에서 꺼냅니다.
핵심 포인트
deque(["first", "second"])는 항목 두 개가 이미 들어 있는 큐를 만듭니다.queue.append("third")는 맨 뒤에 항목을 넣습니다.queue.popleft()는 맨 앞 항목을 꺼내서 돌려줍니다. 여기서는"first"입니다.deque는 맨 앞 항목을 빠르게 꺼냅니다. 리스트라면 남은 항목을 전부 한 칸씩 당겨야 합니다.
언제 사용하나요?
- 작업이나 요청을 도착한 순서대로 처리할 때.
- 그래프와 격자에서 하는 너비 우선 탐색.
- 메시지나 이벤트처럼, 만드는 쪽(생산자)과 가져다 쓰는 쪽(소비자) 사이에 두는 버퍼.
필요 없는 경우
- 가장 최근 항목이 먼저 나와야 하는 경우: 스택을 씁니다.
- 항목마다 우선순위가 있는 경우:
heapq로 우선순위 큐를 만듭니다. - 여러 스레드가 큐 하나를 함께 쓰는 경우:
queue.Queue가 잠금을 알아서 처리해 줍니다.
동작 원리 보기
enqueue와 dequeue를 해 보면 항목이 들어온 순서대로 나간다는 것을 알 수 있습니다.
예제 코드
from collections import deque
queue = deque(["first", "second"])
queue.append("third")
print("served:", queue.popleft())
print("waiting:", list(queue))
실행 결과
served: first
waiting: ['second', 'third']
코드 설명
deque는 append()로 오른쪽에 요소를 넣고 popleft()로 왼쪽에서 꺼낼 수 있으며, 둘 다 O(1)입니다. 일반 리스트에서 첫 요소를 지우면 뒤의 요소를 모두 앞으로 옮겨야 해서 O(n)이 걸리므로, 큐에는 deque가 알맞습니다.
값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.
연습 문제
아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.
- 빈 리스트, 요소가 하나인 리스트, 중복이 있는 리스트로 테스트해 보세요.
- 단계마다 상태를 출력해서 알고리즘이 동작하는 모습을 살펴보세요.
- 요소 100개, 1,000개, 10,000개로 실행 시간을 재고 다른 방법과 비교해 보세요.
자주 하는 실수
리스트와 pop(0) 쓰기
pop(0)은 남은 항목을 전부 한 칸씩 당기므로, 큐가 길어지면 느려집니다.
queue = ["first", "second"]
queue.pop(0)
queue = deque(["first", "second"])
queue.popleft()
이 레슨을 마쳤나요?
학습 완료로 표시하면 진행 상황을 기록할 수 있습니다.
챌린지로 연습하기
이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.
- Course Schedule Order Order courses so every prerequisite comes first. 어려움
- Can We Split Into Two Teams? Decide whether people can be assigned to two teams so that each listed pair is on opposite teams. 보통