문제
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
- push X: 정수 X를 큐에 넣는 연산이다.
- pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 큐에 들어있는 정수의 개수를 출력한다.
- empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
- front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
#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하는 방식을 생각해 볼 수도 있을 것 같다.
