큐(Queue)는 자료구조의 한 종류로, 먼저 들어온 데이터가 먼저 나가는(First-In, First-Out; FIFO) 원리를 따른다. 이는 줄을 서서 기다리는 것과 유사하다고 생각할 수 있다. 가장 먼저 줄에 선 사람이 가장 먼저 서비스를 받는 것처럼, 큐에서도 가장 먼저 추가된 데이터가 가장 먼저 삭제된다.
주요 연산:
- Enqueue (삽입): 큐의 끝(rear)에 새로운 데이터를 추가하는 연산이다.
- Dequeue (삭제): 큐의 앞(front)에서 데이터를 제거하는 연산이다. 만약 큐가 비어있는 경우, 언더플로우(underflow) 에러가 발생할 수 있다.
- Peek (검색): 큐의 앞(front)에 있는 데이터를 확인하는 연산이다. 데이터는 삭제되지 않고, 값만 확인한다.
- isEmpty(): 큐가 비어있는지 확인하는 연산이다.
- isFull(): 큐가 가득 차있는지 확인하는 연산이다. (구현에 따라 다름, 배열 기반 큐의 경우에 해당)
구현 방법:
큐는 배열이나 연결 리스트 등을 이용하여 구현할 수 있다. 배열을 사용하는 경우, 큐의 크기가 고정되며, 꽉 찬 큐에 enqueue 연산을 시도하면 오버플로우(overflow) 에러가 발생한다. 연결 리스트를 사용하는 경우, 메모리의 제약 없이 큐의 크기를 동적으로 조절할 수 있다. 또한, 원형 큐(circular queue)와 같은 변형된 구조를 이용하여 메모리 효율을 높일 수 있다.
응용:
큐는 다양한 분야에서 사용된다. 예를 들어, 운영체제의 작업 스케줄링, 프린터 큐, 브로드캐스트 시스템, 버퍼 등에서 널리 활용된다. FIFO 원리를 필요로 하는 모든 시스템에서 큐는 효율적인 데이터 관리를 위한 필수적인 자료구조이다.