언어 자료구조 알고리즘/[C]디딤돌 자료구조와 알고리즘

[디딤돌 자료구조와 알고리즘] 5.3 큐(QUEUE)

언제나휴일 2016. 5. 23. 16:58
반응형

5.3 큐(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);

}

 

 

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

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


관련 게시글

[디딤돌 자료구조와 알고리즘] 5.3.1 큐(QUEUE) 설계

[디딤돌 자료구조와 알고리즘] 5.3.2 큐 구현 , 5.3.3 큐 테스트


다양한 형태의 큐

[언어 자료구조 알고리즘/C언어 예제] - 원형 큐 - 버퍼 크기 고정, 정수 보관, C언어 소스

[언어 자료구조 알고리즘/C언어 예제] - 원형 큐 - 버퍼 크기 고정, 정수 보관, C언어 소스

[언어 자료구조 알고리즘/C언어 예제] - 원형 큐 - 모든 공간 사용, 정수 보관, C언어 소스

[언어 자료구조 알고리즘/C언어 예제] - 원형 큐 - 버퍼 공간을 동적으로 생성, 정수 보관, C 언어 소스

[언어 자료구조 알고리즘/C언어 예제] - 원형 큐 - 동적 생성, 정수 보관, C언어 소스

[언어 자료구조 알고리즘/C언어 예제] - 원형 큐 - 버퍼 자동으로 확장, 정수 보관, C언어 소스

[언어 자료구조 알고리즘/C언어 예제] - 원형 큐 - 버퍼 공간 자동으로 할당, 동적 데이터 보관, C언어 소스

[언어 자료구조 알고리즘/C언어 예제] - 큐 - 연결리스트 이용, C언어 소스

[언어 자료구조 알고리즘/[C++]- 3.4 큐(Queue) [디딤돌 자료구조와 알고리즘 with C++]

[언어 자료구조 알고리즘/[C++] - 3.5 큐를 이용한 스케쥴러 시뮬레이션 [디딤돌 자료구조와 알고리즘 with C++]


반응형