연결 리스트로 구현한 큐

연결된 큐

- 연결 리스트를 이용하여 구현한 큐를 연결된 큐(linked queue)라 함

- 배열로 구현한 큐와 달리 크기 제한 없음(pros)

- 배열로 구현한 큐에 비해 코드가 복잡(cons)

- 링크 필드가 추가되므로 메모리 공간 소모 多(cons)

 

- 단순 연결 리스트에 2개의 포인터를 추가한 구조

- front 포인터는 삭제, rear 포인터는 삽입과 관련

- 큐가 공백 상태일 경우 front와 rear는 NULL

- 큐의 요소들은 구조체로 정의되며 이 구조체는 데이터 필드와 링크 필드로 구성

---

연결된 큐 정의

typedef int element;
typedef struct QueueNode {
	element data;
	struct QueueNode* link;
} QueueNode;
typedef struct {	//큐 ADT 구현
	QueueNode* front;
	QueueNode* rear;
} LinkedQueueType;

---

삽입 연산

- 동적 메모리 할당을 통해 새로운 노드 생성, 데이터를 저장한 뒤 연결 리스트의 끝에 새로운 노드 추가

- 큐가 공백 상태이면(front=rear=NULL) front와 rear 모두 새로운 노드를 가리키게 해야 함

- 큐가 공백 상태가 아니면 rear가 가리키고 있는 노드의 링크 필드와 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;	//현재 rear의 link가 temp를 가리키게
		q->rear = temp;	//temp를 rear로 변경
	}
}

---

삭제 연산

- 연결 리스트의 front에서 노드를 꺼내는 연산

- 공백 상태라면 오류

- 공백 상태가 아니라면 front가 가리키는 노드를 temp가 가리키게 하고, front는 front의 link로 대입

- 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;
	QueueNode* rear;
} LinkedQueueType;

//초기화
void init(LinkedQueueType* q) {
	q->front = q->rear = 0;
}
//공백 상태 검출
int is_empty(LinkedQueueType* q) {
	return q->front == NULL;
}
//포화 상태 검출(필요x)
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;	//링크 필드 NULL로 설정
	if (is_empty(q)) {
		q->front = temp;
		q->rear = temp;
	}
	else {
		q->rear->link = temp;	//현재 rear의 link가 temp를 가리키게
		q->rear = temp;	//temp를 rear로 변경
	}
}
//삭제 함수
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;
	}
}
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;
}

>>