이번에는 큐를 알아보기로 해요.
큐는 순차적으로 자료를 보관하고 가장 최근에 보관한 자료를 꺼내는(FIFO, First In First Out) 버퍼예요.
여기에서는 버퍼의 크기가 정적인 배열로 정의하는 것을 먼저 구현할 거예요.
그리고 난 후에 이미 작성한 연결리스트를 이용하는 큐를 만들기로 해요.
배열로 큐를 정의할 때 자료를 보관하는 버퍼 외에 자료를 보관할 위치와 꺼낼 인덱스를 기억하고 있어요.
보관할 위치는 맨 뒤에 보관해서 rear라고 부르고 꺼낼 위치는 맨 앞이어서 front라 불러요.
그리고 큐에 자료를 보관하는 행위를 EnQueue 혹은 Put이라 불러요.
큐에서 자료를 꺼내는 행위는 DeDueue 혹은 Get이라 불러요.
그리고 배열로 큐를 구현할 때는 큐가 비었는지 혹은 꽉 찼는지 확인할 수 있는 기능을 제공하죠.
다음은 배열로 구현한 원형 큐예요.
원형 큐는 맨 뒤에 보관한 다음 다시 앞에 보관하는 큐를 말해요.
이와 같이 보관하면 큐가 꽉 찼을 때와 비었을 때 구분하지 못하는 문제가 있어요.
이를 해결하는 방법 중에 rear 다음이 front일 때 꽉 찬 것으로 취급하는 방법이 있어요.
여기에서는 이 방법을 사용하여 구현하였어요.
//원형 큐 - 버퍼 공간을 동적으로 생성, 정수 보관
#include <stdio.h>
#include <stdlib.h>
#define NEXT(index,QSIZE) ((index+1)%QSIZE) //원형 큐에서 인덱스를 변경하는 매크로 함수
typedef struct Queue //Queue 구조체 정의
{
int *buf;//저장소
int qsize;
int front; //꺼낼 인덱스(가장 오래전에 보관한 데이터가 있는 인덱스)
int rear;//보관할 인덱스
int count;//보관 개수
}Queue;
void InitQueue(Queue *queue,int qsize);//큐 초기화
int IsFull(Queue *queue); //큐가 꽉 찼는지 확인
int IsEmpty(Queue *queue); //큐가 비었는지 확인
void Enqueue(Queue *queue,int data); //큐에 보관
int Dequeue(Queue *queue); //큐에서 꺼냄
void DisposeQueue(Queue *queue);//큐 해제화
int main(void)
{
int i;
Queue queue;
InitQueue(&queue,10);//큐 초기화
for(i=1;i<=5;i++)//1~5까지 큐에 보관
{
Enqueue(&queue,i);
}
while( ! IsEmpty(&queue) )//큐가 비어있지 않다면 반복
{
printf("%d ",Dequeue(&queue));//큐에서 꺼내온 값 출력
}
printf("\n");
return 0;
}
void InitQueue(Queue *queue,int qsize)
{
queue->buf = (int *)malloc(sizeof(int)*qsize);
queue->qsize = qsize;
queue->front = queue->rear= 0; //front와 rear를 0으로 설정
queue->count = 0;//보관 개수를 0으로 설정
}
int IsFull(Queue *queue)
{
return queue->count == queue->qsize;//보관 개수가 qsize와 같으면 꽉 찬 상태
}
int IsEmpty(Queue *queue)
{
return queue->count == 0; //보관 개수가 0이면 빈 상태
}
void Enqueue(Queue *queue,int data)
{
if(IsFull(queue))//큐가 꽉 찼을 때
{
printf("큐가 꽉 찼음\n");
return ;
}
queue->buf[queue->rear] = data;//rear 인덱스에 데이터 보관
queue->rear = NEXT(queue->rear,queue->qsize); //rear를 다음 위치로 설정
queue->count++;//보관 개수를 1 증가
}
int Dequeue(Queue *queue)
{
int re=0;
if(IsEmpty(queue))//큐가 비었을 때
{
printf("큐가 비었음\n");
return re;
}
re = queue->buf[queue->front];//front 인덱스에 보관한 값을 re에 설정
queue->front = NEXT(queue->front,queue->qsize);//front를 다음 위치로 설정
queue->count--;//보관 개수를 1 감소
return re;
}
void DisposeQueue(Queue *queue)
{
free(queue->buf);
}
이 외에도 다양한 방법으로 큐를 구현할 수 있어요.
다음 글에서는 이미 앞에서 만들었던 연결리스트를 이용하는 큐를 설계하고 구현해 볼 거예요.