큐는 먼저 넣은 원소를 먼저 꺼내는 선입선출 자료구조이다. 대기 작업을 순서대로 처리하거나 그래프의 너비 우선 탐색에 사용한다.
원리
뒤에서 추가하고 앞에서 제거한다. 원형 배열로 구현하면 앞 원소를 꺼낼 때 배열 전체를 옮기지 않고 시작 인덱스를 바꿀 수 있다.
예시
작업 A, B, C가 차례로 도착했다면 일반적인 큐의 제거 순서는 A, B, C이다. 우선순위에 따라 순서를 바꾸려면 별도의 우선순위 큐가 필요하다.
주의할 점
큐의 순서 보장만으로 여러 작업자의 완료 순서까지 보장되지는 않는다. 용량 제한, 빈 상태, 여러 스레드의 동시 접근 정책도 구현에서 정해야 한다.