[백준] 10828번 스택 (C++)

문제

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

명령은 총 다섯 가지이다.

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

입력

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

예제 입력 1

14
push 1
push 2
top
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
top

출력

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

예제 출력 1

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

풀이

문제 해결 방법

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

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

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

코드

배열을 이용한 구현

// Stack 에서 top 이란 다음 데이터가 추가될 위치를 의미합니다.
// 이를 어레이로 구현할 때에 top은 실제 stack에 쌓여있는 데이터 개수와 동일한 의미를 가집니다.

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

int stack[10001],top;
int n;

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);
            //top위치에 데이터 추가 및 top위치 증가.
            stack[top++] = arg;
        }
        if(!strcmp(cmd,"pop"))
        {
            if(top==0)
            {
                printf("-1\n");
                continue;
            }
            //top-1 위치에서 데이터 추출
            printf("%d\n",stack[--top]);
        }
        if(!strcmp(cmd,"size"))
        {
            printf("%d\n",top);
        }
        if(!strcmp(cmd,"empty"))
        {
            printf("%d\n",top?0:1);
        }
        if(!strcmp(cmd,"top"))
        {
            if(top==0)
            {
                printf("-1\n");
                continue;
            }

            printf("%d\n",stack[top-1]);
        }
    }
    return 0;
}

STL을 이용한 구현

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

using namespace std;

int main()
{
    int n,m;
    char tmp[10];
    stack<int> st;
    scanf("%d",&n);
    for(;n--;)
    {
        scanf(" %s",tmp);
        if(strcmp(tmp,"push")==0)
        {
            scanf("%d",&m);
            st.push(m);
        }
        else if(strcmp(tmp,"pop")==0)
        {
            if(st.empty())
            {
                printf("-1\n");
            }
            else 
            {
                printf("%d\n",st.top());
                st.pop();
            }
        }
        else if(strcmp(tmp,"top")==0)
        {
            if(st.empty())
            {
                printf("-1\n");
            }
            else 
            {
                printf("%d\n",st.top());
            }
        }
        else if(strcmp(tmp,"size")==0)
        {
            printf("%d\n",st.size());
        }
        else
        {
            printf("%d\n",st.empty());
        }
    }
    return 0;
}