[C언어] 연결리스트를 이용하여 큐 구현하기

이번 포스팅에서는 큐를 이용하여 노드의 삽입, 삭제, 탐색 연산을 구현해보겠습니다.

 

삽입: enQueue()

삭제: deQueue()

탐색: peek()

이렇게 3가지로 나누어 구현해보겠습니다.

실행 예시

 

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int element;

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

typedef struct Qtype {
	Qnode* front;
	Qnode* rear;
}LQtype;

LQtype* createLinkedQueue() {
	LQtype* LQ = (LQtype*)malloc(sizeof(LQtype));
	LQ->front = NULL;
	LQ->rear = NULL;	
	return LQ;
}

int isEmpty(LQtype* LQ) {
	if (LQ->front == NULL) {
		return 1;
	}
	else {
		return 0;
	}
}

void printLQ(LQtype*LQ) {
	Qnode* temp;
	temp = LQ->front;

	printf("LQ의 value : ");
	do {
		printf(" %c ", temp->data);
		temp = temp->link;
	} while (temp != NULL);
	printf(" -> (NULL) \n\n");
}

void enQueue(LQtype* LQ, element item) {
	Qnode* newNode = (Qnode*)malloc(sizeof(Qnode));
	newNode->data=item;
	newNode->link = NULL;

	if (isEmpty(LQ)) { //공백 리스트인 경우
		LQ->front = newNode;
		LQ->rear = newNode;
	}
	else { //공백 리스트가 아닌 경우
		LQ->rear->link = newNode;
		LQ->rear = LQ->rear->link;
	}
}

element deQueue(LQtype* LQ) {
	Qnode* old;
	old = LQ->front;
	if (isEmpty(LQ)) { //공백 리스트인 경우
		printf("(제거할 큐가 없습니다)\n");
		return 0;
	}
	else { //공백 리스트가 아닌 경우
		printf("(제거하는 큐 값은 %c 입니다)\n", old->data);
		LQ->front = LQ->front->link;
		free(old);
	}
}

void peek(LQtype*LQ) {
	if (isEmpty(LQ)) {
		printf("peek() 값 오류 (공백 리스트를 호출하였습니다)\n");
	}
	else { //공백 리스트가 아닌 경우
		printf("peek()의 값은 %c 입니다\n\n", LQ->front->data);
	}
}


void main() {
	LQtype* LQ = createLinkedQueue();
	printf("연결 큐를 구현해보자\n");
	
	printf("A 삽입\n"); enQueue(LQ, 'A'); printLQ(LQ);
	printf("B 삽입\n"); enQueue(LQ, 'B'); printLQ(LQ);
	printf("C 삽입\n"); enQueue(LQ, 'C'); printLQ(LQ);

	printf("peek()함수 실행 : "); peek(LQ);

	printf("deQueue 1회 실행 "); deQueue(LQ); printLQ(LQ);
	printf("deQueue 2회 실행 "); deQueue(LQ); printLQ(LQ);
	printf("deQueue 3회 실행 "); deQueue(LQ); printLQ(LQ);
}