큐(Queue)란?
- 최근 프로그래머스 코딩테스트를 풀어보면서 스택/큐 태마에 문제를 풀다 문득, 큐에 대한 정의를 확실히 내릴 수 없었습니다.
- 코드와 씨름하며, 프레임웍과 aws sdk들과 씨름하며 기능개발에 몰두하는 것도 좋지만 기본기를 다지고 싶었습니다.
- 때문에 자료구조에 대해서 정리해봅니다.
- 자료구조 안에서 큐(Queue)란 무엇일까요?
1. 큐의 개념 정리
- 먼저 들어온 자료가 먼저 나가는 선입 선출 형태의 자료구조를 큐(Queue)라고 합니다.
- Queue(큐)라는 영단어 자체가 티켓 등의 표따위를 구매하기 위해 줄을서는 것을 의미합니다.
- 때문에 큐는 대기열 이라고도 합니다.
- 데이터가 들어오는 위치는 대기열의 가장 뒤에서 들어오고 그것을 Rear 혹은 Back이라고 합니다.
- 데이터가 나가는 위치는 대기열의 가장 앞이고 이를 Front라고 하고, 때문에 가장 먼저 들어오는 데이터가 먼저 나가게 됩니다.
- 우선순위 큐, 원형 큐 등의 큐의 변화적인 형태들이 존재합니다.
- 입력은 Enqueue라고 하며 출력은 Dequeue라고 표현, front에 위치한 데이터 조회는 Peek로 읽습니다.
2. 큐의 구현
- 스택처럼 보통의 배열을 사용해서 큐를 구현하면 입력(Enqueue) 및 출력(Dequeue)를 할 때마다 데이터가 앞으로 밀려나가는 문제가 생깁니다.
- 배열의 경우 앞쪽은 채워지고 뒷쪽은 빠져나가므로, 때문에 연결리스트를 사용하면 배열에 비해 쉽게 구현 가능합니다.
- 이를 선형 큐의 문제점이라고 할 수 있는데, 삽입삭제를 반복하다 보면 rear가 마지막 인덱스를 가르켜서 앞에는 비어있을 수 있지만 Rear가 마지막 인덱스이기 때문에 꽉 찼다고 인식하기 때문입니다.
- 이를 해결하기 위하여 시작 부분과 끝 부분을 포인터로 지정한 뒤 입출력을 하는 형태의 원형 큐(원형 버퍼)를 사용합니다.
- 대신 원형 큐가 가득찰 때와 비어있을 때 포인터가 같은 위치를 지정하기 때문에 이를 해결하기 위해 한쪽 공간을 비워놓습니다.
3. 원형 큐
- 배열을 지정해 큐(queue)를 사용할 때, Dequeue시 배열의 앞부분이 비게되는 점을 활용해 배열의 맨 마지막 부분을 쓰면 다시 제일 처음부터 큐를 채우기 시작하는 형태가 되고 이를 원형 큐라고 합니다.
- 기존 큐와 동일하지만 마지막 위치가 시작 위치와 연결되는 원형 구조를 띄어 원형 큐(원형 버퍼)라고 합니다.
- Enqueue를 하게되면 rear 포인터가 앞으로 이동하고 Dequeue를 하게되면 front 포인터가 앞으로 이동합니다.
- 동그랗게 연결되어 있기 때문에 두 포인터가 빙글빙글 돌면서 이동하는 구조가 됩니다.
- 이렇게 돌다가 rear포인터가 front포인터와 같은 위치에서 만나게 된다면 정말 여유 공간이 없기에 에러를 발생합니다.
4. 우선순위 큐
- 위 원형큐 그림의 각각의 원소들에게 우선순위를 매겨서 선입선출과 상관 없이 우선순위가 높은 원소부터 Dequeue하는 큐입니다.
- 이 경우 우선순위가 낮은 원소가 먼저 Enqueue된다면 Dequeue때 선입선출 개념이 안되는 상황이 됩니다.
- 이것의 대표적인 예로 Heap을 이야기할 수 있고, 힙 트리(heap tree)에 대해서 공부해야 자세히 이해할 수 있습니다.
- 힙트리는 여러개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기위해 만든 이진트리를 뜻하며 짧게는 힙(heap)이라 부릅니다.
- 아래 사진처럼 먼저 들어간 자료가 가장 밑에 쌓이는데 그중 우선순위(가장큰값)을 찾아 스왑하며 Dequeue합니다.
- 자세한 내용은 힙트리(Heap Tree)를 따로 포스팅 하겠습니다.
5. 큐의 용도
- 어떠한 작업(혹은 데이터)를 순서대로 실행(혹은 사용)하기 위해 대기열에 대기시킬 때 사용합니다.
- 서로 다른 쓰레드 사이 혹은 프로세스 사이나 네트워크를 통하여 자료를 주고받을 때 자료를 일시적으로 저장하는 용도로 많이 사용합니다.
마무리
- 큐는 선입선출 형태의 자료구조입니다.
- 선형큐는 문제가 있기 때문에 보통 원형큐를 많이 사용합니다.
- 우선순위큐는 선입선출에 위반되며 사용시 힙트리를 응용합니다.
