[6]

1. 큐

: 스택과 같이 데이터를 일시적으로 쌓아놓기 위한 자료구조. 스택과는 다른 선입선출 구조.

2. 링 버퍼 큐

링 버퍼 큐에 대한 링크

https://sustainable-dev.tistory.com/35

구현 코드

다음은 구조체와 함수를 정의한 IntQueue.h 파일이다.

#ifndef ___IntQueue
#define ___IntQueue

typedef struct {
        int max; // 최대 용량
        int num; // 요소 개수
        int front; // 프런트
        int rear; // 리어
        int *que; // 큐의 맨앞요소 포인터
} IntQueue;

int Initialize(IntQueue *q, int x); // 링 버퍼 정의

int Enque(IntQueue *q, int x); // 인큐

int Deque(IntQueue *q, int *x); // 디큐

int Peek(const IntQueue *q, int *x); // 데이터 피크

void Clear(IntQueue *q); // 초기화

int Capacity(const IntQueue *q); // 큐의 최대용량

int Size(const IntQueue *q); // 큐의 현재 크기

int IsEmpty(const IntQueue *q); // 큐가 비어있는지 판단

int IsFull(const IntQueue *q); //큐가 가득찼는지 판단

int Search(const IntQueue *q, int x); //큐에서 데이터 검색

void Print(const IntQueue *q); //큐 데이터 출력

void Terminate(IntQueue *q); //큐 초기화
#endif

다음은 함수들을 작성한 IntQueue.c 이다.

#include<stdio.h>
#include<stdlib.h>
#include "IntQueue.h"

int Initialize(IntQueue *q, int max){
        q->num = q->front = q->rear = 0;
        if((q->que = calloc(max, sizeof(int))) == NULL){
                q->max = 0;
                return -1;
        }
        q->max = max;
        return 0;
}

int Enque(IntQueue *q, int x){
        if(q->num >= q->max) return -1;
        else{
                q->num++;
                q->que[q->rear++] = x;
                if(q->rear == q->max)
                        q->rear=0;
                return 0;
        }
}

int Deque(IntQueue *q, int *x){
        if(q->num <= 0) return -1;
        else{
                q->num--;
                *x = q->que[q->front++];
                if(q->front == q->max) q->front=0;
                return 0;
        }
}

int Peek(const IntQueue *q, int *x){
        if(q->num <= 0)
                return -1;
        *x = q->que[q->front];
        return 0;
}
void Clear(IntQueue *q){
        q->num= q->front = q->rear = 0;
}

int Capacity(const IntQueue *q){
        return q->max;
}

int Size(const IntQueue *q){
        return q->num;
}

int IsEmpty(const IntQueue *q){
        return q->num;
}

int IsFull(const IntQueue *q){
        return q->num >= q->max;
}
int Search(const IntQueue *q, int x){
        int i, idx;
        for(i=0; i<q->num; i++){
                if(q->que[idx = (i+q->front) % q->max] == x)
                        return idx;
        }
        return -1;
}

void Print(const IntQueue *q){
        int i;
        for(i=0; i<q->num; i++)
                printf("%d",q->que[(i+q->front) % q->max]);
        putchar('\n');
}

void Terminate(IntQueue *q){
        if(q->que != NULL)
                free(q->que);
        q->max = q->num = q->front = q->rear = 0;
}

다음은 링 버퍼 큐에 대한 메인함수 IntQueueTest.c 이다.

#include<stdio.h>
#include "IntQueue.c"

int main(){
        IntQueue que;

        if(Initialize(&que, 64) == -1){
                puts("error:make que");
                return 1;
        }

        while(1){
                int m,x;
                printf("data su: %d / %d \n",Size(&que),Capacity(&que));
                printf("(1)Enque (2)Deque (3) Peek (4) Print (0)exit: ");
                scanf("%d",&m);

                if(m==0) break;
                switch(m){
                case 1:
                        printf("data: "); scanf("%d",&x);
                        if(Enque(&que,x)==-1) puts("\aerror: Enque");
                        break;
                case 2:
                        if(Deque(&que,&x) == -1) puts("\aerror: Deque");
                        else printf("Deque data is %d\n",x);
                        break;
                case 3:
                        if(Peek(&que,&x) == 1) puts("\aerror: peek");
                        else printf("peek data is %d",x);
                        break;
                case 4:
                        Print(&que);
                        break;
                }
        }
        Terminate(&que);
        return 0;
}

3. 링 버퍼의 활용

링 버퍼의 경우 max와 num의 값을 비교해주지 않을경우 최근에 입력된 데이터 n개만 저장되고 오래된 데이터는 버리게 된다.
크기가 10인 배열에서 요소를 12개 입력하게되면 처음에 입력한 2개의 요소는 사라지고 나중에 입력된 10개의 요소 데이터만 남아있게 된다