[c언어] FIFO(First in First Out) Linked Queue(연결리스트 큐)구현

앞에서 배운 Linked List를 활용해 Queue를 구현하였습니다.

Queue의 핵심 개념은 FIFO(First In First Out)입니다.

웬만하면 그림이 나와있는 개념서등을 보면서 학습을 권합니다.

 

그림을 머릿속에 떠올리면서 구현하면 훨씬 개념을 이해하기 쉽더라구요

 

#pragma once
#ifndef __LB_QUEUE_H__
#define __LB_QUEUE_H__

#define TRUE 1
#define FALSE 0

typedef int Data;

typedef struct _node {
	Data data;
	struct _node * next;
}Node;


typedef struct _lQueue {
	Node * front;
	Node * rear;
}LQueue;

typedef LQueue Queue;


void QueueInit(Queue * pq);//queue 초기화
int QIsEmpty(Queue * pq); //queue가 비었는지 확인 비었으면 TRUE 안비었으면 FALSE리턴

void Enqueue(Queue * pq, Data data); //queue에 집어넣기
Data Dequeue(Queue * pq); //queue에서 빼내면서 삭제
Data QPeek(Queue * pq); //queue에서 삭제하지않고 빼내기


#endif // !__LB_QUEUE_H__

먼저 헤더파일입니다.

 

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


void QueueInit(Queue * pq) {//큐 초기화
	pq->front = NULL;
	pq->rear = NULL;
}


int QIsEmpty(Queue * pq) {

	//큐가 비었으면 TRUE
	if (pq->front == NULL)//front==rear 이 논리로는 안되는건가? =>근데 저게 더 정확하니 저걸로 ㄱㄱ
		return TRUE;
	//안비었으면 FALSE 리턴
	else
		return FALSE;

}

void Enqueue(Queue * pq, Data data) {
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->next = NULL;
	newNode->data = data;

	if (QIsEmpty(pq)) {
		pq->front = newNode;
		pq->rear = newNode;

	}

	else {
		pq->rear->next = newNode;
		pq->rear = newNode;
		
	}
}





Data Dequeue(Queue * pq) {
	Node * delNode;
	Data retData;

	if (QIsEmpty(pq)) {
		printf("Queue memory error!");
		exit(-1);
	}

	delNode = pq->front;
	retData = delNode->data;
	pq->front = pq->front->next;

	free(delNode);
	return retData;
	
}


Data QPeek(Queue * pq) {
	
	if (QIsEmpty(pq)) {
		printf("Queue memory error!");
		exit(-1);
	}

	else {
		printf("%d", pq->front->data);
		
	}

	return pq->front->data;


}

int ListQueueCall() {
	Queue q;
	QueueInit(&q);

	for (int i = 1; i < 6; i++) {
		Enqueue(&q, i);
		//printf("%d", QPeek(&q));

	}

	printf("\n");


	while (!QIsEmpty(&q))
		printf("%d",Dequeue(&q));

	return 0;

}


int main() {
	ListQueueCall();

	return 0;
}

다음으로 본문파일입니다.

.c파일의 재사용을 위해 ListQueueCall이라는 함수를 따로 만들었습니다.

감사합니다 ^^