프로그래밍을 공부하다보면 가장 먼저 마주하게 되는 자료구조 중 하나가 바로 "큐(Queue)"입니다. 듣고보면 단순한 개념 같지만, 실제로 백엔드 시스템이나 대용량 트래픽을 처리하는 아키텍처에서 절대 빠질 수 없는 핵심 원리이기도합니다.
오늘은 큐의 기본 개념부터 실제 개발 환경에서 어떻게 활용되는지까지 정리해보겠습니다.
1. 큐(Queue)란?
큐는 쉽게 말하면 대기열입니다. 내가 좋아하는 맛집에 가서 줄을 서는 웨이팅, 은행에 가서 번호표를 뽑고 대기하는 상황 등 모두 먼저 온 사람이 먼저 서비스를 받는 것과 동일한 원리로 동작합니다.
이를 컴퓨터 공학 용어로 "FIFO(First In, First Out - 선입선출)"이라고 부릅니다. 먼저 들어간 데이터가 가장 먼저 밖으로 나오는 구조입니다. 흔히 우리가 아는 스택(Stack)은 큐와 반대로 나중에 들어간 데이터가 먼저 나오는 "후입선출"입니다.
2. 큐의 핵심 동작
큐는 데이터를 넣고 빼는 구멍이 양쪽으로 뚫려 있는 원기둥을 상상하면 이해가기 쉽습니다. 한쪽에서는 데이터가 들어오고, 다른 한쪽에서는 데이터가 빠져나갑니다. 이런 데이터의 이동을 활용한 큐의 동작에는 3가지정도 있습니다.
- Enqueue : 큐의 맨 뒤(Rear)에 새로운 데이터를 추가하는 작업입니다. (Java에서는 offer(), add() 메서드 등을 사용합니다.)
- Dequeue : 큐의 맨 앞(Front)에 있는 데이터를 꺼내서 제거하는 작업입니다. (Java에서는 poll(), remove() 등을 사용합니다.)
- Peek : 큐의 맨 앞에 있는 데이터가 무엇인지 '확인'만 하고 꺼내지는 않는 작업입니다.
위와 같은 핵심 동작들이 어떻게 동작하는지 Java에서의 코드로 알아보겠습니다.
3. Java에서의 큐 사용법
Java에서 큐는 인터페이스로 구현되어 있기 때문에 큐를 사용하기위해서는 이를 구현한 클래스를 선택해야 합니다. 이때 가장 흔하게 사용하는 것이 LinkedList입니다.
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
// Queue는 인터페이스이므로 LinkedList를 통해 객체 생성
Queue<String> queue = new LinkedList<>();
// 데이터 추가 (Enqueue)
queue.offer("첫 번째 손님");
queue.offer("두 번째 손님");
queue.offer("세 번째 손님");
// 가장 먼저 들어온 데이터 확인 (Peek)
System.out.println("다음 차례: " + queue.peek()); // 출력: 첫 번째 손님
// 데이터 꺼내기 (Dequeue)
System.out.println("처리 완료: " + queue.poll()); // 출력: 첫 번째 손님
System.out.println("처리 완료: " + queue.poll()); // 출력: 두 번째 손님
}
}
이러한 다양한 기능을 가진 큐에게도 치명적인 단점이 있습니다.
가장 기본적인 형태인 배열 기반의 선형 큐는 심각한 메모리 낭비 문제가 있습니다. 데이터를 꺼낼 때마다 앞쪽(Front)의 공간이 비게 되는데, 뒤쪽(Rear)이 배열의 끝에 도달하면 앞쪽 공간이 비어있음에도 "큐가 가득 찼다"고 잘못 판단하게 됩니다. 이를 해결하기 위해 앞당기는 작업을 하면 O(n)의 시간 복잡도가 발생해 성능이 크게 떨어집니다.
이를 해결하기 위해 등장한 개념들이 있습니다.
① 원형 큐 (Circular Queue)
배열의 처음과 끝이 연결되어 있다고 가정하는 구조입니다. "(Rear + 1) % 배열_크기" 연산을 통해 포인터를 순환시킵니다. 앞쪽 공간이 비어있다면 Rear가 다시 배열의 첫 인덱스로 돌아가 메모리를 재사용합니다.
② 우선순위 큐 (Priority Queue)
들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 나가는 큐입니다. 내부적으로는 주로 힙(Heap) 트리 자료구조를 사용하여 구현되며, 데이터 삽입/삭제 시 O(log n)의 시간 복잡도를 가집니다. 운영체제의 작업 스케줄링이나 네트워크 라우팅에서 핵심적으로 사용됩니다.
③ 덱 (Deque, Double-Ended Queue)
덱은 양쪽 끝 모두에서 데이터의 삽입과 삭제가 자유롭게 가능한 자료구조입니다. 큐와 스택의 특성을 모두 가지고 있어 상황에 맞게 유연하게 활용할 수 있습니다. Java에서는 ArrayDeque나 LinkedList를 통해 구현할 수 있습니다.
4. 실무에서 사용 방안
단순히 알고리즘 문제를 풀 때만 큐가 쓰이는 것은 아닙니다. 실제 서버 시스템을 설계할 때 큐는 엄청난 위력을 발휘합니다. 그 중 하나인 메시지 큐에 대해서 설명해보겠습니다.
메시지 큐 (Message Queue)
단일 프로그램 내부를 넘어, 여러 서버가 통신하는 분산 시스템에서 큐는 메시지 브로커(Message Broker)라는 거대한 인프라 확장됩니다. 대표적으로 Kafka, RabbitMQ 같은 기술들이 있습니다. Kafka는 이에 대한 해결 방법으로 Producer가 발행한 이벤트를 카프카 클러스터의 메시지 큐에 물리적인 저장공간인 파티션에 순서대로 저장해두고 이벤트를 구독하는 Consumer가 차례대로 꺼내쓰는 방식입니다.
가상화폐 거래소의 주문 체결 시스템을 상상해 볼까요? 수만 명의 사용자가 같은 1초 동안 '매수/매도' 버튼을 누릅니다. 이 엄청난 트래픽을 데이터베이스에 바로 꽂아 넣으려 하면, DB 커넥션 풀이 고갈되거나 심각한 데드락에 빠져 서버가 마비됩니다.
이때 메시지 큐가 완충 지대 역할을 합니다.
- 관심사 분리 (Decoupling): 웹 서버는 사용자의 주문 요청을 받아 '메시지 큐'에 던져넣기만 하고 바로 사용자에게 "주문 접수 완료" 응답을 냅니다.
- 부하 분산 (Load Leveling): 뒤편에 있는 체결 엔진 서버들은 큐에 쌓인 주문 데이터를 본인들이 감당할 수 있는 속도로 하나씩(또는 묶어서) 꺼내어 안전하게 DB에 기록합니다.