💻
프로그래밍
큐
Queue
FIFO(선입선출) 자료구조. 작업 스케줄링, BFS에 사용. 메시지 큐의 기반 개념.
📖 상세 설명
큐(Queue)는 FIFO(First In, First Out, 선입선출) 원칙을 따르는 자료구조입니다. 먼저 들어온 데이터가 먼저 나가는 구조로, 줄을 서서 기다리는 것과 같은 방식으로 동작합니다. enqueue(삽입)와 dequeue(제거) 두 가지 핵심 연산을 제공합니다.
큐는 다양한 곳에서 활용됩니다. 운영체제의 프로세스 스케줄링, 프린터 작업 대기열, 네트워크 패킷 처리, 그래프의 BFS(너비 우선 탐색) 알고리즘 등에서 필수적으로 사용됩니다. 웹 개발에서는 작업 큐, 메시지 큐 시스템의 기반 개념이기도 합니다.
큐의 변형으로 덱(Deque, 양방향 큐), 우선순위 큐(Priority Queue), 원형 큐(Circular Queue) 등이 있습니다. 우선순위 큐는 삽입 순서가 아닌 우선순위에 따라 요소를 제거하며, 힙(Heap)으로 구현됩니다. 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능합니다.
분산 시스템에서 메시지 큐(RabbitMQ, Apache Kafka, Amazon SQS 등)는 서비스 간 비동기 통신의 핵심입니다. 생산자가 메시지를 큐에 넣고 소비자가 처리하는 패턴으로, 서비스 간 결합도를 낮추고 확장성을 높입니다.
💻 코드 예제
# Python 큐 구현 및 활용
from collections import deque
import queue
# 1. deque로 큐 구현 (권장)
q = deque()
q.append(1) # enqueue
q.append(2)
q.append(3)
first = q.popleft() # dequeue -> 1
print(list(q)) # [2, 3]
# 2. queue.Queue (스레드 안전)
thread_safe_q = queue.Queue()
thread_safe_q.put('task1')
thread_safe_q.put('task2')
task = thread_safe_q.get() # 'task1'
# 3. 우선순위 큐
import heapq
pq = []
heapq.heappush(pq, (2, 'medium'))
heapq.heappush(pq, (1, 'high'))
heapq.heappush(pq, (3, 'low'))
print(heapq.heappop(pq)) # (1, 'high')
# 4. BFS에서 큐 활용
def bfs(graph, start):
visited = set()
queue = deque([start])
result = []
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
result.append(node)
queue.extend(graph[node])
return result
# 그래프 예시
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [], 'E': [], 'F': []
}
print(bfs(graph, 'A')) # ['A', 'B', 'C', 'D', 'E', 'F']🗣️ 실무 대화 예시
시니어: 이메일 발송이 동기로 되어 있어서 응답이 느려요. 메시지 큐로 분리합시다.
주니어: 어떤 큐 시스템을 쓸까요?
시니어: 규모가 작으니까 Redis Queue부터 시작하고, 나중에 필요하면 RabbitMQ로 넘어가죠. 일단 이메일 전송을 워커가 처리하게 분리하는 게 먼저예요.
면접관: 스택과 큐의 차이점을 설명해주세요.
지원자: 스택은 LIFO로 마지막에 들어온 것이 먼저 나가고, 큐는 FIFO로 먼저 들어온 것이 먼저 나갑니다. 스택은 함수 호출, 실행 취소에 사용되고, 큐는 작업 스케줄링, BFS 탐색에 사용됩니다.
면접관: BFS에서 왜 큐를 사용하나요?
지원자: 같은 레벨의 노드를 먼저 방문해야 하기 때문입니다. 큐에 인접 노드를 넣고 순서대로 꺼내면 자연스럽게 레벨 순서로 탐색됩니다.
리뷰어: 리스트로 큐를 구현했는데, pop(0)은 O(n)이에요.
작성자: 데이터가 적어서 괜찮지 않을까요?
리뷰어: deque를 쓰면 popleft()가 O(1)이에요. 습관적으로 효율적인 자료구조를 선택하는 게 좋아요.
⚠️ 주의사항
- 리스트로 큐 구현 금지: Python에서 list.pop(0)은 O(n)입니다. collections.deque를 사용하세요.
- 큐 오버플로우: 크기가 제한된 큐에서 계속 삽입하면 오버플로우가 발생합니다. 최대 크기와 대응 전략을 설계하세요.
- 메시지 유실: 메시지 큐 시스템에서 소비자가 처리 중 실패하면 메시지가 유실될 수 있습니다. ACK 메커니즘을 활용하세요.