enqueue(A) enqueue(B) enqueue(C) dequeue()
┌─────────────────┐ ┌─────────────────┐
│ A │ │ B C │
└─────────────────┘ └─────────────────┘
front → ← rear front → ← rear
변형
유형
특징
활용
일반 큐
FIFO
작업 대기열
우선순위 큐
우선순위 높은 것 먼저
작업 스케줄링, 다익스트라
원형 큐
배열 끝→처음 연결
버퍼 관리
덱 (Deque)
양쪽 삽입/삭제
슬라이딩 윈도우
실무 활용
메시지 큐 (Kafka, RabbitMQ): 비동기 처리
BFS: 그래프 너비 우선 탐색
CPU 스케줄링: 프로세스 대기열
프린터 스풀러: 인쇄 대기열
배열로 만들 때의 함정
앞에서 빼는 것을 배열의 첫 칸을 지우는 식으로 만들면 뺄 때마다 전체를 한 칸씩 당깁니다.
그러면 빼는 것이 원소 수에 비례해 느려집니다.
머리와 꼬리 위치를 따로 들고 다닌다
꼬리가 끝에 닿으면 처음으로 돌아간다
그래서 넣고 빼는 것이 늘 일정한 시간이다
이 방식을 원형 큐라고 부릅니다. 다 찼는지와 다 비었는지가 같은 모양으로 보이는 것이
유일한 까다로운 점이라, 개수를 따로 세거나 한 칸을 비워 둡니다.
실무에서 큐가 하는 일
자료구조로서의 큐와 서비스에서 말하는 큐는 목적이 다릅니다.
어디
무엇을 위해
자료구조
순서대로 꺼낸다
스레드 사이
만드는 쪽과 쓰는 쪽의 속도를 떼어 놓는다
서비스 사이
받는 쪽이 느려도 보내는 쪽이 멈추지 않게 한다
셋째에서 큐의 길이가 곧 지연입니다. 무한히 늘어나는 큐는 문제를 감추다가 한꺼번에
터뜨립니다. 그래서 길이 상한을 둡니다.
시간 복잡도
연산
복잡도
enqueue
O(1)
dequeue
O(1)
peek/front
O(1)
탐색
O(n)
면접에서 이렇게 나옵니다
Q.큐를 활용하는 실무 사례를 말해주세요
사례
왜 큐인가
주문과 결제 처리
먼저 온 요청을 먼저 처리해야 공정하다
알림과 메일 발송
순서대로 보내되 실패는 뒤로 미룬다
작업 대기열 (이미지 변환, 리포트)
처리량을 넘는 요청을 쌓아두고 소화한다
메시지 브로커
생산자와 소비자의 속도를 분리한다
너비 우선 탐색
발견한 순서대로 방문해야 최단 거리가 나온다
프린터와 스케줄러
도착 순서를 지킨다
큐의 실무 가치는 순서만이 아닙니다. 처리 속도가 다른 두 쪽을 떼어 놓는 완충 역할이 더 큽니다. 초당 1,000건이 들어오고 200건만 처리할 수 있어도, 큐가 있으면 요청을 잃지 않고 밀린 만큼 지연으로 흡수합니다.
흔한 실수: 큐를 두면 지연이 사라진다고 답하는 것. 지연은 남고 유실이 줄어듭니다. 유입이 계속 처리량을 넘으면 큐는 무한히 자랍니다.
Q.우선순위 큐는 어떻게 구현하나요? 시간 복잡도는?
힙으로 구현합니다. 완전 이진 트리를 배열에 담아 부모가 자식보다 작다는 규칙만 유지합니다.
연산
복잡도
방법
최솟값 확인
O(1)
뿌리를 본다
삽입
O(log n)
맨 끝에 넣고 부모와 비교하며 올린다
최솟값 제거
O(log n)
뿌리에 마지막 원소를 놓고 자식과 비교하며 내린다
임의 값 탐색
O(n)
형제 사이 순서를 모른다
다른 선택과 비교하면 힙이 왜 표준인지 보입니다.
구현
삽입
최솟값 제거
정렬된 배열
O(n)
O(1)
정렬 안 된 배열
O(1)
O(n)
힙
O(log n)
O(log n)
둘 다 자주 쓰이므로 한쪽이 O(n)인 구현은 불리합니다.
흔한 실수: 우선순위 큐를 정렬된 리스트로 설명하는 것. 삽입이 O(n)이라 갱신이 잦은 스케줄러에는 맞지 않습니다.
Q.원형 큐가 일반 큐보다 유리한 경우는?
배열로 큐를 만들 때 앞쪽에 생긴 빈 공간을 재사용할 수 있습니다.
크기 5 배열에서 3개를 넣고 2개를 뺐다고 해봅시다.
방식
앞의 빈 두 칸
끝에 닿으면
일반 배열 큐
쓰지 못한다
더 넣을 수 없다
원형 큐
재사용한다
앞으로 돌아간다. (뒤 + 1) 나머지 크기로 위치를 계산한다
앞의 빈 칸을 메우려고 매번 앞으로 당기면 O(n)이 듭니다. 원형으로 쓰면 넣고 빼는 것이 모두 O(1)입니다.
그래서 크기가 정해진 버퍼에 유용합니다. 네트워크 수신 버퍼, 오디오 버퍼, 최근 로그 N건 보관이 대표적입니다.
흔한 실수: 꽉 찬 상태와 빈 상태를 구분하지 않는 것. 앞과 뒤가 같은 위치를 가리키는 상황이 둘 다에서 생기므로, 개수를 따로 세거나 한 칸을 비워두는 규칙이 필요합니다.
Q.BFS에서 큐를 쓰는 이유는?
가까운 곳을 먼저 다 보고 다음 겹으로 넘어가야 하므로, 발견한 순서대로 꺼내야 합니다.
시작점을 넣는다
꺼낸 노드의 이웃을 모두 넣는다
큐가 빌 때까지 반복한다
겹 0: 시작점
겹 1: 시작점의 이웃들
겹 2: 그 이웃들의 이웃들
먼저 넣은 것을 먼저 꺼내므로 겹 1 이 전부 나온 뒤에 겹 2 가 나옵니다. 이 성질 덕분에 간선 비용이 모두 같은 그래프에서 처음 도달한 시점이 최단 거리가 됩니다.
스택으로 바꾸면 방금 발견한 이웃부터 파고들어 깊이 우선 탐색이 됩니다. 최단 거리 보장이 사라집니다.
흔한 실수: 방문 표시를 꺼낼 때 하는 것. 넣을 때 표시해야 같은 노드가 큐에 여러 번 들어가지 않습니다.