문과생이 이해한 연결된 큐

출처 : <c언어로 쉽게 풀어쓴 자료구조> + 학교 수업

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

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

typedef struct {
	QueueNode* front;  //삭제
	QueueNode* rear;   //삽입
}QueueType;

void init(QueueType* q) {
	q->front = NULL;
	q->rear = NULL;
}

/*void enqueue_first(QueueType* q, int item) {
	QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
	new_node->data = item;
	new_node->link = NULL;
	q->rear = new_node;
	q->front = new_node;
}*/

void enqueue(QueueType* q, int item) {
	QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
	new_node->data = item;
	new_node->link = NULL;
	if (q->front == NULL) {
		q->rear = new_node;
		q->front = new_node;
	}else {
		q->rear->link = new_node;
		q->rear = new_node;
	}
}

void dequeue(QueueType* q) {
	QueueNode* delete_node = q->front;
	q->front = q->front->link;
	free(delete_node);
}

void print(QueueType* q) {
	QueueNode* i = q->front;
	if (i != NULL) {
		for (i = q->front; i !=NULL; i = i->link)
			printf("%d ", i->data);
	}
	printf("\n");
}

int main() {
	QueueType q;
	init(&q);

	enqueue(&q, 10); print(&q);
	enqueue(&q, 20); print(&q);
	enqueue(&q, 30); print(&q);

	dequeue(&q); print(&q);
	dequeue(&q); print(&q);
	dequeue(&q); print(&q);

	return 0;
}

 

 이거 짜느라 몇 시간 걸린 듯... 책에도 없고 강의 자료도 부분 코드만 있어서ㅜㅜ 영구실 칭구들의 도움으로 짜버렸다♥

 

 

#main()

 

 일단 구조체는 총 2개를 썼다. 사실 스택 쓸 때도 2개 썼는데 귀찮아서 2개만 썻단 말임. 근데 이번에도 그러면  발전없을 것 같아서 눈물 머금고 2개로 짜봤다. 

 

 

 일단 QueueType 구조체 변수를 선언해주고 초기화 해준다. 

 사실 전역변수로 해도 상관없는데. 전역변수 사용을 자제해야 하는게. 전역변수 특성상 코드의 어디서든 수정될 수 있기 때문에 그 값이 훼손될 우려가 있다. 심지어 어디서 훼손됐는지 찾기 어려울 수 밖에... 그래서 번거로워도 값을 넘겨주는게 좋은 코드라 배웟따

 

 

#enqueue

 

 코드 보면 enqueue_first가 잇는데ㅋㅋㅋ 처음에 rear가 계속 new_node값을 가리켜야 하니까 front를 가장 처음 node를 가리키게 설정하려고 함수를 따로따로 만들었다. 근데 영구실 칭구가 딱 보더니 바로 enqueue 함수 안에 if문 만들어서 함수 하나로 끝내버림. 굳굳... 역시 연륜은 무시 못한다... 

 

 

 아무튼 

 

 일단 QueueNode를 동적 할당 해준다. 저 줄은 연결리스트 삽입 연산가면 각 연산이 무슨 연산인지 잘 나와있다. 그치만 나도 나중에 찾아보러 가기 귀찮을 것 같아서 첨부함..

 

 구조체는 연결리스트와 동일하고, 이게 30줄까지 동적할당하고 data와 link필드 채워넣은 후 메모리 상태이다. 

 

 

 현재 front가 NULL이니까 if문을 실행한다.

 

 

 요로코롬. 

 

 

~~두번째 enqueue(else문 실행했을 때)~~

 

#dequeue

 

이게 enqueue를 마친 메모리 상태. 여기서 데큐를 해보자. 

 

 

 

 쟈 41번 줄처럼 QueueNode를 참조하는 delete_node를 생성하고 q->front 즉 100'로 초기화 해준다. 

 

 

 

 그리고 42줄. q->front를 q->front 노드 즉 100'의 link 필드 200'로 변경한다. 

 

 

 

 그리고 delete_node가 가리키던 100'를 메모리에서 해제하고 함수가 끝나고 난 메모리 상태다. 

 

 

#print

 

 

 대망의 print문... 여기서도 엄청 헤맸따. i가 계속 널포인터 에러나서 Hㅏ......

 

 

 일단 메모리 상태는 이거라고 가정하고 print함수 ㄱㄱ

 

 

 이렇게 i라는 순회노드를 큐의 가장 앞부분에 있는 front로 초기화 해준다. 그리고 일단 처음에 front와 rear를 NULL로 초기화했으니까 혹시 front에 NULL이 들어있다면 print() 실행하지 않도록 조건문을 설정한다. 

 

 그 이후는 연결리스트와 동일하게 i가 NULL 즉, 연결리스트의 끝이 되기 전까지 i에 i가 가리키는 link 필드를 새로 저장하며 반복하면 된다.