(매일 BOJ) C++ 10828번 스택

이번 문제는 실버 4 난이도 10828번 스택 문제이다.

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

 

이 문제의 접근법부터 알아보자.

이 문제는 표준 입력으로 주어지는 명령어에 따라 스택에 값을 넣거나(push), 맨 위 값을 빼거나(pop), 현재 스택의 크기(size), 스택이 비었는지(empty), 맨 위 값(top)을 조회하는 기능을 차례대로 수행하고, 각 명령의 결과를 요구하는 대로 즉시 출력하는 구현 문제이기에 스택이 비어 있을 때 pop이나 top 명령이 들어오면 -1을 출력해야 하며, 나머지 연산은 스택 자료구조의 기본 동작에 맞게 처리하면 된다.

 

따라서 C++  라이브러리 중 stack 라이브러리를 사용하여 구현하면 해결되는 간단한 구현 문제이다.

 

여기서 나오는 스택에 대해 알아보자

 

스택(stack)

스택(stack)은 후입선출(LIFO, Last-In First-Out) 방식으로 동작하는 자료구조
즉, 가장 나중에 넣은 데이터가 가장 먼저 나오는 구조다.

주요 특징

• 한쪽 끝(맨 위, top)에서만 데이터의 추가(push)와 제거(pop)가 일어남
• 맨 위(top) 원소만 접근 가능
• 구조상 삽입/삭제가 빠름 시간복잡도(O(1))

주요 연산

• push(x): x를 스택의 맨 위에 추가
• pop(): 맨 위의 원소를 제거
• top(): 맨 위의 원소를 확인(제거는 안 함)
• size(): 스택의 원소 개수 반환
• empty(): 스택이 비었는지 확인

큐와 스택의 차이점 정리

                                 스택(Stack)                                                     큐(Queue)

 

구조	후입선출(LIFO)	선입선출(FIFO)
삽입 위치	top(맨 위)	back(맨 뒤)
삭제 위치	top(맨 위)	front(맨 앞)
주요 함수	push, pop, top, empty	push, pop, front, back, empty
비유	접시 쌓기	줄서기(은행, 버스 등)
응용 예시	되돌리기, 괄호검사	프린터 대기열, BFS

 

핵심 요약

• 스택(Stack) :
  마지막에 넣은 데이터가 가장 먼저 나온다.
  (책 더미, 웹 브라우저 뒤로가기, undo 기능 등)
• 큐(Queue) :
  먼저 넣은 데이터가 가장 먼저 나온다.
  (놀이공원 입장 줄, 콜센터 대기, BFS 등)

 

아래는 이 문제를 해결하기 위해 작성한 코드이다.

 

#include <bits/stdc++.h>
using namespace std;

int main (void){
    ios::sync_with_stdio(0); cin.tie(0);
    int N;
    cin >> N;
    stack<int> s;
    for (int i = 0; i < N; i++){
        string str;
        cin >> str;
        if (str == "push"){
            int X;
            cin >> X;
            s.push(X);
        }

        else if (str == "pop"){
            if (s.size() == 0) cout << -1 << '\n';
            else{
            cout << s.top() << '\n';
            s.pop();
            }   
        }

        else if (str == "size"){
            cout << s.size() << '\n';
        }

        else if (str == "empty"){
            cout << s.empty() << '\n';
        }
        else if (str == "top"){
            if (s.size() == 0) cout << -1 << '\n';
            else cout << s.top() << '\n';
        }
    }
    return 0;
}