[백준] 10845번 큐 (C++)

문제

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

명령은 총 여섯 가지이다.

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

입력

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

예제 입력 1

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

출력

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

예제 출력 1

1
2
2
0
1
2
-1
0
1
-1
0
3

풀이

문제 해결 방법

이 문제는 큐를 직접 구현하거나 STL의 queue를 사용하여 해결할 수 있습니다. 두 가지 방법으로 구현해보겠습니다:

1. 배열을 이용한 구현:
   • 배열과 front, rear 변수를 사용하여 큐를 구현
   • push, pop, front, back 연산을 직접 구현
2. STL queue 사용:
   • C++ STL의 queue 컨테이너를 사용
   • 내장 함수들을 활용

두 방법 모두 각 연산의 시간 복잡도는 O(1)입니다.

코드

배열을 이용한 구현

// Queue 에서 front는 데이터를 추출할 위치를, rear는 데이터의 마지막 위치를 이야기 합니다.
// 따라서 데이터가 비어있을때는 rear의 값이 front보다 앞에 올 수 있습니다.
// 본 문제에서는 size를 썼지만, 실질적인 queue의 size는 rear-front+1로 계산됩니다.

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

int n;

int queue[10001];
int front, rear, size;

char cmd[10];
int arg;

int main()
{
    int i;
    scanf("%d", &n);

    //queue 초기화
    front = 0; rear = -1;

    for (i = 1; i <= n; i++)
    {
        scanf(" %s", cmd);

        if (!strcmp(cmd, "push"))
        {
            scanf(" %d", &arg);
            //rear 다음 위치에 데이터 추가 및 top위치 증가.
            queue[++rear] = arg;
            size++;
        }
        if (!strcmp(cmd, "pop"))
        {
            if (size == 0)
            {
                printf("-1\n");
                continue;
            }

            //front 위치에 원소 추출.
            printf("%d\n", queue[front++]);
            size--;
        }
        if (!strcmp(cmd, "size"))
        {
            printf("%d\n", size);
        }
        if (!strcmp(cmd, "empty"))
        {
            printf("%d\n", size == 0 ? 1 : 0);
        }
        if (!strcmp(cmd, "front"))
        {
            if (size == 0)
            {
                printf("-1\n");
                continue;
            }

            printf("%d\n", queue[front]);
        }
        if (!strcmp(cmd, "back"))
        {
            if (size == 0)
            {
                printf("-1\n");
                continue;
            }

            printf("%d\n", queue[rear]);
        }
    }
    return 0;
}

10845번 큐 (STL 버전)

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

int n;

std::queue<int> q;

char cmd[10];
int arg;

int main()
{
    int i;
    scanf("%d", &n);

    for (i = 1; i <= n; i++)
    {
        scanf(" %s", cmd);

        if (!strcmp(cmd, "push"))
        {
            scanf(" %d", &arg);

            q.push(arg);
        }
        if (!strcmp(cmd, "pop"))
        {
            if (q.empty())
            {
                printf("-1\n");
                continue;
            }

            printf("%d\n", q.front());
            q.pop();
        }
        if (!strcmp(cmd, "size"))
        {
            printf("%d\n", q.size());
        }
        if (!strcmp(cmd, "empty"))
        {
            printf("%d\n", q.empty() ? 1 : 0);
        }
        if (!strcmp(cmd, "front"))
        {
            if (q.empty())
            {
                printf("-1\n");
                continue;
            }

            printf("%d\n", q.front());
        }
        if (!strcmp(cmd, "back"))
        {
            if (q.empty())
            {
                printf("-1\n");
                continue;
            }

            printf("%d\n", q.back());
        }
    }
    return 0;
}