큐(자료구조)

상위항목: 자료구조

Queue

1 개념

400px

선입선출(先入先出, First In First Out; FIFO)의 자료구조. 대기열이라고도 한다. Queue라는 단어 자체가 표 같은 것을 구매하기 위해 줄서는 것을 의미한다.

데이터가 들어오는 위치는 가장 뒤(Rear 또는 Back이라고 한다.)에 있고, 데이터가 나가는 위치는 가장 앞(Front라고 한다.)에 있어서, 먼저 들어오는 데이터가 먼저 나가게 된다. 우선순위 큐, 원형 큐 등의 바리에이션이 존재한다. 입력 동작은 Enqueue, 출력 동작은 Dequeue라고 한다.

2 구현

보통의 배열을 사용해서 큐를 구현하면 Enqueue와 Dequeue을 할 때마다 계속 데이터가 앞으로 밀려나는 문제가 생기는데(앞쪽은 채워지고 뒤쪽은 빠져나가므로), 이를 해결하기 위해 원형 버퍼를 사용한다. 시작 부분과 끝 부분을 포인터로 지정한 뒤 Enqueue와 Dequeue를 하는 형태. 대신 가득찰 때와 비어있을 때 포인터가 같은 위치를 지정하기 때문에 이를 해결하기 위해 한 공간을 비워놓는다.

연결 리스트를 사용하면 배열에 비해 매우 쉽게 구현이 가능하다.

STL에는 선형 큐가 이미 알고리즘으로 구현되어 있지만, STL의 알고리즘을 이용해 원형 큐를 구현하는 것은 상당히 힘들다. 3번째 Jeremy Jurksztowicz의 답변 참고. 영어 주의

3 특수한 형태의 큐

3.1 원형 큐

큐를 위해 배열을 지정해 놓고 큐를 쓰다보면 배열의 앞부분이 비게된다는 점을 활용해서 배열의 맨 마지막 부분을 쓰면 다시 제일 처음부터 다시 큐를 채우기 시작하는 형태의 큐이다.

3.2 우선순위 큐

우선순위 큐는 말 그대로 원소들에게 우선순위를 매겨서 넣을 때의 순서와 상관없이 뺄 때에는 우선순위가 높은 원소부터 빼내는 것이다. 이 경우에 만약 우선순위가 낮은 원소가 들어간다면(Enqueue) 빼낼 때에는(Dequeue) 정말로 들어갈 땐 마음대로지만 나갈땐 아닌 상황이 된다. 대표적인 예로 heap이 있다. 자세한 내용은 힙 트리 항목 참조.

3.3 데크(Deque; Double Ended Queue)

400px
일반적인 큐는 뒤에서만 삽입이 이루어지고 앞에서만 인출이 가능한 데 비해, 데크는 양쪽에서 모두 삽입/인출이 가능하다.

4 용도

어떠한 작업/데이터를 순서대로 실행/사용하기 위해 대기시킬 때 사용한다.

서로 다른 쓰레드 사이 또는 프로세스 사이에서나 네트워크를 통해 자료를 주고받을 때 자료를 일시적으로 저장하는 용도로 많이 사용된다.

흔히 자동매칭이 되는 게임(대표적으로 리그 오브 레전드)에서 대기할 때 "큐를 돌린다"고 하는데 그게 바로 이 큐다. 먼저 준비를 마친 쪽이 우선적으로 매칭이 되도록 만드는 시스템이기 때문. 사실 이 경우는 굳이 전문용어로서의 의미가 아니라 단어 자체의 원 의미인 '줄서기'에 가깝다.