큐

상위항목: 자료구조

[목차]

Queue

개념

width=400

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

데이터가 들어오는 위치는 가장 뒤(Rear 또는 Back이라고 한다.)에 있고, 데이터가 나가는 위치는 가장 앞(Front라고 한다.)에 있어서, 먼저 들어오는 데이터가 먼저 나가게 된다. 우선순위 큐, 원형 큐 등의 베리에이션이 존재한다. 입력 동작은 Enqueue, 출력 동작은 Dequeue라고 한다[* 간혹 스택과 동일하게 Push와 Pop을 쓰기도 하고, Push와 Pull을 사용하는 경우도 있다.].

구현

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

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

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

특수한 형태의 큐

원형 큐

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

우선순위 큐

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

데크(Deque; Double Ended Queue)

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

용도

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

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

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