백준_10845_큐(queue)

 

 

큐를 구현하는 문제입니다.

 

 

 

큐의 개념)

큐는 먼저 넣은 데이터가 먼저 나오는 선입선출(FIFO)의 형태를 가지고 있습니다.

 

나중에 넣은 데이터가 먼저 나오는 스택과는 정반대의 성질을 지니고 있죠. ( 스택에 대해서는 추후에 정리해보겠습니다 )

 

큐에서 front와 rear은 데이터의 시작과 끝 위치를 나타냅니다.

 

rear을 이용해 가장 나중에 최근에 데이터에 접근할 수 있고, front를 통해 가장 나중에 들어간 데이터에 접근할 수 있습니다. 

 

 

큐의 종류)

1. 선형 큐(Linear Queue) : 가장 기본적인 막대기 형태의 큐. 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 있습니다.

 

2. 원형 큐(Circular Queue) : 선형 큐의 단점을 보완한, front 와 rear가 연결되어 있는 형태입니다.

 

3.우선순위 큐(Priority Queue) : 데이터를 넣을 때 우선순위를 매겨 정렬해 넣는 큐입니다.

 

 

원형 큐를 이용하여 문제를 풀어보겠습니다.

 

 

풀이)

 

우선, 모든 함수에서 큐를 이용하기 편하도록 전역 변수로 큐를 만들고, 큐를 초기화 하는 함수까지 작성하였습니다.

#define S 100000

int queue[S];    //큐 생성
int frt, rear;   //front는 문제에서 명령어로 사용해서 frt로 대체

void init_queue()    //큐 초기화
{
    frt = rear = 0;
}

 

이제 문제에 나온 명령어들을 차례대로 구현해주면 됩니다.

 

 

PUSH)

int push(int k)
{
    if ((rear + 1) % S == frt)
    {
        return -1;
    }
    else
    {
        queue[rear] = k;
        rear++;
        rear %= S;

        return 1;
    }
}

push 값을 입력받아서 queue[rear]에 입력받은 값을 집어넣고 rear을 다음 칸으로 옮겨줍니다.

rear%=S; 를 해준 이유는 원형 큐이기 때문에 계속 순환시키기 위해서입니다.

 

만약, 값을 계속 넣다가 rear 다음 칸이 front 가 된다면, 그때는 큐가 가득 찬 상태이므로 -1을 반환합니다.(overflow)

rear==frt 가 아닌 이유 : 큐는 frt와 rear 값을 구분할 공백 한 칸이 필요하기 때문입니다.

 

코드만 보고 잘 이해가 안되실 수 있습니다.

 

이해가 안되신다면, 아래 그림과 모듈러를 생각해 보시면 보다 쉽게 이해하실 수 있을 겁니다.

 

https://www.shiksha.com/online-courses/articles/circular-queue-in-data-structure/

Circular Queue in data structure - Shiksha Online

 

 

 

POP)

void pop()
{
    int k;
    if (frt == rear)
    {
        printf("-1\n");
    }
    else
    {
        k = queue[frt];
        frt++;
        frt %= S;

        printf("%d\n", k);
    }
}

 

push 함수를 이해하셨다면, pop함수는 쉽게 느껴지실겁니다.

pop 함수를 실행시키면, 가장 먼저 들어간 값이 출력되고 frt를 1 증가시킵니다.

 

만약 모든 값을 pop 해서 빈 큐가 된다면, frt와 rear가 같은 위치에 있겠죠.

 

그래서 그 경우 -1을 출력합니다.

 

 

SIZE)

void size()
{
    int count = 0;
    for (int i = frt; i < rear;)
    {
        count++;

        i++;
        i %= S;
    }
    printf("%d\n", count);
}

 

큐에 들어있는 정수의 개수를 출력해주는 함수입니다.

 

큐의 성질을 생각하면 쉽습니다.

 

각 값의 위치는

가장 최근에 들어온 값+1 = rear 이고,

가장 먼저 들어온 값 = frt  이므로

 

큐 배열의 frt부터 rear-1까지 몇 개인지 count하면 됩니다.

 

 

 

EMPTY)

void empty()
{
    if (rear == frt)
    {
        printf("1\n");
    }
    else
    {
        printf("0\n");
    }
}

 

큐가 비어있으면 1, 아니면 0을 출력해주는 함수입니다.

 

위에서 push, pop 함수를 만들 때, 그림을 보며 원형 큐의 성질에 대해 이야기했습니다.

 

rear==front 라면 빈 큐이므로 1을 출력하고, 아니라면 0을 출력합니다.

 

 

FRONT, BACK)

void front()
{
    if (rear == frt)
    {
        printf("-1\n");
    }
    else
    {
        printf("%d\n", queue[frt]);
    }
}

void back()
{
    if (rear == frt)
    {
        printf("-1\n");
    }
    else
    {
        printf("%d\n", queue[rear - 1]);
    }
}

 

큐의 가장 앞에 위치한 정수를 출력하는 front 함수, 가장 뒤에 위치한 정수를 출력해주는 back 함수입니다.

 

frt 와 rear 가 처음과 마지막 값의 위치를 나타내기 때문에 쉽습니다.

 

 

전체 코드)

#include <stdio.h>
#include <string.h>
#define S 100000

int queue[S];
int frt, rear;

void init_queue()
{
    frt = rear = 0;
}

void clear_queue()
{
    frt = rear;
}

int push(int k)
{
    if ((rear + 1) % S == frt)
    {
        return -1;
    }
    else
    {
        queue[rear] = k;
        rear++;
        rear %= S;

        return 1;
    }
}

void pop()
{
    int k;
    if (frt == rear)
    {
        printf("-1\n");
    }
    else
    {
        k = queue[frt];
        frt++;
        frt %= S;

        printf("%d\n", k);
    }
}

void size()
{
    int count = 0;
    for (int i = frt; i < rear;)
    {
        count++;

        i++;
        i %= S;
    }
    printf("%d\n", count);
}

void empty()
{
    if (rear == frt)
    {
        printf("1\n");
    }
    else
    {
        printf("0\n");
    }
}

void front()
{
    if (rear == frt)
    {
        printf("-1\n");
    }
    else
    {
        printf("%d\n", queue[frt]);
    }
}

void back()
{
    if (rear == frt)
    {
        printf("-1\n");
    }
    else
    {
        printf("%d\n", queue[rear - 1]);
    }
}

int main(void)
{
    init_queue();
    int N;
    int data = 0;
    scanf("%d", &N);

    char word[6];
    for (int i = 0; i < N; i++)
    {
        char word[6];
        scanf("%s", word);
        getchar();

        if (strcmp(word, "push") == 0)
        {
            scanf("%d", &data);
            push(data);
        }
        else if (strcmp(word, "pop") == 0)
        {
            pop();
        }
        else if (strcmp(word, "size") == 0)
        {
            size();
        }
        else if (strcmp(word, "empty") == 0)
        {
            empty();
        }
        else if (strcmp(word, "front") == 0)
        {
            front();
        }
        else if (strcmp(word, "back") == 0)
        {
            back();
        }
    }

    return 0;
}

 

main 함수에서는 strcmp를 통해 어떤 명령이 입력되었는지를 판별하였습니다.