큐 연결리스트로 구현하기

연결리스트로 큐를 구현하는 것은 그리 어렵지 않다

헤더파일

#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);
Data DeQueue(Queue *pq);
Data QPeek(Queue *pq);

#endif

소스파일

#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->data = data;
   newNode->next = NULL;

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

Data DeQueue(Queue *pq)
{
   Node *rnode = pq->front;
   Data rdata = rnode->data;

   if (QIsEmpty(pq))
   {
      printf("Queue Memory Error!");
      exit(-1);
   }

   pq->front = pq->front->next;
   free(rnode);

   return rdata;
}

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

   return pq->front->data;
}

메인파일

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

int main()
{
   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));
   printf("\n");
   return 0;
}

결과

1 2 3 4 5