[자료구조 06] 큐, 먼저 넣은 걸 먼저 꺼내기

은행이나 매표소에 줄을 서면, 먼저 온 사람이 먼저 일을 봅니다. 뒤에 온 사람은 뒤에서 기다리다가 차례가 되어야 앞으로 나옵니다. 이렇게 먼저 넣은 것을 가장 먼저 꺼내는 방식으로 데이터를 다루는 자료구조를 큐(queue, 줄 서기)라고 합니다. 영어 첫 글자를 따서 선입선출(FIFO, First In First Out)이라고도 부릅니다. 스택이 한쪽 끝만 썼다면, 큐는 뒤로 넣고 앞으로 뺍니다. 파이썬에서 큐는 리스트가 아니라 collections 모듈의 deque(데크, 양쪽 끝을 다루는 줄)를 씁니다. 그 이유까지 차근차근 확인해 보겠습니다.

06.1 큐는 뒤로 넣고 앞으로 뺍니다

큐의 규칙도 단순합니다. 새 데이터는 항상 뒤(끝)에 붙이고, 꺼낼 때는 항상 앞(맨 처음)에서 뺍니다. 넣는 동작을 인큐(enqueue), 꺼내는 동작을 디큐(dequeue)라고 부릅니다.

파이썬 리스트로도 append로 뒤에 넣고 pop(0)으로 앞을 뺄 수는 있습니다. 그런데 앞에서 빼는 pop(0)이 아주 느립니다. 그래서 큐가 필요할 때는 deque를 씁니다. deque는 앞에서 빼는 popleft가 빠르도록 특별히 만들어진 도구입니다.

큐도 우리 주변에 흔합니다. 프린터에 여러 문서를 보내면 보낸 순서대로 인쇄되고, 고객센터 상담 대기도 먼저 건 사람이 먼저 연결됩니다. 게임 서버의 대기열, 메시지를 순서대로 처리하는 작업 큐도 모두 큐입니다. 공정하게 "온 순서대로" 처리해야 하는 상황이라면 큐가 정답입니다.

06.2 줄 세우고 앞에서부터 처리하기

손님을 줄 세운 뒤 앞에서부터 받아 보겠습니다. 먼저 deque를 불러와야 합니다.

from collections import deque
q = deque()
q.append("손님1")
q.append("손님2")
q.append("손님3")
print(list(q))
print(q.popleft())
print(list(q))

['손님1', '손님2', '손님3']
손님1
['손님2', '손님3']

append로 손님을 뒤에 차례로 세웠습니다. popleft는 맨 앞 값을 빼면서 그 값을 돌려줍니다. 이름 그대로 "왼쪽(앞)에서 꺼내기"입니다. 가장 먼저 온 손님1이 가장 먼저 처리되었고, 줄에는 손님2와 손님3만 남았습니다. list(q)로 감싼 이유는 deque를 보기 좋게 리스트 모양으로 출력하기 위해서입니다. deque를 그냥 출력하면 deque(['손님1', ...]) 같은 형태로 나오는데, 내용만 깔끔히 보려고 리스트로 바꾼 것입니다.

뒤에 넣는 append와 앞에서 빼는 popleft 모두 O(1)입니다. 줄이 아무리 길어도 끝과 앞 한 곳만 건드리므로 걸리는 시간이 일정합니다.

06.3 양쪽 끝을 자유롭게 다루는 deque

deque는 이름 그대로 양쪽 끝을 모두 다룰 수 있습니다. 뒤에 넣는 append, 앞에 넣는 appendleft가 함께 있습니다.

from collections import deque
dq = deque([2, 3])
dq.appendleft(1)
dq.append(4)
print(list(dq))

[1, 2, 3, 4]

[2, 3]으로 시작해 appendleft(1)로 앞에 1을, append(4)로 뒤에 4를 붙여 [1, 2, 3, 4]가 되었습니다. 앞이든 뒤든 넣고 빼는 동작이 모두 O(1)이라, deque 하나로 스택처럼도 큐처럼도 쓸 수 있습니다.

deque라는 이름은 양방향 큐(double-ended queue, 양쪽 끝에서 넣고 뺄 수 있는 큐)를 줄인 말입니다. 뒤에서 빼는 pop과 앞에서 빼는 popleft가 모두 있어, 어느 쪽 끝이든 자유롭게 다룹니다. 그래서 큐가 필요하면 append와 popleft를, 스택이 필요하면 append와 pop을 쓰면 됩니다. 하나의 도구로 두 자료구조를 모두 표현할 수 있는 셈입니다.

06.4 최근 N개만 남기기

deque에는 편리한 기능이 하나 더 있습니다. 만들 때 maxlen(최대 길이)을 정해 두면, 그 개수를 넘겨 새 값이 들어올 때 반대쪽의 오래된 값이 자동으로 밀려 나갑니다.

from collections import deque
recent = deque(maxlen=3)
for i in [1, 2, 3, 4, 5]:
recent.append(i)
print(list(recent))

[3, 4, 5]

최대 3개까지만 담기게 정했습니다. 1, 2, 3까지는 그대로 들어가지만 4가 들어올 때 가장 오래된 1이, 5가 들어올 때 2가 밀려 나가 최근 세 개인 3, 4, 5만 남았습니다. 직접 오래된 값을 지우는 코드를 쓰지 않아도 deque가 알아서 처리해 줍니다. 최근 접속 기록, 최근 검색어, 최근 알림처럼 "최신 몇 개만" 유지할 때 아주 유용합니다. 일정 구간만 옮겨 가며 살펴보는 슬라이딩 윈도우(sliding window, 창을 옆으로 밀며 보기) 문제에서도 자주 쓰입니다.

06.5 왜 리스트 대신 deque인가

앞에서 큐는 deque를 쓴다고 했습니다. 그 이유를 실제 시간으로 확인해 보겠습니다. 2만 개를 앞에서 빼는 데 리스트의 pop(0)과 deque의 popleft가 각각 얼마나 걸리는지 재 보겠습니다.

import timeit
from collections import deque
def q_list(n):
a = list(range(n))
while a:
a.pop(0)
def q_deque(n):
a = deque(range(n))
while a:
a.popleft()
n = 20000
print(round(timeit.timeit(lambda: q_list(n), number=1), 4), "초 (list.pop 0)")
print(round(timeit.timeit(lambda: q_deque(n), number=1), 4), "초 (deque.popleft)")

0.0453 초 (list.pop 0)
0.0013 초 (deque.popleft)

위 초 단위 수치는 컴퓨터 사정에 따라 달라지는 예시 값이지만, 차이의 방향은 늘 같습니다. deque가 리스트보다 약 수십 배 빠릅니다. 리스트의 pop(0)은 앞을 뺄 때마다 남은 값을 모두 한 칸씩 앞으로 당겨야 해서 O(n)이고, deque의 popleft는 앞을 바로 떼어 내 O(1)이기 때문입니다. 데이터가 2만 개가 아니라 수십만 개로 늘어나면 이 격차는 더 크게 벌어집니다. 리스트는 큐로 쓸수록 느려지지만 deque는 개수와 상관없이 일정하게 빠릅니다. 그래서 큐가 필요하면 리스트가 아니라 deque를 씁니다. 반대로 맨 끝만 다루는 스택이라면 리스트로도 충분히 빠릅니다. 어느 쪽 끝을 자주 건드리느냐가 도구 선택의 기준입니다.

06.6 정리

큐는 먼저 넣은 것을 먼저 꺼내는 선입선출 구조이고, 뒤로 넣고 앞으로 뺍니다. 파이썬에서는 앞에서 빼기가 느린 리스트 대신 collections.deque를 써서 append와 popleft를 각각 O(1)로 처리합니다. deque는 양쪽 끝을 모두 다루고 maxlen으로 최근 몇 개만 유지할 수도 있어 활용 폭이 넓습니다. 순서대로 들어온 일을 순서대로 처리해야 하는 상황이라면 큐를 떠올리시고, 앞에서 빼는 동작이 있다면 반드시 deque를 쓴다는 점을 기억하시기 바랍니다.