백준 10828 스택 [C]

이번 게시물에서는 자료구조 스택에 대하여 학습해 본 이후에 C++ STL을 통하여 백준 10828 스택 문제까지 풀여보려 합니다.

스택?

* 스택을 떠올리면, 가장 쉽게 떠올릴 수 있는 이미지가 컵입니다.
* 예를 들어, 동전 1개만 들어갈 수 있는 입구를 가진 컵에 빨간 동전, 초록 동전, 파랑 동전을 순서대로 넣었다고 가정해봅시다.
* 이때 컵을 기울여 동전을 꺼낸다고 가정을 하면 파랑 동전, 초록 동전, 빨강 동전 순서대로 다시 나오게 됩니다.
* 위와 같이, 스택은 가장 나중에 삽입한 원소를 가장 나중에 꺼낼 수 있는 LIFO(Last-In First-Out) 자료구조라고 생각해주시면 됩니다.

STL?

Standard Template Library 의 약자이며, 사용자가 자료구조와 알고리즘을 직접 모두 구현하지 않아도 편리하게 사용할 수 있는 라이브러리라 생각해주시면 됩니다.

STL - Stack

STL Stack을 사용하기 위해서는 헤더파일을 선언해주어야 합니다.

#include<stack>
using namespace std;

using namespace std; 이것은 나중에 stack을 선언할때마다 std::를 붙이지 않고 선언할 수 있도록 도와줍니다. 이제 헤더파일을 선언했으면, Stack을 만들어줍시다. 

stack<int> S;

정수형만을 담을 수 있는 스택을 만들어보았습니다. 다른 데이터 타입을 넣고 싶은 경우에는 <>안에 해당 데이터타입을 넣어주시면 됩니다.

Stack에는 크게 5가지 연산이 있습니다. 하나씩 살펴보도록 합시다.

원소를 삽입하는 push입니다.

S.push(3);

스택에 3이라는 정수형 데이터를 삽입하였습니다.

다음에는 스택의 맨 위에 있는 원소를 삭제하는 pop입니다.

S.pop();

 

스택에 들어있는 원소의 갯수를 리턴해주는 size입니다.

printf("%d", S.size());

위와 같은 코드로 해당 스택의 원소의 갯수를 출력할 수 있습니다.

다음은, 스택이 비어있는지 여부를 판단하는 empty입니다. 스택이 비어있다면 1이 리턴이 됩니다.

S.size()가 0인지 비교로도 구할 수 있습니다.

if(S.empty()) {
	// 스택이 비어있을 때 실행되는 구문
}

마지막으로, 스택의 가장 위에 있는 원소를 리턴하는 top입니다.

printf("%d", S.top());

위 5가지 연산을 이용하여 백준 10828번 문제를 풀어보도록 하겠습니다.

 

문제

https://www.acmicpc.net/problem/10828

10828번: 스택

코드

#include<stdio.h>
#include<stack>
#include<string.h>
using namespace std;
int N;
stack<int> st;

char str[10];
int main()
{
    int a;
    scanf("%d",&N);
    for(int ii=0;ii<N;ii++){
        scanf("\n%s",str);
        if(strcmp(str,"push")==0){
            scanf(" %d",&a);
            st.push(a);
        }
        if(strcmp(str,"top")==0){
            if(st.empty()){
                printf("-1\n");
            }else {
                printf("%d\n",st.top());
            }
        }
        if(strcmp(str,"empty")==0){
            printf("%d\n",st.empty() ? 1 : 0);
        }
        if(strcmp(str,"size")==0){
            printf("%d\n",st.size());
        }
        if(strcmp(str,"pop")==0){
            if(st.empty()){
                printf("-1\n");
            } else {
                printf("%d\n",st.top());
                st.pop();
            }
        }
    }
    return 0;
}