[C언어 자료구조] 4. 큐(Queue)

[C언어 자료구조] 4. 큐(Queue)

---

이번에는 큐를 알아보기로 해요.

큐는 순차적으로 자료를 보관하고 가장 최근에 보관한 자료를 꺼내는(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);

}

 

 

이 외에도 다양한 방법으로 큐를 구현할 수 있어요.

다음 글에서는 이미 앞에서 만들었던 연결리스트를 이용하는 큐를 설계하고 구현해 볼 거예요.

---

[C언어 자료구조] 4.1 큐 설계

[C언어 자료구조] 4.2 큐 구현

[C언어 자료구조] 4.3 큐 테스트

[C언어 자료구조] 4.4 큐 소스 코드