스택

스택(Stack)

스택은 한 쪽이 막힌 큐와 같다. 하노이의 탑을 생각해보면 좋다. 하노이의 탑은 내가 원하는 원판을 꺼내려면 그 위에 있는 원판을 먼저 꺼낸 뒤에 꺼낼 수 있다.

스택 자료구조도 마찬가지이다. 스택은 먼저 들어간 자료가 마자막에 나오는 LIFO방식을 따른다.

스택은 먼저 입력한 정보가 나중에 나와야 하는 DFS, 백 트래킹 등에 사용할 수 있다.

C++에는 스택 자료형이 존재하기 때문에 헤더 파일 하나만 추가한다면 스택을 사용할 수 있다.

아래는 스택의 선언, 사용 방법, 멤버 함수들이다.

c++

#include <stack>  // stack 헤더 파일 필요

stack<자료형> 스택 이름;
stack<int> s;  // 스택 선언

s.empty();  // 스택이 비어있다면 참, 아니면 거짓을 반환
s.size();  // 현재 스택에 들어있는 자료의 개수를 반환
s.top();  // 스택의 맨 위(마지막에 들어온 값) 반환
s.push();  //스택 위에 값 삽입
s.pop();  // 스택의 맨 위의 값 삭제

예시) 백준 #10828 스택

c++

#include <iostream>
#include <stack>
#include <cstring>
using namespace std;

stack<int> stc;

int main()
{
    int n;
    cin>>n;
    
    for(int i = 0 ; i < n ; i++)
    {
        string s;
        int num;
        cin>>s;

        if(s == "push")
        {
            cin>>num;
            stc.push(num);
        }

        if(s == "top")
        {
            if(!stc.empty())
            {
                cout<<stc.top()<<"\n";
            }
            else
            {
                cout<<-1<<"\n";
            }
        }

        if(s == "pop")
        {
            if(!stc.empty())
            {
                cout<<stc.top()<<"\n";
                stc.pop();
            }
            else
            {
                cout<<-1<<"\n";
            }
        }

        if(s == "size")
        {
            cout<<stc.size()<<"\n";
        }

        if(s == "empty")
        {
            cout<<stc.empty()<<"\n";
        }
    }
}

스택을 사용하는 기본 문제이다.