큐(Queue) 자료구조 정리: 줄서기로 배우는 선입선출(FIFO)의 원리
앞서 알아본 스택(Stack)이 바닥이 막힌 '프링글스 통'이었다면, 오늘 알아볼 큐(Queue)는 양쪽이 시원하게 뚫려있는 '긴 파이프'나 '고속도로 터널'과 같습니다. 여러분이 금요일 저녁, 소문난 맛집 앞에 도착했다고 가정해 봅시다. 이미 식당 앞에는 길게 줄이 늘어서 있습니다. 이때 누군가가 늦게 왔음에도 불구하고 새치기를 해서 식당에 먼저 들어간다면 엄청난 항의가 빗발칠 것입니다. 먼저 온 사람이 먼저 서비스를 받는 것, 이것은 인간 사회의 가장 기본적인 공평함의 룰입니다. 놀랍게도 컴퓨터 세계에서도 수많은 데이터와 작업 요청이 동시에 쏟아질 때 질서를 유지하기 위해 이와 완벽하게 똑같은 원리를 사용합니다. 데이터의 순서를 엄격하게 보장해 주는 자료구조, 큐(Queue)의 세계로 안내합니다.
1. 큐(Queue)란 무엇인가?
큐(Queue)는 영어 단어 자체로 '표를 사기 위해 기다리는 줄', '대기 행렬'이라는 뜻을 가지고 있습니다. 컴퓨터 과학에서 큐는 데이터를 보관할 때 한쪽 끝에서는 데이터가 새롭게 들어오기만 하고, 반대쪽 끝에서는 저장된 데이터가 순서대로 빠져나가기만 하는 선형 자료구조를 일컫습니다. 스택이 입구와 출구가 같아서 순서가 뒤집히는 구조였다면, 큐는 입구와 출구가 명확하게 분리되어 있어 데이터의 흐름이 한쪽 방향으로만 일정하게 흐른다는 것이 가장 큰 구조적 특징입니다.
1-1. FIFO (First-In, First-Out) 원리: 공평한 줄 서기
큐를 관통하는 제1원칙은 바로 선입선출(FIFO)입니다. 직역하면 "가장 먼저 들어온 데이터가 가장 먼저 나간다"는 뜻입니다. 은행 창구에서 번호표를 뽑고 기다리는 상황을 생각하면 이해가 매우 쉽습니다. 1번 번호표를 뽑은 고객이 업무를 가장 먼저 보고, 100번 번호표를 뽑은 고객은 앞선 99명이 모두 업무를 마치고 빠져나갈 때까지 순서대로 대기해야만 합니다. 이처럼 큐는 들어온 순서를 100% 보장해주기 때문에, 작업의 '순서(Order)'와 '공평성'이 생명인 모든 시스템 아키텍처에서 근간이 됩니다.
2. 큐를 움직이는 핵심 동작 (Operations)
데이터가 앞뒤로 흐르는 큐를 조작하기 위해서는 특별한 명칭의 명령어들이 사용됩니다.
2-1. 인큐(Enqueue)와 디큐(Dequeue)
- Enqueue (넣기): 큐의 맨 뒤쪽(Rear, 꼬리)에 새로운 데이터를 추가하는 작업입니다. 맛집 대기 줄에 새로운 손님이 도착하면 항상 줄의 맨 끝에 서야 하는 것과 같은 이치입니다.
- Dequeue (꺼내기): 큐의 맨 앞쪽(Front, 머리)에 있는 데이터를 꺼내서 처리하고 제거하는 작업입니다. 줄의 맨 앞에 서 있던 손님이 드디어 식당 안으로 입장하는 것입니다.
큐 역시 맨 앞의 데이터가 무엇인지 확인만 하고 꺼내지는 않는 Peek 기능을 지원하며, 스택과 마찬가지로 양 끝에서의 데이터 추가와 삭제가 O(1)의 상상 초월하는 속도로 매우 빠르게 이루어집니다.
3. 큐의 진화: 메모리 낭비를 막는 '원형 큐(Circular Queue)'
이론적인 큐는 매우 직관적이지만, 막대기 모양의 배열(Array)을 이용해 코드로 실제 구현을 하다 보면 치명적인 한계에 부딪히게 됩니다. 맨 앞의 데이터가 빠져나가면(Dequeue) 배열의 앞쪽 공간은 텅 비게 됩니다. 하지만 새로운 데이터는 항상 맨 뒤(Rear)로만 들어오기 때문에, 앞쪽 메모리 공간이 비어있음에도 불구하고 뒤쪽 공간이 꽉 차버리면 더 이상 데이터를 받을 수 없는 심각한 메모리 낭비 현상이 발생합니다. 빈 공간을 채우기 위해 남은 데이터를 모두 앞으로 한 칸씩 당겨오는(Shift) 작업은 막대한 컴퓨터 자원을 낭비하게 됩니다.
이 문제를 천재적으로 해결한 것이 바로 원형 큐(Circular Queue) 또는 링 버퍼(Ring Buffer)입니다. 막대기 양 끝을 구부려서 동그란 도넛 모양으로 이어 붙인 형태입니다. 이렇게 하면 끝에 도달하더라도 다시 텅 비어있는 맨 앞자리로 자연스럽게 순환하며 공간을 100% 무한히 재활용할 수 있게 됩니다. 실제 현업의 운영체제나 서버 시스템에서는 대부분 이 원형 큐의 원리를 채택하여 사용합니다.
4. 큐는 실생활 시스템에서 어떻게 쓰일까?
큐는 여러 장치 간의 '속도 차이를 극복하는 완충 지대(Buffer)' 역할로 가장 널리 쓰입니다.
4-1. 프린터의 인쇄 대기열 (Spooling)
초고속으로 연산을 마치는 컴퓨터의 CPU에 비해, 종이에 잉크를 뿌리는 프린터의 물리적 동작 속도는 턱없이 느립니다. 만약 10명의 직원이 동시에 인쇄 명령을 내렸을 때 CPU가 프린터 속도에 맞춰 한 장씩 기다려준다면 컴퓨터는 멈춰버릴 것입니다. 그래서 운영체제는 인쇄 데이터들을 순서대로 프린터 큐(Queue)에 쏟아붓고 다른 일을 하러 떠납니다. 프린터는 큐에 쌓인 문서를 순서대로 차근차근 인쇄합니다.
4-2. 콜센터 대기열과 서버 트래픽 관리
고객센터에 전화를 걸었을 때 "현재 대기 인원이 많아 상담원 연결이 지연되고 있습니다"라는 안내 멘트를 들어보셨을 것입니다. 이때 여러분의 전화 연결 요청은 큐에 차곡차곡 쌓여 있으며, 상담원의 통화가 끝나는 대로 큐의 맨 앞(Front)부터 순차적으로 연결됩니다. 유명 콘서트 티켓팅 서버나 수강신청 서버에서도 트래픽 폭주로 서버가 터지는 것을 막기 위해, 모든 접속 요청을 일단 큐에 넣고 서버가 처리할 수 있는 양만큼만 순서대로 들여보내는 방식을 사용합니다.
1. 큐(Queue)는 입구와 출구가 명확히 분리되어 있어 데이터가 한 방향으로 흐르는 선형 구조입니다.
2. 먼저 들어온 요청을 먼저 처리하는 FIFO(선입선출)의 엄격한 순서 보장 원칙을 가집니다.
3. 빠른 장치와 느린 장치 간의 속도 차이를 메우는 버퍼(Buffer)나 서버 대기열(트래픽 관리)에 필수적입니다.