연결리스트기반 큐구현

연결리스트기반 큐

큐의 헤더

ListBaseQueue.h 소스)

#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);

int QIsEmpty(Queue * pq);

void Enqueue(Queue * pq, Data data); // Enqueue 연산 함수

Data Dequeue(Queue * pq); // Dequeue 연산 함수

Data QPeek(Queue * pq);

#endif

큐의 함수정의

ListBaseQueue.c 소스)

#include <stdio.h>

#include <stdlib.h>

#include "ListBaseQueue.h"

void QueueInit(Queue * pq)

{

pq->front = NULL;

pq->rear = NULL;

}

int QIsEmpty(Queue * pq)

{

if(pq->front == NULL)

return TRUE;

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);

}

return pq->front->data;

}

큐를 활용한 Main함수

ListBaseQueueMain.c 소스)

#include <stdio.h>

#include "ListBaseQueue.h"

int main(void)

{

// Queue 생성 및 초기화

Queue q;

QueueInit(&q);

// 데이터 넣기

Enqueue(&q ,1);Enqueue(&q ,2);

Enqueue(&q ,3);Enqueue(&q ,4);

Enqueue(&q ,5);

// 데이터 꺼내기

while(!QIsEmpty(&q))

printf("%d ", Dequeue(&q));

return 0;

}