원형리스트기반 큐구현

원형리스트기반 큐란?

큐란 스택과 반대 개념으로 FIFO 첫 번째로 들어간 데이터가 첫 번째로 나오는 선입선출 구조이다. 큐는 front와 rear라는 변수가 각각 처음과 끝을 가리키는데 큐가 가득 찼는지 안찼는지를 알아낼 방법이 없어 배열을 꽉 채우지 않은 상태에서 구현하게 된다.

즉 배열이 최대값에서 -1 한만큼 값을 채우고 front와 rear를 확인하여 rear + 1한 값이 front와 같게 되면 큐가 가득 찬것으로 구분한다.

ex)

if(read+1 == front)     // 가득참

큐의 헤더

CirculaQueue.h 소스)

#ifndef __C_QUEUE_H__

#define __C_QUEUE_H__

#define TRUE 1

#define FALSE 0

#define QUE_LEN 100

typedef int Data;

typedef struct _cQueue

{

int front; // Dequeue때 사용하는 변수

int rear; // Enqueue때 사용하는 변수

Data queArr[QUE_LEN];

} CQueue;

typedef CQueue Queue;

void QueueInit(Queue * pq);

int QIsEmpty(Queue * pq);

void Enqueue(Queue * pq, Data data);

Data Dequeue(Queue * pq);

Data QPeek(Queue * pq);

#endif

큐의 함수정의

CircularQueue.c 소스)

#include <stdio.h>

#include <stdlib.h>

#include "CirculaQueue.h"

void QueueInit(Queue * pq) // 텅 빈 경우 front와 rear은 동일위치 가리킴

{

pq->front = 0;

pq->rear = 0;

}

int QIsEmpty(Queue * pq)

{

if(pq->front == pq->rear) // 큐가 텅 비었다면

return TRUE;

else

return FALSE;

}

int NextPosIdx(int pos)

{

if(pos == QUE_LEN-1) // 배열의 마지막 요소의 인덱스 값이라면

return 0;

else

return pos+1;

}

void Enqueue(Queue * pq, Data data)

{

if(NextPosIdx(pq->rear) == pq->front) // 큐가 꽉 찼다면,

{

printf("Queue Memory Error!");

exit(-1);

}

pq->rear = NextPosIdx(pq->rear); // rear를 한 칸 이동

pq->queArr[pq->rear] = data; // rear이 가리키는 곳에 데이터 저장

}

Data Dequeue(Queue * pq)

{

if(QIsEmpty(pq))

{

printf("Queue Memory Error!");

exit(-1);

}

pq->front = NextPosIdx(pq->front); // front를 한 칸 이동

return pq->queArr[pq->front]; // front가 가리키는 데이터 반환

}

Data QPeek(Queue * pq)

{

if(QIsEmpty(pq))

{

printf("Queue Memory Error!");

exit(-1);

}

return pq->queArr[NextPosIdx(pq->front)];

}

큐를 활용한 Main함수

CircularQueueMain.c 소스)

#include <stdio.h>

#include "CirculaQueue.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;

}