큐(Queue)와 FIFO: 맛집 줄서기로 이해하는 선입선출의 원리
스택이 '프링글스 통'이라면, 큐(Queue)는 우리가 매일 겪는 '줄 서기'입니다. 유명한 맛집 앞에 길게 늘어선 줄, 출근길 버스를 타기 위해 기다리는 줄을 생각해 보세요. 새치기가 없다면, 가장 먼저 온 사람이 가장 먼저 식당에 들어가고 버스에 탑승합니다. 이 공평하고 상식적인 원리가 바로 큐의 핵심인 FIFO(First In, First Out)입니다. 컴퓨터 시스템이 수많은 작업을 꼬이지 않고 순서대로 처리할 수 있는 비결, 큐에 대해 파헤쳐 봅니다.
1. 큐의 대원칙: 선입선출 (FIFO)
큐는 스택과 달리 양쪽이 뚫려 있는 터널과 같습니다. - 입구 (Rear): 데이터가 들어가는 곳입니다. 줄의 맨 뒤에 서는 것과 같습니다 (Enqueue). - 출구 (Front): 데이터가 나가는 곳입니다. 줄의 맨 앞에서 입장하는 것과 같습니다 (Dequeue). 들어오는 문과 나가는 문이 다르기 때문에, 데이터의 흐름은 한쪽 방향으로 일정하게 유지됩니다.
2. 큐의 종류와 진화 (선형 큐 vs 원형 큐)
이론적인 큐는 쉽지만, 실제로 컴퓨터 코드로 구현할 때는 한 가지 문제가 발생합니다.
2-1. 선형 큐(Linear Queue)의 문제점
막대기 같은 배열로 큐를 만들었다고 칩시다. 앞사람이 빠져나가면(Dequeue) 앞자리가 빕니다. 하지만 뒤에서는 계속 사람이 들어옵니다(Enqueue). 결국 앞쪽 공간은 텅 비었는데 뒤쪽은 꽉 차서 더 이상 데이터를 못 받는 메모리 낭비가 발생합니다. 그렇다고 앞자리를 채우려고 뒤에 있는 사람들을 다 앞으로 한 칸씩 땡기자니 시간이 너무 오래 걸립니다.
2-2. 해결책: 원형 큐 (Circular Queue)
그래서 똑똑한 개발자들은 큐의 머리와 꼬리를 이어 붙여 도넛 모양의 원형 큐를 만들었습니다. 이렇게 하면 데이터가 빠져나간 빈 앞자리에 다시 새로운 데이터를 채워 넣을 수 있어 메모리를 100% 알뜰하게 재사용할 수 있습니다. (운영체제 버퍼 등 실무에서는 대부분 원형 큐를 씁니다.)
3. 큐, 어디에 쓰일까? (순서가 생명이다)
큐는 '비동기 처리'와 '순서 보장'이 필요한 모든 곳에 쓰입니다.
3-1. 프린터 인쇄 대기열
회사에서 10명이 동시에 '인쇄' 버튼을 눌렀다고 상상해 봅시다. 프린터는 한 대뿐입니다. 이때 프린터는 요청 들어온 순서대로 문서를 큐(Queue)에 쌓아둡니다. 그리고 먼저 들어온 문서부터 하나씩 차례대로 인쇄합니다. 큐가 없다면 문서 내용이 뒤섞여 엉망진창이 될 것입니다.
3-2. 티켓팅 대기 순번
아이유 콘서트 티켓팅을 할 때 "현재 대기 순서 15,300번째입니다"라는 창을 보신 적 있나요? 서버가 접속 요청을 큐에 넣어두고 처리 가능한 만큼만 순서대로 입장시키기 때문입니다. 큐는 폭주하는 트래픽으로부터 서버가 다운되지 않도록 지켜주는 방파제 역할을 합니다.
3-3. 키보드 입력 버퍼
여러분이 타자를 엄청 빠르게 치면, 컴퓨터가 잠시 멈칫하더라도 글자는 사라지지 않고 순서대로 화면에 찍힙니다. 입력된 키 정보가 '입력 버퍼(큐)'에 저장되어 있다가 순차적으로 처리되기 때문입니다.
1. 큐(Queue)는 입구와 출구가 다른 FIFO(선입선출) 구조로, 순서 보장에 최적화되어 있습니다.
2. 메모리 낭비를 막기 위해 시작과 끝을 연결한 원형 큐(Circular Queue) 방식을 주로 사용합니다.
3. 프린터 스풀링, 서버 대기열, 프로세스 관리 등 순차적 처리가 필요한 시스템의 핵심 부품입니다.