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