큐(Queue)

큐는 데이터를 처리할 때 들어온 순서 그대로 다뤄야 하는 상황에서 사용하는 자료구조다. 이 구조의 가장 큰 특징은 먼저 들어온 값이 먼저 나가는 FIFO(First In, First Out) 방식이라는 점이다. 우리가 은행이나 카페에서 줄을 서는 모습과 같다. 먼저 줄을 선 사람이 먼저 서비스를 받고, 나중에 온 사람은 뒤에서 기다린다. 큐에서는 이러한 흐름을 그대로 코드로 표현한다.

큐의 기본 동작은 두 가지다. 데이터를 뒤에 추가하는 enqueue, 앞에서 꺼내는 dequeue. enqueue는 “줄 맨 뒤에 서기”에 해당하고, dequeue는 “줄 맨 앞 사람이 빠져나가는 것”이다. 이 두 연산은 큐의 양 끝에서만 이루어지기 때문에 구조가 단순하고, 삽입과 삭제가 모두 O(1)의 일정한 시간 안에 처리된다. 그래서 외부에서 데이터가 밀려오고, 내부에서는 들어온 순서대로 하나씩 처리해야 하는 환경에서 큐는 아주 유용하다.

실제로 큐는 컴퓨터 곳곳에서 쓰인다. 프린터가 출력할 문서를 하나씩 처리할 때, 먼저 들어온 문서부터 순서대로 뽑힌다. 운영체제(OS)에서는 프로세스를 공평하게 다루기 위해 큐를 사용해 작업을 대기시키고 실행 순서를 조절한다. 네트워크에서도 패킷이 도착하는 순서를 보존하기 위해 큐 구조를 사용한다. 알고리즘에서는 BFS(너비 우선 탐색)의 핵심이 바로 큐인데, 노드를 하나씩 탐색할 때 들어온 순서대로 처리해야 하므로 큐가 자연스럽게 선택된다.

물론 큐에도 한계는 있다. 스택처럼 중간값을 바로 꺼낼 수는 없다. 왜냐하면 큐는 언제나 가장 앞에 있는 값부터 꺼내도록 설계되어 있기 때문이다. 따라서 “특정 위치의 값을 빠르게 찾아야 하는 문제”에는 적합하지 않다. 그 대신, 순서를 보장하고 공정하게 처리해야 하는 상황이라면 큐만 한 구조가 없다.

정리하자면 큐는 단순하지만 여러 시스템에서 핵심적으로 사용되는 자료구조다. 들어온 순서대로 처리해야 하는 상황이 생긴다면, 큐는 가장 자연스럽고 가장 안정적으로 문제를 해결한다. 그리고 enqueue와 dequeue라는 두 동작만으로도 충분히 다양한 흐름을 다룰 수 있기 때문에, 자료구조를 배울 때 꼭 이해하고 넘어가야 하는 개념이기도 하다.