[백준] 10845번 큐

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

 

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

 

'큐' 자료구조는  First In, First Out 의 구조를 가진다. 

따라서 스택과 달리 데이터 접근점이 두개(top, rear 혹은 left, right 혹은 front, back)가 필요하다.

데이터가 들어가는 지점을 하나 지정하고, 나오는 점을 하나 지정해야 한다.

 

 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef enum{
    PUSH,
    POP,
    SIZE,
    EMPTY,
    FRONT,
    BACK,
    UNKNOWN    
} CommandType;

void push(int **q_front, int **q_back); //정수 X를 큐에 넣는 연산이다.
int pop(int **q_front, int **q_back); //큐에서 가장 앞에 있는 정수를 빼고, 그 수를 리턴한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 리턴한다.
int size(int **q_front, int **q_back); //큐에 들어있는 정수의 개수를 리턴한다.
int empty(int **q_front, int **q_back); //큐가 비어있으면 1, 아니면 0을 리턴한다.
int front(int **q_front, int **q_back); //큐의 가장 앞에 있는 정수를 리턴한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 리턴한다.
int back(int **q_front, int **q_back); //큐의 가장 뒤에 있는 정수를 리턴한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 리턴한다.

CommandType getCommandType(const char* input){
    if (strcmp(input, "push") == 0 || strcmp(input, "PUSH") == 0)
        return PUSH;
    else if (strcmp(input, "pop") == 0 || strcmp(input, "POP") == 0)
        return POP;
    else if (strcmp(input, "size") == 0 || strcmp(input, "SIZE") == 0)
        return SIZE;
    else if (strcmp(input, "empty") == 0 || strcmp(input, "EMPTY") == 0)
        return EMPTY;
    else if (strcmp(input, "front") == 0 || strcmp(input, "FRONT") == 0)
        return FRONT;
    else if (strcmp(input, "back") == 0 || strcmp(input, "BACK") == 0)
        return BACK;
    else 
        return UNKNOWN;
}

int main(int argc, char *argv[]){
    int number_of_commands = 0;
    int i = 0, j = 0;
    char user_input_command[6];
    int *queue;
    int *q_front, *q_back;

    scanf("%d",&number_of_commands);

    if(number_of_commands > 10000 || number_of_commands < 1)
        return -1;

    queue = (int *)malloc(sizeof(int)*number_of_commands);
    q_front = queue;
    q_back = queue;

    for(i = 0; i < number_of_commands; i++){
        scanf("%s", user_input_command);
        CommandType cmd = getCommandType(user_input_command);
        
        switch(cmd){
            case PUSH:
                push(&q_front, &q_back);
                break;
            case POP:
                printf("%d\n",pop(&q_front, &q_back));
                break;
            case SIZE:
                printf("%d\n",size(&q_front, &q_back));
                break;
            case EMPTY:
                printf("%d\n",empty(&q_front, &q_back));
                break;
            case FRONT:
                printf("%d\n",front(&q_front, &q_back));
                break;
            case BACK:
                printf("%d\n",back(&q_front, &q_back));
                break;
            case UNKNOWN:
                break;
            default:
                printf("Error on switch.\n");
                return -1;                
        }

        //memset(user_input_command, 0, sizeof(user_input_command));
    }
    free(queue);
    return 0;
}

void push(int **q_front, int **q_back){
    int X = 0;
    scanf("%d",&X);
    if(X <= 100000 && X >= 1){
        **q_back = X;
        (*q_back)++; 
    }
    
}//정수 X를 큐에 넣는 연산이다.

int pop(int **q_front, int **q_back){
    if(*q_front == *q_back)
        return -1;
    int temp = **q_front;
    (*q_front)++;
    return temp;
} //큐에서 가장 앞에 있는 정수를 빼고, 그 수를 리턴한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 리턴한다.

int size(int **q_front, int **q_back){
    if(*q_back == *q_front)
        return 0;
    else
        return (*q_back - *q_front);// / sizeof(int)라 생각했으나, 컴파일러에서 포인터간의 차를 계산할때 자동으로 타입 크기로 나눠준다고 한다!;
} //큐에 들어있는 정수의 개수를 리턴한다.

int empty(int **q_front, int **q_back){
    return *q_front == *q_back;
} //큐가 비어있으면 1, 아니면 0을 리턴한다.

int front(int **q_front, int **q_back){
    if(*q_front != *q_back)
        return **q_front;
    else
        return -1;
} //큐의 가장 앞에 있는 정수를 리턴한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 리턴한다.

int back(int **q_front, int **q_back){
    if(*q_front != *q_back)
        return *(*q_back-1);
    else
        return -1;
} //큐의 가장 뒤에 있는 정수를 리턴한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 리턴한다.

 

 

enum을 활용하여 switch_case구문으로 메뉴를 구성하였다. (3개 이상의 if문은 컴파일러에 따라 비효율적일 수 있다고 한다)

 

위 코드의 로직대로 공간을 할당하면, 큐의 크기를 push할 때 확인하지 않아도 된다는 장점이 있지만, 명령의 수만큼 공간을 할당하므로 실제 사용하는 양에 비해서 불필요할 정도로 공간을 할당한다. 따라서, 최적화를 위해서는 push를 할 때마다 malloc하는 방식을 생각해 볼 수도 있을 것 같다.