[자료구조][C언어]큐(Queue)란?(4)_큐의 활용(백준10845번)

저번 시간에는 큐를 배열을 활용해 구현해 보았다. 이번엔 저번 시간에 구현한 큐를 가지고 활용해 보도록하자.

아래에 큐를 활용하기에 좋은 백준 문제가 하나 있다.

https://www.acmicpc.net/problem/10845

10845번: 큐

저번에 만든 원형큐를 이 문제에 맞게 변형해 보도록 하겠다.

 

enqueue는 push로, dequeue는 pop으로, isEmpty는 empty로, rear은 back으로 변형이 가능할 것이다

size는 front와 rear의 차이를 활용하면 나타낼 수 있다.

 

다만 주의해야 할 점이 입력의 형태와 자료형인데, 위 문제는 이므로 기존의 char 자료형으로 반환을 하고 받는 변수나 함수를 전부 int로 바꿔주어야 한다.

(char 자료형 범위: -128(= -2^7) ~ 127, int 범위: -2147483648(= -2^31) ~ 2147483647)

 

 

큐 구조체 정의

문제의 조건을 확인하면 명령의 수는 1~10000으로 최대 사이즈를 10003로 바꾸어 주면 된다.

또한 문제에서 주어지는 수의 크기 또한 1~100000이므로 char 배열 대신 해당범위의 수를 담을 수 있는 int 배열로 바꾸어 주면 된다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 10003

typedef struct
{
    int data[SIZE];
    int front, rear;
}QueueType;

void init(QueueType *Q)
{
    Q->front = Q->rear = 0;
}

 

push

push X: 정수 X를 큐에 넣는 연산이다.

이 연산은 기존에 구현해 놓았던 enqueue함수를 그대로 가져와 사용하면 된다.

void push(QueueType *Q, int e)
{
    if(isFull(Q))//큐가 가득 차있는지 확인
        printf("Queue is Full!\n");
    else //가득 차있지 않다면
    {
        Q->rear = (Q->rear + 1) % SIZE; //rear 이동
        Q->data[Q->rear] = e; //데이터 삽입
    }
}

 

pop

큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다

dequeue함수를 그대로 가져와서 사용하나, 큐가 비어있는 경우 오류 메시지를 띄우는 것 대신 -1을 반환하도록 바꾸어 주면 된다. char 자료형을 int 자료형으로 바꾸어 주는 거 잊지 말기!!

int pop(QueueType *Q)
{
    if(empty(Q))//큐가 비어 있는지 확인
    {
        //printf("Queue is Empty!\n");
        return -1;
    }
    Q->front = (Q->front + 1) % SIZE; //front 이동
    return Q->data[Q->front]; //제거한 값 반환
}

 

size

큐에 들어있는 정수의 개수를 출력한다.

기존에 구현되어 있던 front와 rear을 활용해 구현하면 된다.

front에서 얼마큼 가야 rear에 도달하는가?라고 생각하면 쉽다.

큐의 size = (rear - front + 배열의 크기) % 배열의 크기

위 식이 잘 이해가 되지 않을 수 있는데 그림을 보면 이해가 쉬울 것이다.

front 와 rear 만을 사용해 큐의 size 구하기

 

위 그림에서 4번을 보면 front는 0, rear은 3이므로 3 - 0 즉 3으로 3개가 들어있음을 알 수 있다.

하지만 원형큐는 순환적으로 돌아가기에 6번과 같이 front는 1, rear은 0이므로 단순히 빼기만 한다면 -1로 원하는 값을 얻을 수 없다.

큐의 크기를 얻고자 하면 rear에서 front을 뺀 값이 음수인 경우, 배열의 총크기를 더해주어야 한다.

음수가 아닌 경우에도 식을 적용하기 위해 rear - front 값에 배열의 총크기를 더한 뒤 배열의 총크기로 모듈러 연산을 해주면 쉽게 큐의 크기를 구할 수 있게 된다.

int size(QueueType *Q)
{
    return (Q->rear-Q->front+SIZE)%SIZE;
}

 

empty

큐가 비어있으면 1, 아니면 0을 출력한다.

기존의 isEmpty 함수를 그대로 이용하면 된다.

int empty(QueueType *Q)
{
    return Q->front == Q->rear;
}

 

front

큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

front의 정의를 이용, 배열의 front+1 인덱스를 가져온다.

int front(QueueType *Q)
{
    return Q->data[Q->front+1];
}

 

back

큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

rear의 정의를 이용, 배열의 rear 인덱스를 가져오면 된다.

int back(QueueType *Q)
{
    return Q->data[Q->rear];
}

 

main 함수 부분

각 연산들을 모두 구현해 놓았다면 메인함수에서는 최대 몇 개의 명령을 받을지 입력받고

주어지는 입력이 push, pop, size, empty, front, back 중 어느 명령인지 확인 후 각 명령을 수행하는 반복문을 만들면 된다.

(문자열의 비교를 위해 string.h의 strcmp를 사용하였다.)

int main()
{
    QueueType Q;
    init(&Q);
    int N;
    char command1[100];
    int command2;
    scanf("%d",&N);
    for(int i = 0; i < N; i++){
        scanf("%s",command1);
        //printf("%s\n",command1);
        
        if(0 == strcmp(command1,"push")){
            scanf("%d",&command2);
            push(&Q,command2);
        }
        else if(0 == strcmp(command1,"pop")){
            printf("%d\n",pop(&Q));
        }
        else if(0 == strcmp(command1,"size")){
            //printf("%d %d\n",Q.rear,Q.front);
            printf("%d\n",size(&Q));
        }
        else if(0 == strcmp(command1,"empty")){
            printf("%d\n",empty(&Q));
        }
        else if(0 == strcmp(command1,"front")){
            printf("%d\n",front(&Q));
        }
        else if(0 == strcmp(command1,"back")){
            printf("%d\n",back(&Q));
        }
    }
}

 

코드 정리 및 제출

구현한 것들을 정리하면 다음과 같은 코드가 나온다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 10003

typedef struct
{
    int data[SIZE];
    int front, rear;
}QueueType;

void init(QueueType *Q)
{
    Q->front = Q->rear = 0;
}

int empty(QueueType *Q)
{
    return Q->front == Q->rear;
}

int isFull(QueueType *Q)
{
    return Q->front == (Q->rear + 1) % SIZE;
}

void push(QueueType *Q, int e)
{
    if(isFull(Q))//큐가 가득 차있는지 확인
        printf("Queue is Full!\n");
    else //가득 차있지 않다면
    {
        Q->rear = (Q->rear + 1) % SIZE; //rear 이동
        Q->data[Q->rear] = e; //데이터 삽입
    }
}

int pop(QueueType *Q)
{
    if(empty(Q))//큐가 비어 있는지 확인
    {
        //printf("Queue is Empty!\n");
        return -1;
    }
    Q->front = (Q->front + 1) % SIZE; //front 이동
    return Q->data[Q->front]; //제거한 값 반환
}

int front(QueueType *Q)
{
    if(empty(Q))
        return -1;
    return Q->data[Q->front+1];
}

int back(QueueType *Q)
{
    if(empty(Q))
        return -1;
    return Q->data[Q->rear];
}

int size(QueueType *Q)
{
    return (Q->rear-Q->front+SIZE)%SIZE;
}

int main()
{
    QueueType Q;
    init(&Q);
    int N;
    char command1[100];
    int command2;
    scanf("%d",&N);
    for(int i = 0; i < N; i++){
        scanf("%s",command1);
        //printf("%s\n",command1);
        
        if(0 == strcmp(command1,"push")){
            scanf("%d",&command2);
            push(&Q,command2);
        }
        else if(0 == strcmp(command1,"pop")){
            printf("%d\n",pop(&Q));
        }
        else if(0 == strcmp(command1,"size")){
            //printf("%d %d\n",Q.rear,Q.front);
            printf("%d\n",size(&Q));
        }
        else if(0 == strcmp(command1,"empty")){
            printf("%d\n",empty(&Q));
        }
        else if(0 == strcmp(command1,"front")){
            printf("%d\n",front(&Q));
        }
        else if(0 == strcmp(command1,"back")){
            printf("%d\n",back(&Q));
        }
    }
    

}

 

백준 10845번 실행

위 코드 실행결과 쉽게 문제를 해결할 수 있었다.

 

이렇게 오늘 큐를 활용한 문제를 풀어보았다.

큐는 스택처럼 직접적으로 활용되는 알고리즘이 나오는 경우는 거의 없으나 추후 설명할 BFS에 활용되므로 잘 이해하고 있어야 한다.