큐 구조 설명 및 구현

 큐 란?

큐(Queue)란 자료구조는 앞서 배웠던 스택(Stack) 자료구조와는 달리 선입선출(First In, First Out: FIFO)의 구조를 지니고 있습니다. 한마디로 먼저 들어온 데이터는 먼저 나간다는 소리입니다. 예를 들면, 점심시간에 학생들이 점심을 먹으러 일렬로 줄을 서있다고 가정합시다. 줄을 선 순서대로 차례차례 급식을 받고 빠져나가죠? 이러한 구조를 지닌 자료구조가 바로 큐(Queue)라고 말할 수 있습니다.

큐는 크게 순환 큐와 링크드 큐로 나뉠수 있는데,

 

먼저 순환큐(Circular Queue)는 원소들을 옮기지 않고 반대로 전단과 후단의 유연하게 위치를 옮기는 방식인데, 

한 마디로 만약 후단이 배열 끝에 있을때 숫자가 삽입이되면,

숫자가 맨앞으로 옵니다.

그래서 순환큐를 표현할때는 보통 이렇게 원형으로 표시합니다

 

(하지만 여기서 문제점이 하나 생긴다. 바로 비어있음과 가득차있음을 구별하는 일인데,

먼저 비어있음은 전단과 후단이 같을경우로 구별한다. 하지만 여기서 또 문제가

하나더 발생하는데 바로 이번에는 비어있음과 가득참을 서로 구별못한다는 것이다.

그래서 일부러 더미 공간을 하나더 만들어서 전단 다음이 후단일 경우 가득찬 상태로 나타내게 하였다.)

그 다음 링크드 큐는   

장점이 공간이 필요하면 그때 메모리를 할당하여 공간을 만들고 만들어진 공간을 기존의 리스트에 추가하면 된다는 점입니다.   

필요없는 데이터는 삭제하고 중간에 끊기는 리스트를 앞뒤로 이어주면 리스트를 파괴하지 않고도 데이터 수정할 수 있습니다.

(링크드 큐(Linked Queue)는 용량에 구애받지 않고, 포인터로 연결하기 때문에 큐가 가득 차 있는지(포화상태), 큐가 비어있는지(공백상태)때문에 신경을 쓸 필요가 없다.)

구현

순환 큐

#include<stdio.h>
#define MAX 5
 
int arr[MAX];        //배열
int jendan = 0;            //전단
int hudan = 0;            //후단
int number = 0;                //데이터의 갯수
void input(int a) {
    hudan = (hudan + 1) % MAX;            //값 삽입 만약 5를 넘어설경우  다시 0
    if (jendan == hudan) {
        printf("데이터가 가득 찼습니다.\n");
    }
    else {
        number++;
        arr[hudan] = a;
    }
}
void bogi() {
    int i;
        for (i = 1; i <= number; i++) {
            printf(" %3d", arr[(jendan + i) % 5]);    //데이터 출력
        }
        printf("\n");
}
void Delete() {
    if (jendan == hudan) {
        printf("전단과 후단이 같아 삭제할수 없습니다\n");
    }
    else {
        number--;
        jendan = (jendan + 1) % MAX;
    }
}
int main() {
    int a, b, i;
    while (1) {
        getch();
        printf("1. 입력하기\n2. 현재 입력된값 확인하기 \n3. 삭제\n4. 나가기\n입력 : ");
        scanf("%d", &a);
        switch (a) {
        case 1: scanf("%d", &b); input(b);
            printf("전단 값 : %d, 후단 값 : %d\n", jendan, hudan);
            break;
        case 2: bogi();
            printf("전단 값 : %d, 후단 값 : %d\n", jendan, hudan);
            break;
        case 3: Delete();
            printf("전단 값 : %d, 후단 값 : %d\n", jendan, hudan);
            break;
        case 4: return 0;
        default: printf("입력하신 번호는 선택지에 없습니다\n");
        }
    }
    return 0;
}

링크드 큐

#include<stdio.h>
#define MAX 5
 
int Q[MAX] = { 0, };
int number = 0;
 
void add(int input){
        if (number == MAX)
        {
            printf("큐가 꽉 찼습니다");
            return 0;
        }
        Q[number] = input;//입력된 값입력
        number++;
    }
void Delete(){
        int j;
        Q[0] = 0;
        for (j = 1; j < MAX; j++)//앞으로 당김
            Q[j - 1] = Q[j];
        Q[4] = 0;
        number--;
    }
void bogi()    {
        int j;
        printf("큐의 저장상태\n\n");
        for (j = 0; j < MAX; j++)                //출력
            printf("%2d", Q[j]);    
        printf("\n");
        for (j = 0; j < MAX; j++)                //번호
            printf("%2d", j);
        printf("\n");
    }
int main(){
    while (1) {
        int a, b;
        getch();
        printf("  1. 추가\n  2. 현재 입력된값 확인하기 \n  3. 삭제\n  5. 나가기\n  입력 : ");
        scanf("%d", &a);
        switch (a) {
        case 1: scanf("%d", &b); add(b);
            break;
        case 2: bogi();
            break;
        case 3: Delete();
            break;
        case 4: return 0;
        default: printf("입력하신 번호는 선택지에 없습니다\n");    
        }
    }
    return 0;
}