18258번 큐2 BOJ 백준 C언어

문제

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

명령은 총 여섯 가지이다.

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

입력

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

출력

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

구현

해당 문제는 명령의 수가 200만개이기 때문에 모든 명령을 push 했을 경우 배열의 수가 int로 가능한 25만을 초과할 수 있다. 따라서 다른 방식으로 풀어야만 하는데 동적할당을 하여 구현 해주는 방법과 링크드 리스트를 사용하는 방법이 있다. (STL라이브러리에서 지원해주는 queue는 제외)

큐라는 자료구조형은 스택과는 약간만 다를 뿐이다. 스택은 쌓아주는 개념이었다면 큐는 줄을 세우는 개념이다.

해당 그림과 같이 먼저 넣어 준 것을 빼지만 push할 경우 뒤에 쌓인다. 따라서 배열로 구현하여 다양한 명령을 수행하기 위해서는 front와 back의 인덱스를 확실히 파악하고 구현하는 것이 중요하다. 

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;

int main(void) {
    int *arr;
    arr = (int*)malloc(sizeof(int) * 2000000); // int 배열로는 25만개 까지만 할당가능
    int i, front = 0, back = 0, push, N;
    char str[6];
    scanf("%d", &N);
    for (i = 0; i < N; i++) {
        scanf("%s", str);
        if (strcmp(str, "push") == 0) {
            scanf("%d", &push);
            back++;
            arr[back] = push;
        }
        else if (strcmp(str, "pop") == 0) {
            if (back-front == 0) {
                printf("-1\n");
            }
            else {
                printf("%d\n", arr[front+1]);
                arr[front+1] = 0;
                front++;
            }
        }
        else if (strcmp(str, "size") == 0) {
            printf("%d\n", back-front);
        }
        else if (strcmp(str, "empty") == 0) {
            if (back-front == 0) {
                printf("1\n");
            }
            else {
                printf("0\n");
            }
        }
        else if (strcmp(str, "front") == 0) {
            if (back-front == 0) {
                printf("-1\n");
            }
            else {
                printf("%d\n", arr[front+1]);
            }
        }
        else if (strcmp(str, "back") == 0) {
            if (back-front == 0) {
                printf("-1\n");
            }
            else {
                printf("%d\n", arr[back]);
            }
        }
    }
}

정리

알고리즘에서 자주 사용되는 자료구조형 중 2번째 큐이다. 큐와 스택은 매우 유사해보이지만 분명하게도 다른 점을 가지고 있다. 스택과 큐의 차이점을 명확하게 파악하고 각 문제에 적용하는 것이 중요하게 보인다.