AI Agent Developer 황화인 blog

큐

8 min read

큐 (Queue)

한마디 요약: “먼저 온 놈이 먼저 나간다(FIFO)” 규칙으로 데이터를 줄 세우는 자료구조. AI Agent에서는 비동기 작업 처리, 메시지 버퍼링, BFS 탐색의 뼈대다.

1. 큐가 뭔가

Queue(큐, 대기 줄): 데이터를 한쪽 끝에서 넣고(Enqueue, 뒤에 줄서기) 반대쪽 끝에서 꺼내는(Dequeue, 앞에서 빠져나가기) 자료구조. 영어 단어 그대로 “줄서기”다.

일상 비유: 은행 창구 대기표. 먼저 뽑은 사람이 먼저 호출되고, 나중에 온 사람은 뒤에 서서 기다린다. 새치기는 없다. 이 규칙을 FIFO(First-In-First-Out, 먼저 들어간 게 먼저 나옴) 라고 부른다.

포함 관계: 큐는 “선형 자료구조(Linear Data Structure)“의 한 종류. 형제로 Stack(스택, LIFO 방식) 이 있고, 사촌으로 Deque(덱, 양쪽 끝에서 모두 넣고 뺄 수 있는 양방향 큐) 가 있다. Deque은 큐와 스택의 기능을 둘 다 가진 확장판.

2. 스택과 큐 나란히 비교

관점Stack(스택)Queue(큐)
규칙LIFO(Last-In-First-Out)FIFO(First-In-First-Out)
일상 비유접시 쌓기(맨 위부터 꺼냄)은행 줄(앞에서 빠짐)
넣기 함수pushenqueue
꺼내기 함수popdequeue
대표 용도함수 호출, 실행 취소(undo), 괄호 매칭작업 대기열, 메시지 버퍼, 트리의 BFS 탐색
Python 구현list.append() / list.pop()collections.deque

핵심 차이는 “꺼내는 쪽이 어디냐”뿐이다. 같은 줄이지만 한쪽은 뒤에서 빼고, 한쪽은 앞에서 뺀다.

3. 큐의 동작 단계 분해

queue = [A] 상태에서 벌어지는 일:

1단계: enqueue(B) → 뒤에 붙여 [A, B] 2단계: enqueue(C) → 뒤에 붙여 [A, B, C] 3단계: dequeue() → 앞에서 A 빠짐, 반환값 A, 남은 큐 [B, C] 4단계: dequeue() → 앞에서 B 빠짐, 반환값 B, 남은 큐 [C]

들어간 순서(A→B→C) 그대로 나온다. 이게 FIFO.

4. Python에서 직접 확인

Python 리스트로도 큐를 흉내낼 수 있지만, list.pop(0)은 O(n)이라 느리다. 제대로 하려면 collections.deque를 쓴다.

from collections import deque
 
q = deque()
 
# 작업 추가 (O(1))
q.append("task_1")
q.append("task_2")
q.append("task_3")
 
print(q)  # deque(['task_1', 'task_2', 'task_3'])
 
# 앞에서 꺼내기 (O(1))
first = q.popleft()
print(first)  # 'task_1'
print(q)      # deque(['task_2', 'task_3'])
 
# 길이 확인 (O(1))
print(len(q))  # 2
 
# 비어있는지 확인
print(not q)   # False (아직 항목 있음)

왜 list.pop(0)은 O(n)이고 deque.popleft()는 O(1)인가? 리스트는 배열 기반이라 앞을 빼면 뒤 원소들을 전부 한 칸씩 당겨야 함. Deque은 양쪽 끝에 포인터가 있어 바로 끊어낼 수 있다. 상세는 시간복잡도_기초.

5. 큐의 변형들

5-1. Priority Queue(우선순위 큐, VIP 줄)

무엇: 들어간 순서가 아니라 “우선순위 숫자가 낮은(또는 높은) 것부터” 꺼내는 큐. 응급실 접수와 같다. 먼저 왔어도 경증이면 뒤로 밀린다.

구현: 보통 Heap(힙, 최솟값/최댓값이 꼭대기에 있는 완전 이진 트리) 으로 만든다. Python에서는 heapq 모듈 제공.

import heapq
 
pq = []
heapq.heappush(pq, (2, "중간 일"))
heapq.heappush(pq, (1, "급한 일"))
heapq.heappush(pq, (3, "나중에 할 일"))
 
print(heapq.heappop(pq))  # (1, '급한 일')  ← 우선순위 1이 제일 먼저
print(heapq.heappop(pq))  # (2, '중간 일')

5-2. Deque(덱, 양방향 큐)

앞뒤 어디서든 넣고 뺄 수 있는 큐. 큐 + 스택 기능 동시. 슬라이딩 윈도우 알고리즘에 자주 등장.

5-3. Circular Queue(원형 큐, 끝이 처음으로 이어지는 큐)

고정 크기 배열에서 끝에 도달하면 처음으로 돌아가 재활용. OS 스케줄러나 오디오 버퍼처럼 크기가 고정된 곳에서 씀.

6. AI Agent 개발에서 어디에 쓰이나

메시지 큐(Message Queue): 유저 요청이 몰릴 때, LLM 호출을 큐에 쌓아두고 워커가 하나씩 처리. Celery, RabbitMQ, Kafka가 이 패턴의 대규모 버전. “갑자기 1000명이 들어와도 터지지 않는” 비결.

Agent 작업 큐(Task Queue): Agent가 계획한 하위 태스크를 큐에 넣고 순서대로 실행. LangGraph의 상태 전이, ReAct 루프의 액션 큐가 여기에 해당.

BFS(Breadth-First Search, 너비 우선 탐색): 트리나 그래프를 “가까운 노드부터” 훑을 때 큐가 필수. 예: 지식 그래프에서 “2홉 이내 관련 문서 찾기”.

스트리밍 응답 버퍼: LLM이 토큰을 하나씩 뱉을 때, 클라이언트로 전송하기 전 잠깐 큐에 쌓아 배치 처리. 속도와 매끄러움의 타협.

Rate Limiter(요청 제한기): “초당 10개만 처리”를 지키기 위해 들어오는 요청을 큐에 담아 천천히 소화.

7. 왜 이렇게 만들었나 (설계 의도)

대안: 리스트에 그냥 append / pop(0) 쓰기 → 앞에서 빼는 게 O(n)이라 큐 크기가 커지면 급격히 느려짐.

큐의 트레이드오프:

  • 장점: 공평함(먼저 온 놈이 먼저 처리됨), 순서 보장, O(1) 삽입·삭제
  • 단점: 중간 원소 접근이 어려움(줄 중간을 건너뛰어 볼 수 없음), 탐색은 O(n)
  • 우선순위가 필요하면 Priority Queue로 업그레이드해야 함

핵심 교훈: 데이터 처리 순서가 공평해야 하거나, 작업을 비동기로 쌓아뒀다 꺼내 써야 할 때 큐를 고른다. 순서가 상관없으면 해시맵, 순서대로 훑어야 하면 리스트.

8. 관련 문서

Graph View

Backlinks