큐

큐는 들어온 순서대로 하나씩 꺼내는 줄입니다. 가장 먼저 들어온 것이 가장 먼저 나가고, 뒤에 온 것은 자기 차례가 올 때까지 기다립니다. 한꺼번에 다 처리하지 못할 만큼 일이 몰릴 때, 그 일들을 순서를 지키며 쌓아 두는 데 씁니다.

상세

이 절은 큐를 앞과 뒤라는 두 지점으로 따라갑니다. 먼저 항목이 어디로 들어오고 어디로 나가는지 보고, 그다음 이 순서가 시스템에서 왜 중요한지, 실제로 무엇으로 만드는지를 봅니다.

앞과 뒤로 나뉜 두 끝

큐는 항목을 넣는 끝과 꺼내는 끝이 서로 다릅니다. 항목을 넣는 끝(위 「쉽고 빠른 이해」에서 '뒤'라 부른 곳)을 꼬리(tail)라 하고, 꺼내는 끝('앞')을 머리(head)라고 부릅니다. 새 항목은 언제나 꼬리에 붙고, 꺼낼 항목은 언제나 머리에서 나갑니다.

들어온 순서를 그대로 지켜 꺼내는 이 규칙을 FIFO(First In First Out, 먼저 들어온 것이 먼저 나간다)라고 부릅니다.

큐에 항목을 넣는 동작은 인큐(enqueue)라고 부릅니다. 큐에서 항목을 꺼내는 동작은 디큐(dequeue)라고 부릅니다.

머리와 꼬리가 갈라져 있어서 한쪽에서 넣는 일과 다른 쪽에서 꺼내는 일이 서로 방해하지 않습니다. 스택처럼 한쪽 끝만 쓰는 자료구조와 갈리는 지점이 여기입니다.

큐는 들어온 차례만 볼 뿐 일의 중요도는 안 봅니다. 급한 일을 남보다 먼저 처리해야 한다면 큐 하나로는 안 되고, 순위를 매겨 그 순위대로 꺼내는 우선순위 큐를 써야 합니다.

쌓이고 빠지는 순서

항목 A, B, C 가 차례로 들어온 큐에 D 가 도착하면 D 는 꼬리에 붙습니다. 그다음 머리에서 하나를 꺼내면 가장 먼저 들어왔던 A 가 나갑니다.

flowchart TD
    subgraph S1["A, B, C 가 들어와 있다"]
        A1["머리 · A"] --> B1["B"] --> C1["꼬리 · C"]
    end
    S1 -->|"D 도착"| S2
    subgraph S2["D 가 꼬리에 붙는다"]
        A2["머리 · A"] --> B2["B"] --> C2["C"] --> D2["꼬리 · D"]
    end
    S2 -->|"머리를 꺼낸다"| S3
    subgraph S3["A 가 빠지고 B 가 머리다"]
        B3["머리 · B"] --> C3["C"] --> D3["꼬리 · D"]
    end

처리 속도보다 빨리 쌓이면 생기는 일

들어오는 속도가 처리하는 속도보다 빠르면 큐에 쌓인 항목 수가 점점 늘어납니다. 서버 하나가 초당 800건을 처리할 수 있는데 요청이 초당 1000건씩 들어오면, 못 처리한 200건이 매초 큐에 쌓입니다.

이렇게 처리가 밀리는 지점을 병목이라고 부르고, 단위 시간에 실제로 끝낸 일의 수를 처리량이라고 부릅니다. 큐는 그 자체로 병목을 없애지 않습니다. 밀린 일을 잃어버리지 않고 순서대로 세워 둘 뿐입니다.

큐에 담을 수 있는 항목 수에는 한계가 있습니다. 한계에 닿으면 새로 들어오는 항목을 거절하거나 기다리게 하는데, 이 조절을 백프레셔라고 부릅니다.

큐가 쌓이는 속도와 기다리는 시간을 수식으로 다루는 분야가 큐잉 이론입니다. 큐에 평균 몇 개가 쌓여 있는지와 평균 대기 시간의 관계를 다루는 규칙은 리틀의 법칙이라고 부릅니다.

코드로 보면

파이썬 표준 라이브러리의 deque(더블 엔디드 큐, double-ended queue)로 큐의 동작을 확인할 수 있습니다. 왼쪽 끝을 머리, 오른쪽 끝을 꼬리로 씁니다.

from collections import deque
q = deque()
q.append("A")    # 큐: [A]
q.append("B")    # 큐: [A, B]
q.popleft()       # 'A' 반환, 큐: [B]

append 는 꼬리에 넣고, popleft 는 머리에서 꺼냅니다. 두 동작 모두 큐에 몇 개가 들어 있든 걸리는 시간이 일정합니다. 배열 하나로 어설프게 큐를 만들면 머리에서 뺄 때마다 나머지 항목을 전부 한 칸씩 당겨야 해서 항목 수에 비례해 시간이 늘어나는데, deque 는 이 문제를 피해 개수와 무관하게 일정한 시간만 씁니다.

배열로 만들 때와 연결 리스트로 만들 때

큐는 배열로도 만들 수 있고 연결 리스트로도 만들 수 있습니다. 배열로 만들면 머리 위치가 계속 뒤로 밀리는데, 이미 꺼낸 항목이 있던 앞부분이 빈 채로 낭비되지 않게 하려면 배열의 끝과 처음을 이어 붙인 것처럼 다루는 원형 버퍼 방식을 씁니다.

연결 리스트로 만들면 머리와 꼬리를 가리키는 포인터 두 개만 있으면 되고, 크기를 미리 정해 두지 않아도 됩니다. 대신 항목마다 다음 항목을 가리키는 포인터를 따로 저장해야 해서 배열보다 메모리를 조금 더 씁니다.

관련 항목

큐가 속하는 상위 분류

자료구조 · 선형 자료구조 · 컬렉션

큐를 대신 쓸 수 있는 다른 순서의 자료구조

스택 · 덱 · 우선순위 큐

큐를 만드는 데 쓰는 밑감 자료구조

배열 · 연결 리스트 · 원형 버퍼

큐가 밀릴 때 함께 나오는 성능 개념

병목 · 처리량 · 백프레셔 · 큐잉 이론 · 리틀의 법칙

큐를 실제로 쓰는 시스템과 기술

Vulkan · 스레드 풀 · 커넥션 풀 · 메시지 큐