[Data Structure] 연결리스트 응용 : 큐

연결리스트 큐

- front : 삭제(delete)

- rear : 삽입(insert)

- rear의 link 필드는 NULL로 설정해야 한다

- 초기 상태 : front == rear == NULL

- 공백 상태 : front == NULL 

 

 

[코드 - C]

#include <stdio.h>
#include <stdlib.h>
// 연결리스트를 이용한 큐

typedef int element;

typedef struct qnode {
	element data;
	struct qnode* link;
}qnode;

qnode* front = NULL; // 큐의 front(삭제와 관련)
qnode* rear = NULL; // 큐의 rear(삽입과 관련)

int is_empty() {
	return front == NULL; // 공백 상태이면 front == NULL
}

void enqueue(element item) { // 큐에 삽입 (rear 이용)
	qnode* new_node = (qnode*)malloc(sizeof(qnode));
	if (new_node == NULL) {
		fprintf(stderr, "메모리 할당 에러\n\n");
		return;
	}
	else {
		new_node->data = item;
		new_node->link = NULL;
		if (is_empty()) { // 공백 상태이면 new_node 자체가 front 이자 rear
			front = new_node;
			rear = new_node;
		}
		else {
			rear->link = new_node;
			rear = new_node;
		}
	}
}

element dequeue() { // 큐에서 삭제 (front 이용)
	if (is_empty()) {
		fprintf(stderr, "Error : Stack is empty\n\n");
		return;
	}
	else {
		qnode* removed = front;
		element item = removed->data;
		front = removed->link;
		if (front == NULL) rear == NULL;
		free(removed);
		return item;
	}
}

element peek() {
	if (is_empty()) {
		fprintf(stderr, "Error : Queue is empty\n\n");
		return;
	}
	else
		return rear->data;
}

void print_queue() {
	if (is_empty()) {
		fprintf(stderr, "Queue is empty\n\n");
		return;
	}
	else {
		qnode* p = front;
		printf("(front : delete) <- |");
		while (p) {
			printf(" %d ", p->data);
			p = p->link;
		}
		printf("| <- (rear : insert)\n\n");
	}
}

int main(void) {
	print_queue();
	printf(">>> enqueue 10\n"); enqueue(10);
	print_queue();
	printf(">>> enqueue 20\n"); enqueue(20);
	print_queue();
	printf(">>> enqueue 30\n"); enqueue(30);
	print_queue();
	printf(">>> enqueue 40\n"); enqueue(40);
	print_queue();
	printf(">>> dequeue\n>>> dequeue된 data : %d\n", dequeue());
	print_queue();
	printf(">>> dequeue\n>>> dequeue된 data : %d\n", dequeue());
	print_queue();
	printf(">>> dequeue\n>>> dequeue된 data : %d\n", dequeue());
	print_queue();
	printf(">>> dequeue\n>>> dequeue된 data : %d\n\n", dequeue());
	print_queue();
}