Queue의 개념과 특징
큐(queue)는 한 쪽에서는 원소를 삽입하기만 할 수 있고 다른 쪽에서는 원소를 삭제하기만 할 수 있는, 줄(queue) 혹은 파이프 같은 형태의 자료구조이다.
영어에서 queue는 줄이라는 뜻이다. 버스 정류장에서 사람들이 줄을 서서 기다리는 모습이 큐와 유사하다고 할 수 있다. 버스 정류장에서 줄을 설 때 먼저 온 사람이 줄의 앞에 서고, 나중에 온 사람은 줄의 가장 뒤에 선다. 버스가 오면 먼저 온 사람부터 차례대로 버스를 탄다. 자료구조의 한 형태인 큐도 마찬가지로 먼저 삽입된 원소가 먼저 불러와지고 삭제되고, 나중에 삽입된 원소들은 뒤에서 기다리고 있다가 차례대로 불러와지고 삭제된다.
큐는 한 쪽에서 원소 삽입과 삭제가 모두 일어나는 스택(stack)과는 대비된다. 스택은 First come, last served, 즉 가장 먼저 삽입된 원소가 가장 나중에 리턴되고 삭제되며 가장 나중에 삽입된 원소가 가장 먼저 리턴되고 삭제된다. 이에 비해 큐는 Fisrt come, first served, 즉 가장 먼저 삽입된 원소가 가장 먼저 리턴되고 삭제되는 특징을 가진다.
큐에는 rear 포인터와 front 포인터가 사용된다. front 포인터는 큐에 들어있는 원소들 중 제일 먼저 삽입된 원소의 위치의 바로 앞을 가리킨다. front는 처음에 큐가 비어있을 때나, 삽입만 일어나고 삭제는 일어나지 않은 상태에서는 –1을 가리키고, 원소가 하나씩 삭제될 때마다 1씩 증가하여 삭제 후 남은 원소들 중 가장 먼저 삽입된 원소의 바로 앞 위치를 가리킨다.
rear 포인터는 큐에 들어있는 원소들 중 가장 나중에 삽입된 원소의 위치를 가리킨다. 큐가 비어있을 때에는 –1, 원소 하나가 삽입되면 0, 원소가 하나씩 삽입 될 때마다 1씩 증가한다.
큐가 비었을 때 rear 포인터와 front 포인터가 만난다(rear 포인터와 front 포인터가 같은 위치를 가리킨다).
CPU에서 여러 작업을 처리할 때 큐가 이용된다. 먼저 요청된 작업 순서대로 처리하고자 할 때 요청된 작업들을 큐에 삽입한 후 차례로 불러오고 큐에서 제거하는 방식이다.
배열을 이용한 큐 구현 시 문제점과 해결방안
배열을 이용하여 큐를 구현했을 시 발생하는 문제점은 큐가 가득 차 있지 않은 상태더라도 더 이상 삽입을 할 수 없는 경우가 생긴다는 점이다. 이러한 상황이 발생하는 이유는, 큐에 원소들을 삽입하고 삭제하면 큐의 앞부분이 비어버리기 때문이다. 이것을 그림으로 살펴보겠다.
그림 8
그림 9
그림 8은 크기가 4인 큐를 나타낸다. 4개의 공간에 모두 원소가 삽입되어 있어 큐가 가득 차 있는 상태이다. 여기에서 삭제 연산을 두 번 수행하게 되면 그림 9처럼 [0]과 [1] 부분이 비게 된다. rear 쪽에서만 삽입 연산을 할 수 있으므로, 앞의 두 자리가 비어 있는데도 불구하고 더 이상 원소를 삽입할 수 없는 상황이 된다. 이 경우 비어있는 부분의 메모리가 낭비되어 이상적이지 않다. 그림에서 색칠된 부분은 낭비되는 메모리를 나타낸다.
이 문제를 해결하기 위해 원형 큐가 고안되었다. 원형 큐는 기존의 관 형태의 큐의 처음과 마지막 부분을 이어 붙여 원형으로 만든 것이다. 이렇게 하면 큐가 가득 차지만 않았다면 새로운 원소를 삽입할 수 있다. 결과적으로 메모리 공간을 효율적으로 사용할 수 있다.
그림 10
그림 11
그림 10은 그림 1, 2의 큐를 원형 큐로 변형해 나타낸 것이다. 기존 큐의 마지막 부분인 [3] 다음에 처음 부분인 [0]이 이어지는 형태이다. 색칠된 부분은 기존에 낭비되었던 메모리 공간이다. 기존 큐에서는 그 공간에 새로운 원소를 삽입할 수 없었지만, 원형 큐로 바꾸게 되면 그림 11처럼 색칠된 공간인 [0]과 [1]에 새로운 원소를 삽입할 수 있다. 이처럼 원형 큐를 사용하면 큐가 가득 차지 않았는데도 더 이상 원소를 삽입할 수 없는 문제가 해결되어 메모리 공간의 낭비를 막을 수 있다.
