연결 리스트로 구현한 큐

연결 리스트로 큐를 구현하면 배열로 구현한 큐에 비해 크기가 제한되지 않는다는 장점이 있다. 다만, 메모리 공간을 더 많이 차지하고 삽입과 삭제시 좀 더 오래 걸린다는 단점이 있다.

기본적인 구조

단순 연결 리스트에 front와 rear 포인터를 추가한 것과 같다. 큐에 요소가 없는 경우에는 front와 rear은 NULL이 된다.

구조체 정의

typedef int element;
typedef struct QueueNode {
	element data;
	struct QueueNode *link;
} QueueNode;

typedef struct {
	QueueNode *front, *rear;
} LinkedQueueType;

삽입 연산

기본적인 원리는 단순 연결 리스트의 추가와 동일하나 head 포인터로 첫 번째 노드를 가리키지 않고, front와 rear 포인터로 첫 노드와 마지막 노드를 가리킨다는 차이점이 있다.

위 그림은 공백 상태일 때의 삽입 연산을 나타낸 것이다.

값이 존재할 때의 삽입 연산은 다음과 같다.

코드는 다음과 같다.

void enqueue(LinkedQueueType *q, element data)
{
	QueueNode *temp = (QueueNode *)malloc(sizeof(QueueNode));
	temp->data = data; 		// 데이터 저장
	temp->link = NULL; 		// 링크 필드를 NULL
	if (is_empty(q)) { 		// 큐가 공백이면
		q->front = temp;
		q->rear = temp;
	}
	else {
		q->rear->link = temp;
		q->rear = temp;
	}
}

삭제 연산

가장 먼저 공백 상태인지 확인하고, 공백 상태라면 front가 가리키는 노드를 temp가 가리키도록 하고 front는 front의 링크값으로 대입한다. 그러면 front는 현재 가리키는 노드의 다음 노드를 가리키게 될 것이다. 그 다음 temp가 가리키는 노드로부터 데이터를 꺼내오고 메모리 해제를 하여 노드를 삭제해준다.

코드는 다음과 같다.

element dequeue(LinkedQueueType *q)
{
	QueueNode *temp =q-> front;
	element data;
	if (is_empty(q)) {		// 공백상태
		fprintf(stderr, "스택이 비어있음\n");
		exit(1);
	}
	else {
		data = temp->data; 		// 데이터를 꺼낸다.
		q->front = q->front->link; // front를 다음노드를 가리키도록 한다.
		if (q->front == NULL) 	// 공백 상태
			q->rear = NULL;
		free(temp); 			// 동적메모리 해제
		return data; 			// 데이터 반환
	}
}

전체 코드

#include <stdio.h>
#include <stdlib.h>

typedef int element;	// 요소의 타입
typedef struct QueueNode {	// 큐의 노드의 타입 
	element data;
	struct QueueNode* link;
} QueueNode;

typedef struct {		// 큐 ADT 구현
	QueueNode* front, * rear;
} LinkedQueueType;

void init(LinkedQueueType* q)
{
	q->front = q->rear = 0;
}

int is_empty(LinkedQueueType* q)
{
	return (q->front == NULL);
}

int is_full(LinkedQueueType* q)
{
	return 0;
}

void enqueue(LinkedQueueType* q, element data)
{
	QueueNode* temp = (QueueNode*)malloc(sizeof(QueueNode));
	temp->data = data;
	temp->link = NULL;
	if (is_empty(q)) {
		q->front = temp;
		q->rear = temp;
	}
	else {
		q->rear->link = temp;
		q->rear = temp;
	}
}

element dequeue(LinkedQueueType* q)
{
	QueueNode* temp = q->front;
	element data;
	if (is_empty(q)) {
		fprintf(stderr, "스택이 비어있음\n");
		exit(1);
	}
	else {
		data = temp->data;
		q->front = q->front->link;
		if (q->front == NULL)
			q->rear = NULL;
		free(temp);

		return data;
	}
}
void print_queue(LinkedQueueType* q)
{
	QueueNode* p;
	for (p = q->front; p != NULL; p = p->link)
		printf("%d->", p->data);
	printf("NULL\n");
}

int main(void)
{
	LinkedQueueType queue;

	init(&queue);

	enqueue(&queue, 1);	print_queue(&queue);
	enqueue(&queue, 2);	print_queue(&queue);
	enqueue(&queue, 3);	print_queue(&queue);
	dequeue(&queue);	print_queue(&queue);
	dequeue(&queue);	print_queue(&queue);
	dequeue(&queue);	print_queue(&queue);

	return 0;
}

출처
C언어로 쉽게 풀어쓴 자료구조 - 천인구