배열로 큐를 만들었을 때는 몇 가지 불편한 점이 있다. 우선 배열의 크기보다 더 많은 데이터가 삽입되면 큐가 가득 차서 더 이상 삽입할 수 없는 오버플로우가 발생한다는 점이다. 그래서 필요한 최대 크기를 잘 고려하여 충분한 크기로 할당해야 한다. 그러나 아무리 넉넉해도 무한하지는 않기 때문에 언제 부족한 상황이 발생할지 예측할 수 없다. 물론 동적 배열을 쓸 수도 있겠지만 여러 가지 상황으로 볼 때 어울리지 않는다.
또한 배열은 연속적인 메모리 공간을 차지하는 직선적인 구조를 가지기 때문에 최대 크기만큼 충분한 용량을 확보했더라도 삽입점이 금방 배열 끝에 이르게 된다. 그래서 처음과 끝을 인위적으로 연결하여 원형으로 만들어 직선의 기억 공간을 재사용해야 하는 불편함이 있다. 뿐만 아니라 원형 구조이다 보니 가득찬 경우와 빈 경우가 잘 구분되지 않아 한칸을 버리거나 별도의 플래그를 도입하는 기법도 동원되어야 한다.
배열 대신 연결 리스트로 구현하면 이런 여러 가지 불편한 점을 해결할 수 있는데 배열이나 연결 리스트나 동일한 타입의 집합을 다룰 수 있으므로 연결 리스트로도 큐를 작성할 수 있다. 다음 예제는 앞에서 만든 배열 큐와 비슷하게 동작하는 연결 리스트로 만든 큐이다.
|
예 제 : LinkedQueue |
#include <Turboc.h>
struct Node
{
int value;
Node *prev;
Node *next;
};
Node *head;
void InitQueue()
{
head=(Node *)malloc(sizeof(Node));
head->prev=NULL;
head->next=NULL;
}
void Insert(int data)
{
Node *New;
Node *tail;
for (tail=head;tail->next;tail=tail->next) {;}
New=(Node *)malloc(sizeof(Node));
New->value=data;
New->next=NULL;
New->prev=tail;
tail->next=New;
}
int Delete()
{
int data;
Node *Target;
Target=head->next;
if (Target==NULL) {
return -1;
}
data=Target->value;
head->next=Target->next;
if (head->next) {
head->next->prev=head;
}
free(Target);
return data;
}
void FreeQueue()
{
while (Delete()!=-1) {;}
free(head);
head=NULL;
}
void main()
{
int i;
InitQueue();
for (i=0;i<100;i++) {
Insert(i);
}
for (i=0;i<100;i++) {
printf("%d ",Delete());
}
FreeQueue();
}
이중 연결 리스트를 사용했는데 100개의 자료를 넣었다가 빼 보았다. 연결 리스트는 데이터를 삽입할 때 노드를 동적으로 할당해서 뒤에 덧붙일 수 있으므로 이론적으로 메모리 한계까지 큐의 크기를 늘릴 수 있다. 따라서 큐가 가득차는 오버플로우가 발생하지 않으며 처음부터 큐의 크기를 미리 정할 필요도 없다. 또한 노드가 메모리의 임의 위치에 생성되었다가도 언제든지 파괴될 수 있으므로 원형으로 만들지 않아도 상관없다.
tail 쪽에서는 항상 새로 노드를 할당해서 덧붙이고 head쪽에서는 항상 노드를 삭제하기만 한다. 배열로 만든 큐가 고정된 크기를 가지는 원형 기억 공간을 다람쥐처럼 빙글 빙글 돌아다니는 꼴이라고 한다면 연결 리스트로 만든 큐는 빈 메모리 공간을 뱀처럼 구불 구불 기어다니는 모양에 비유할 수 있다. 연결 리스트를 쓸 때 오버플로우는 발생하지 않지만 큐가 빈 상태는 있을 수 있으므로 이 경우의 에러 처리는 생략할 수 없다.
큐를 만들 때는 연결 리스트가 배열에 비해서 확실히 쓰기 편하다. 그러나 삽입, 삭제가 단순히 head, tail을 옮기는 정도가 아니라 메모리를 할당하고 링크를 조작하는 번거로운 과정을 거쳐야 하므로 속도상으로는 약간의 불이익이 있다. 그리고 큐가 아주 작을 때는 꼭 필요한만큼의 노드만 생성하므로 배열에 비해 메모리 소모량이 적지만 일정 규모 이상으로 커지면 동적 할당된 노드와 링크 정보로 인해 오히려 배열보다 더 많이 메모리를 소모하기도 한다.
오버플로우를 걱정하지 않아도 된다는 것은 장점이기는 하지만 때로는 이것이 더 위험할 수도 있다. 프로그램에 논리적인 에러가 있을 경우 시스템의 전 메모리를 다 까먹을 때까지 할당을 해 댈 것이므로 차라리 오버플로우가 발생하는 것이 더 나을지도 모른다. 사실 큐를 사용하는 실제 예도 무한대의 큐를 요구하지는 않기 때문에 때로는 오버플로우가 필요하기도 하다.