[ C ] 백준 10845번 큐

 

 

문제

 

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

명령은 총 여섯 가지이다.

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

 

입력

 

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

 

출력

 

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

 

 

 

 

 

728x90

 

 소스코드

 

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

int queue[10000];
int queue_size=0;

void push(int push_data){
    queue[queue_size] = push_data;
    queue_size += 1;
}

int empty(){
    if(queue_size == 0){
        return 1;
    }
    return 0;
}

int pop(){
    if(empty()){
        return -1;
    }
    queue_size -= 1;
    return queue[0];
}

int front(){
    if(empty()){
        return -1;
    }
    return queue[queue_size-queue_size];
}

int back(){
    if(empty()){
        return -1;
    }
    return queue[queue_size-1];
}

void setting(){
    for (int i=0;i<queue_size;i++)
    {
        queue[i]=queue[i+1];
    }
}

int main(){

    int N = 0, push_data = 0;
    char command[5] = {0,};

    scanf("%d",&N);

    for(int i=0;i<N;i++){

        scanf("%s",command);

        if(!strcmp(command,"push")){
            scanf("%d",&push_data);
            push(push_data);
        }
        else if(!strcmp(command,"pop")){
            printf("%d\n",pop());
            setting();
        }
        else if(!strcmp(command,"empty")){
            printf("%d\n",empty());
        }
        else if(!strcmp(command,"size")){
            printf("%d\n",queue_size);
        }
        else if(!strcmp(command,"front")){
            printf("%d\n",front());
        }
        else if(!strcmp(command,"back")){
            printf("%d\n",back());
        }

    }


    return 0;
}

스택 문제에서 사용한 코드를 변형 및 추가하여 만들었다.

 

 

설명

 

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

int queue[10000];
int queue_size=0;

 

해더는 기본적인 stdio.h 와 string.h을 사용하였다.

string.h를 사용한 이유는 strcmp를 사용하여 입력받은 문자와 push, pop, size, empty, front, back을 비교하여 사용자 정의 함수를 불러서 사용하기 위해서 이다.

queue 배열과 queue 변수를 전역 변수로 선언하였다.

queue 변수는 처음 시작할 때 queue 배열에 아무 값이 없을 것이기 때문에 0으로 초기화를 했다.

 

int main(){

    int N = 0, push_data = 0;
    char command[5] = {0,};

    scanf("%d",&N);

    for(int i=0;i<N;i++){

        scanf("%s",command);

        if(!strcmp(command,"push")){
            scanf("%d",&push_data);
            push(push_data);
        }
        else if(!strcmp(command,"pop")){
            printf("%d\n",pop());
            setting();
        }
        else if(!strcmp(command,"empty")){
            printf("%d\n",empty());
        }
        else if(!strcmp(command,"size")){
            printf("%d\n",queue_size);
        }
        else if(!strcmp(command,"front")){
            printf("%d\n",front());
        }
        else if(!strcmp(command,"back")){
            printf("%d\n",back());
        }

    }


    return 0;
}

 

main에서는 반복의 관한 N 변수와 push로 입력받는 데이터의 값을 받아주는 push_data 변수

그리고 push, pop, empty, size, front, back 중 어떤 함수를 불러올 것인지 입력을 받아오는 command 배열이 있다.

 

void push(int push_data){
    queue[queue_size] = push_data;
    queue_size += 1;
}

int empty(){
    if(queue_size == 0){
        return 1;
    }
    return 0;
}

int pop(){
    if(empty()){
        return -1;
    }
    queue_size -= 1;
    return queue[0];
}

int front(){
    if(empty()){
        return -1;
    }
    return queue[queue_size-queue_size];
}

int back(){
    if(empty()){
        return -1;
    }
    return queue[queue_size-1];
}

void setting(){
    for (int i=0;i<queue_size;i++)
    {
        queue[i]=queue[i+1];
    }
}

 

사용자 정의 함수로는 push, empty, pop, front, back, setting 이 있다. size 함수를 만들지 않은 이유는 queue_size를 출력만 하면 끝이기 때문에 딱히 만들 필요가 없다고 생각하여 만들지 않았다.

 

void push(int push_data){
    queue[queue_size] = push_data;
    queue_size += 1;
}

 

push 함수에서는 push_data변수의 값을 받아와서 queue배열 queue_size(카운터의 역할도 함께 함) 번째 요소에 push_data 값을 넣어준다. 그 후 배열에 값이 추가되었기 때문에 queue_size에 값을 1 더한다.

 

int empty(){
    if(queue_size == 0){
        return 1;
    }
    return 0;
}

 

empty 함수에서는 queue 배열에 값이 있는지 없는지만 판단해 주면 되는 함수이기 때문에 카운터의 역할을 하고 있는

queue_size 함수값이 0인지 아닌지만 확인해서 값을 반환해 주도록 했다.

 

int pop(){
    if(empty()){
        return -1;
    }
    queue_size -= 1;
    return queue[0];
}

 

pop 함수에서는 queue 배열에서 가장 앞에 값(가장 먼저 입력한 값)을 출력하는 역할의 함수이다.

문제에서 queue 배열에 값이 없을 경우 -1을 출력하라는 부분이 있는데 이것은 empty 함수에서 queue_size 값이 0인지

확인하는 것으로 대체 가능하기 때문에 여기서도 사용했다. 만약 queue 배열에 값이 없다면 (만약 queue_size가 0이라면) -1 값을

반환하고 함수가 끝난다. 아닐 경우 가장 마지막에 입력한 값을 출력하고 queue_size에 값을 1 마이너스한다.

 

int front(){
    if(empty()){
        return -1;
    }
    return queue[queue_size-queue_size];
}

 

front 함수도 마찬가지로 empty 함수를 이용하여 queue 배열에 값이 있는지 없는지 확인해 주었다.

front 함수는 가장 앞에 있는 값(가장 먼저 입력한 값)을 출력해주는 함수이기 때문에 queue_size - queue_size는 0이므로

배열에 0번째 (첫 번째) 요소 값을 반환하게 된다.

 

int back(){
    if(empty()){
        return -1;
    }
    return queue[queue_size-1];
}

 

back 함수도 마찬가지로 empty 함수를 이용했다.

back 함수는 가장 뒤에 있는 값(마지막에 입력한 값)을 출력해주는 함수이기 때문에 queue_size - 1 요소 값을 반환한다.

push 함수에서 queue 배열에 push_data를 넣은 후 queue_size를 +1 하기 때문에 queue_size - 1을 반환해야

마지막에 입력한 값을 반환하는 것이다.

 

void setting(){
    for (int i=0;i<queue_size;i++)
    {
        queue[i]=queue[i+1];
    }
}

 

큐 문제는 스택 문제와 다르게 가장 앞에 있는 값(가장 먼저 입력한 값)을 출력하기 때문에

가장 앞에 있는 값을 출력한 후 재 정렬을 할 필요가 있다.

queue 배열에 0번째 요소 값을 없애야 하기 때문에 1번째 값을 0번에, 2번째 값을 1번에, 3번째 값을 2번에...... 이것을 반복하여

요소 값을 한 칸씩 내린다. 그러면 0번째 값은 사라지고 나머지  값들은 배열에 0번째부터 재 정렬된다.

 

큐 구조도 스택 구조만큼 중요하다. 또 정리하여 공부하자!!!

 

 

www.acmicpc.net/problem/10845

10845번: 큐