3. Queue

1. Queue란?

- linear list in which data can only be inserted at one end

(한 쪽 끝에서만 데이터가 들어가지는 연결 리스트)

- has rear and front (rear와 front를 가짐)

- ensures that data are processed in the order in which they are received (FIFO)

(들어온 순서대로 데이터가 , first in first out)

 

Operations

1) Create Queue

2) Enqueue

3) Dequeue

4) Destroy Queue

 

2. 구현

이번에는 큐 안에 저장될 데이터를 기본 데이터형으로 하지 않고 바로 구조체로 만들어보았다.

 

student.c & student.h

기존에 정의된 것과 같음

// student.h
#include <stdio.h>

typedef struct student {
	char name[10];
	int age;
}Student;

void printStudent(Student* stu);
int compareStudent(Student* stu1, Student* stu2);
Student* createStudent(char* n, int a);

// student.c
#include <stdio.h>
#include <string.h>
#include "Student.h"

void setStudent(Student* stu, char* n, int a) {
	strcpy_s(stu->name, 10, n);
	stu->age = a;
}

void printStudent(Student* stu) {
	printf("name: %s, age: %d \n", stu->name, stu->age);
}

int compareStudent(Student* stu1, Student* stu2) {
	if (stu1->age == stu2->age)
		return 1;
	else
		return 0;
}
// allocate memory for Student structure, set name and age
Student* createStudent(char* n, int a) {
	Student* stu = (Student*)malloc(sizeof(Student));
	strcpy_s(stu->name, 10, n);
	stu->age = a;

	return stu;
}

queue.h

#include <stdio.h>
#include "student.h"

#define TRUE 1
#define FALSE 0

typedef Student LData;

typedef struct node {
	
	LData* data;
	struct NODE* next;
	
}NODE;

typedef struct myqueue {
	NODE* front;
	NODE* rear;
	int count;
	//int size;
}Queue;

Queue* createQ();
void insertQ(Queue* q, LData* data);
LData retrieveQ(Queue* q);
int isEmpty(Queue* q);
void printQ(Queue* q);
void destroyQ(Queue* q);

 

queue.c

- 이번에는 queue의 사이즈를 특별히 지정하지 않았다.

- retrieveQ()의 반환값을 LData로 한 것은 retrieve 시 노드를 없앨 때 노드의 data부분도 free 해줘야 하기 때문에, 포인터를 반환하는 것이 아니라 데이터 자체를 반환하는 것이 낫겠다고 판단함. 대신에 main에서 printStudent()를 호출할 때 LData자체를 넘겨주는 것이 아니라, 그 주소값을 넘겨줬다.(printStudent()가 LData포인터를 매개변수로 받기 때문)

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

#include "queue.h"

Queue* createQ() {

	Queue* q = (Queue*)malloc(sizeof(Queue));
	if (q != NULL) {
		q->front = NULL;
		q->rear = NULL;
		q->count = 0;
	}
}

void insertQ(Queue* q, LData* data) {

	NODE* newNode = (NODE*)malloc(sizeof(NODE));
	if (newNode != NULL) {
		newNode->next = NULL;
		newNode->data = data;
	}
	if (isEmpty(q)) {
		q->front = newNode;
	}
	else {
		q->rear->next = newNode;
	}
	q->rear = newNode;
	q->count++;
}

LData retrieveQ(Queue* q) {

	NODE* temp;
	LData tempd;

	if (isEmpty(q)) {
		printf("The queue is empty \n");
		return;
	}
	temp = q->front; // copy to free memory
	tempd = *(q->front->data); // copy to return data
	q->front = q->front->next; // reset front
	free(temp->data); // free memory of the data inside node
	free(temp); // free node memory
	q->count--;
	return tempd;
}



int isEmpty(Queue* q) {
	if (q->count == 0)
		return TRUE;
	else
		return FALSE;
}

void printQ(Queue* q) {

	printf("print Queue: \n");
	NODE* temp = q->front;
	for (int i = 0; i < q->count; i++) {
		printStudent(temp->data);
		temp = temp->next;
	}
	printf("\n");
}
void destroyQ(Queue* q) {
	
	NODE* temp = NULL;
	while (q->front != NULL) {
		temp = q->front;
		q->front = q->front->next;
		free(temp->data);
		free(temp);
	}
	free(q);
	printf("Queue destroyed! \n");

}

main.c

#include <stdio.h>
#include "queue.h"

int main(void) {

	// create queue
	Queue* myq = createQ();

	// insert data into queue
	insertQ(myq, createStudent("nyam", 20));
	insertQ(myq, createStudent("oyam", 21));
	insertQ(myq, createStudent("pyam", 22));
	insertQ(myq, createStudent("ryam", 23));
	printQ(myq); // check if data are successfully inserted

	// retrieve data from queue
	LData ret_d = retrieveQ(myq);
	printf("retrieved data) ");
	printStudent(&ret_d);
	printf("\n");
	printQ(myq); // check if the retrieved data is successfully deleted

	// destroy queue
	destroyQ(myq);

	return 0;

}

결과