스택(Stack)이 막혀있는 프링글스 통이었다면, 큐(Queue)는 양쪽이 뚫려있는 긴 파이프와 같습니다. 큐는 우리 일상생활에서 가장 익숙한 개념인 '줄 서기'를 그대로 컴퓨터 세계로 옮겨온 자료구조입니다. 맛집 앞에서 기다릴 때, 먼저 온 사람이 먼저 들어가는 것이 공평한 것처럼 컴퓨터 시스템에서도 순서대로 작업을 처리해야 할 때 큐가 반드시 필요합니다. 이번 글에서는 큐의 작동 원리인 FIFO 개념과 함께, 큐가 시스템 성능 최적화에 어떻게 기여하는지 상세히 알아보겠습니다.
1. 큐(Queue)란 무엇인가?
큐(Queue)는 데이터가 들어오는 입구(Rear)와 나가는 출구(Front)가 서로 다른 선형 자료구조입니다. 한쪽에서는 계속 밀어 넣고, 반대쪽에서는 계속 빼내는 구조를 가지고 있습니다.
1-1. FIFO (First In, First Out) 원리
큐의 제1원칙은 선입선출(FIFO)입니다. "가장 먼저 들어온 것이 가장 먼저 나간다"는 뜻입니다.
- Enqueue(인큐): 큐의 맨 뒤(Rear)에 줄을 서듯이 데이터를 추가하는 작업입니다.
- Dequeue(디큐): 큐의 맨 앞(Front)에 있는, 즉 가장 오래 기다린 데이터를 꺼내서 처리하는 작업입니다.
스택은 나중에 들어온 것이 먼저 나가지만, 큐는 들어온 순서가 그대로 유지됩니다. 따라서 데이터의 순서 보장(Ordering)이 필요한 모든 시스템의 기초가 됩니다.
2. 큐의 효율적인 구현: 선형 큐 vs 원형 큐
큐를 코드로 구현할 때 알아야 할 중요한 이슈가 있습니다. 바로 메모리 낭비 문제입니다.
2-1. 선형 큐(Linear Queue)의 문제점
막대기 같은 배열로 큐를 만들었다고 가정해 봅시다. 앞쪽(Front)에서 데이터가 빠져나가면 그 자리는 비게 됩니다. 하지만 큐의 특성상 데이터는 뒤쪽(Rear)으로만 계속 쌓입니다. 결과적으로 앞쪽 메모리 공간은 텅 비어있는데, 뒤쪽은 꽉 차서 더 이상 데이터를 받을 수 없는 비효율적인 상황이 발생합니다. 마치 버스 앞자리가 비었는데 승객들을 뒤로만 밀어 넣는 것과 같습니다.
2-2. 해결책: 원형 큐(Circular Queue)
이 문제를 해결하기 위해 등장한 것이 원형 큐입니다. 큐의 맨 끝과 맨 처음을 연결하여 도넛 모양의 고리(Ring)처럼 만든 구조입니다. 이렇게 하면 데이터가 빠져나가 빈 앞쪽 공간을 다시 재활용하여 뒤쪽에서 들어오는 데이터를 채울 수 있습니다. 메모리를 알뜰하게 무한히 회전시키며 사용할 수 있어 실무에서는 대부분 원형 큐(Ring Buffer) 방식을 사용합니다.
3. 큐는 어디에 쓰일까? (실무 활용 사례)
큐는 주로 두 장치 간의 속도 차이를 조절하거나, 비동기 처리를 할 때 완충지대 역할을 합니다.
3-1. 프린터의 인쇄 대기열 (Spooling)
컴퓨터(CPU)는 처리 속도가 엄청나게 빠르지만, 프린터는 상대적으로 매우 느립니다. 만약 CPU가 프린터 속도에 맞춰 인쇄 데이터를 하나씩 보낸다면 컴퓨터는 인쇄가 끝날 때까지 아무것도 못 하고 멈춰있을 것입니다. 그래서 CPU는 인쇄할 데이터를 큐(Queue)에 한 번에 다 몰아넣고 다른 일을 하러 갑니다. 프린터는 큐에 쌓인 순서대로 데이터를 하나씩 꺼내어 인쇄합니다. 이것이 바로 '스풀링'입니다.
3-2. 프로세스 스케줄링 (Scheduling)
운영체제(OS)는 하나의 CPU로 여러 프로그램을 동시에 실행하는 것처럼 보여줘야 합니다. 이때 실행 중인 프로그램(프로세스)들을 '준비 큐(Ready Queue)'에 줄 세워 놓고, 순서대로 CPU 사용 시간을 아주 조금씩 할당해 줍니다. 큐가 공평하게 순서를 관리해주기 때문에 우리는 음악을 들으며 문서 작업을 할 수 있습니다.
3-3. 너비 우선 탐색 (BFS) 알고리즘
코딩 테스트나 길 찾기 알고리즘에서 사용되는 BFS(Breadth-First Search)는 큐를 사용하는 대표적인 알고리즘입니다. 가까운 곳부터 순서대로 방문하고, 방문한 곳 주변을 다시 큐에 넣어 탐색 범위를 넓혀가는 방식으로 최단 경로를 찾아냅니다.
4. 우선순위 큐 (Priority Queue)
일반적인 큐는 무조건 선착순이지만, 예외가 필요한 경우가 있습니다. 바로 '응급실' 같은 상황입니다. 응급실에서는 접수 순서보다 환자의 위급함(우선순위)에 따라 진료 순서가 바뀝니다. 이처럼 데이터마다 우선순위를 부여하고, 우선순위가 높은 데이터가 먼저 나가는 특수한 큐를 '우선순위 큐'라고 하며, 힙(Heap)이라는 자료구조를 통해 구현합니다.
1. 큐는 들어온 순서대로 데이터를 처리하는 FIFO(선입선출) 구조입니다.
2. 메모리 효율을 위해 시작과 끝을 연결한 원형 큐(Circular Queue)를 주로 사용합니다.
3. 프린터 대기열, 프로세스 스케줄링, 데이터 버퍼링 등 순차 처리와 비동기 작업의 핵심 도구입니다.