[목차] Queue[* 스펠링은 5개인데 그 중 뒤의 3개(eue)가 묵음, 그리고 Q 자체가 "큐"라고 읽히니 실질적으론 뒤에 붙은 ueue가 싹 다 묵음인 기묘한 단어라 가끔 농담 소재가 된다. 원어민 중에서도 "큐웨웨"(...) 같은 식으로 잘못 발음하는 사람이 가끔 있다고.] == 개념 == [[파일:attachment/큐(자료구조)/queue.png|width=400]] 선입선출(先入先出, First In First Out; FIFO)의 [[자료구조]]. 대기열이라고도 한다. Queue라는 단어 자체가 표 같은 것을 구매하기 위해 줄서는 것을 의미한다. 데이터가 들어오는 위치는 가장 뒤(Rear 또는 Back이라고 한다.)에 있고, 데이터가 나가는 위치는 가장 앞(Front라고 한다.)에 있어서, 먼저 들어오는 데이터가 먼저 나가게 된다. 우선순위 큐, 원형 큐 등의 [[베리에이션]]이 존재한다. 입력 동작은 Enqueue, 출력 동작은 Dequeue라고 한다[* 간혹 [[스택(자료구조)|스택]]과 동일하게 Push와 Pop을 쓰기도 하고, Push와 Pull을 사용하는 경우도 있다.]. == 구현 == 보통의 [[배열]]을 사용해서 큐를 구현하면 Enqueue와 Dequeue을 할 때마다 계속 데이터가 앞으로 밀려나는 문제가 생기는데(앞쪽은 채워지고 뒤쪽은 빠져나가므로), 이를 해결하기 위해 원형 버퍼를 사용한다. 시작 부분과 끝 부분을 포인터로 지정한 뒤 Enqueue와 Dequeue를 하는 형태. 대신 가득찰 때와 비어있을 때 포인터가 같은 위치를 지정하기 때문에 이를 해결하기 위해 한 공간을 비워놓는다. [[연결 리스트]]를 사용하면 배열에 비해 매우 쉽게 구현이 가능하다. STL에는 선형 큐가 이미 알고리즘으로 구현되어 있지만, STL의 알고리즘을 이용해 원형 큐를 구현하는 것은 상당히 힘들다. [[http://bytes.com/topic/c/answers/443602-how-create-circular-queue-c|3번째 Jeremy Jurksztowicz의 답변(영어)]] === 라이브러리(c++) === c++에서 헤더 <queue>를 포함하면 std::queue로 구현된 큐 자료구조를 사용할 수 있다. 이 라이브러리는 상당히 스택 라이브러리와 비슷하다. 선언 : queue<원하는 자료형(구조체 가능)> (큐 이름, 배열도 가능) 입력 : 큐의 제일 앞에 값을 삽입한다. (큐 이름).push(<>안 자료형에 맞는 값); 값 제거 : 큐의 마지막 값을 제거한다. (큐 이름).pop(); 여기서 중요한것은 큐가 비어있을 때 실행하면 오류난다. 아래에서 서술할 empty 함수와 함께 사용해야 한다. 큐의 크기(반환값 정수) (큐 이름).size(); 큐가 비었는지 확인(반환값은 bool[* true 혹은 false]) : 큐가 비었으면 1 (큐 이름).empty(); ==== 예시 소스코드 ==== == 특수한 형태의 큐 == === 원형 큐 === 큐를 위해 배열을 지정해 놓고 큐를 쓰다보면 배열의 앞부분이 비게된다는 점을 활용해서 배열의 맨 마지막 부분을 쓰면 다시 제일 처음부터 다시 큐를 채우기 시작하는 형태의 큐이다. 원형 큐는 FIFO 구조를 지닌다는 점에서 기존의 큐와 동일하다. 그러나 마지막 위치가 시작 위치와 연결되는 원형구조를 띠기 때문에, 링 버퍼(Ring Buffer)라고도 부른다. 기존의 큐는 공간이 꽉 차게 되면 더 이상 요소를 추가할 수 없었다. 심지어 앞쪽에 요소들이 deQueue()로 모두 빠져서 충분한 공간이 남게 돼도 그쪽으로는 추가할 수 있는 방법이 없다.그래서 앞쪽에 공간이 남아 있다면 다음 그림과 같이 동그랗게 연결해 앞쪽으로 추가할 수 있도록 재활용 가능한 구조가 바로 원형 큐다. [[파일:3-9-7.png|width=600]] [[https://www.onlybook.co.kr/entry/algorithm-interview|<파이썬 알고리즘 인터뷰>]] p.260, 책만, 2020 동작하는 원리는 투 포인터와도 비슷하다. 그림과 같이 마지막 위치와 시작 위치를 연결하는 원형 구조를 만들고, 요소의 시작점과 끝점을 따라 투 포인터가 움직인다. enQueue()를 하게 되면 rear 포인터가 앞으로 이동하고, deQueue()를 하게 되면 front 포인터가 앞으로 이동한다. 이렇게 enQueue()와 deQueue()를 반복하게 되면 서로 동그랗게 연결되어 있기 때문에 투 포인터가 빙글빙글 돌면서 이동하는 구조가 된다. 이 그림의 enQueue(60) 이후에는 rear 포인터가 원래의 front 포인터 자리까지 도달해 빙글빙글 돌고 있는 모습을 확인할 수 있다. 만약 rear 포인터가 front 포인터와 같은 위치에서 서로 만나게 된다면, 다시 말해 만나는 위치까지 이동했다면, 그때는 정말로 여유 공간이 하나도 없다는 얘기가 되므로 공간 부족 에러를 발생시킨다. === 우선순위 큐 === 우선순위 큐는 말 그대로 원소들에게 우선순위를 매겨서 넣을 때의 순서와 상관없이 뺄 때에는 우선순위가 높은 원소부터 빼내는 것이다. 이 경우에 만약 우선순위가 낮은 원소가 들어간다면(Enqueue) 빼낼 때에는(Dequeue) 정말로 [[들어올 때는 마음대로였겠지만 나갈 때는 아니란다|들어갈 땐 마음대로지만 나갈땐 아닌]] 상황이 된다. 대표적인 예로 heap이 있다. 자세한 내용은 [[힙 트리]] 항목 참조. === 데크(Deque; Double Ended Queue) === [[파일:3-10-1.png|width=600]] [[https://www.onlybook.co.kr/entry/algorithm-interview|<파이썬 알고리즘 인터뷰>]] p.266, 책만, 2020 일반적인 큐는 뒤에서만 삽입이 이루어지고 앞에서만 인출이 가능한 데 비해, 데크는 양쪽에서 모두 삽입/인출이 가능한 스택과 큐의 특징을 모두 갖고 있다. 이 추상 자료형(ADT)의 구현은 배열이나 연결 리스트 모두 가능하지만, 특별히 그림과 같이 이중 연결 리스트(Doubly Linked List)로 구현하는 편이 가장 잘 어울린다. 이중 연결 리스트로 구현하게 되면, 그림처럼 양쪽으로 head와 tail이라는 이름의 두 포인터를 갖고 있다가 새로운 아이템이 추가될 때마다 앞쪽 또는 뒤쪽으로 연결시켜 주기만 하면 된다. 당연히 연결 후에는 포인터를 이동하면 된다. == 용도 == 어떠한 작업/데이터를 순서대로 실행/사용하기 위해 '''대기'''시킬 때 사용한다. 서로 다른 쓰레드 사이 또는 프로세스 사이에서나 네트워크를 통해 자료를 주고받을 때 자료를 일시적으로 저장하는 용도로 많이 사용된다. [[분류:자료구조]]