(C언어)16.큐(Queue)

<큐>

큐는 터널이라고 보면 된다. 아주 좁은 터널.

어릴적에 놀이터에서 원통을 눕힌 모양(이하 터널모양)에서 놀아본 기억이 있을것이다.

상상해보자.

한명이 터널 입구로 들어간다.(여기서 터널은 오로지 한사람만 지나갈 수 있고 터널의 길이는 5명밖에 못들어간다.)

그 한명이 터널 출구 바로 전에서 대기한다.

또다른 한명이 터널 입구로 들어간다.

먼저 들어간 아이 바로 뒤에서 대기한다.

이렇게 3번을 더 반복하면 터널이 꽉찬다.

여기서 나와! 를 외치면 가장 먼저 터널로 들어간 아이 한명이 나온다.

나머지 아이들은 한칸씩 전진한다.

이렇게 4번을 더 나와!를 외치면 모두가 나오게 된다.

이걸 메모리를 이용해서 말해보자면:

데이터 하나가 큐로 들어간다.(여기서 큐는 일정한 메모리마다 한명씩 들어갈 수 있고, 큐의 길이는 5이다.)

그 데이터는 큐의 front위치이다.(여기서 그 데이터는 큐의 rear위치이기도 한다.)

또다른 데이터가 큐로 들어간다.

먼저 들어간 데이터 뒤에 위치한다.(이 데이터는 큐의 rear위치가 된다.)

3번 반복하면 큐가 꽉찬다.

(이때 큐에 데이터를 집어넣으려고 하면 overflow가 발생한다.)

여기서 GET!을 외치면 가장 먼저 큐에 들어간 데이터가 나온다.

나머지 데이터들은 한칸씩 front쪽으로 이동한다.

이렇게 4번을 GET하면 큐가 비게 된다(empty).

PUSH : 값 넣기. 이 값이 곧 rear가 된다.

GET : front에 있던 값을 빼내기. 그 다음에 있던 데이터가 front가 된다.

SHOW : 현재 큐상황을 보여준다.

구현 : 

#include <stdio.h>
 
int que[10];
int cnt=-1;
 
void put(int num, int *rear){
    if(cnt==9){
        printf("\n\nOVER FLOW\n\n");
        return;
    }
    else{
        que[++cnt]=num;
        rear=&que[cnt];
        return;
    }
}
 
void get(int *front){
    int i;
    if(cnt==-1){
        printf("값이 없습니다\n");
        return;
    }
    else
        for(i=0; i<cnt; ++i){
            que[i]=que[i+1];
        }
        --cnt;
        front=&que[0];
}
 
void show(){
    int i;
    for(i=cnt; i>=0; --i){
        printf("%d =====> %d\n", i, que[i]);
    }
    return;
}
 
int main(){
    int input, i, input_num;
    int *front, *rear;
    printf("기본 자료 개수 입력 : ");
    scanf("%d", &input);
    cnt+=input;
    for(i=0; i<input; ++i){
        printf("queue[%d] : ",i);
        scanf("%d", &input_num);
        que[i]=input_num;
    }
    front=&que[0];
    rear=&que[cnt];
    while(1){
        printf("\n\n0 : 종료\n");
        printf("1 : PUT\n");
        printf("2 : GET\n");
        printf("3 : SHOW\n");
        printf("0~3 선택 : ");
        scanf("%d", &input);
        if(input==0){
            return 0;
        }
        else if(input==1){
            printf("집어넣을 값 : ");
            scanf("%d", &input_num);
            put(input_num, rear);
        }
        else if(input==2){
            get(front);
        }
        else if(input==3){
            show();
        }
    }
}