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

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

10828번: 스택

이번 포스팅에서는 백준 10828번 문제를 학습합니다.

 

 

10828번 문제를 풀기 위해서 스택에 대해 간단히 정리하자.

 

I) 스택

스택은 가장 기본이 되는 자료구조이다.

한쪽에서만 자료를 넣고 뺄 수 있고, 나중에 들어온 것이 먼저 처리 되기 때문에 Last In First Out (LIFO) 라고도 부른다.

아래 그림과 같이 접시 쌓기라고 생각 할 수 있다.

한줄로 쌓인 스택

위 그림에서 먼저 들어온 숫자는 순서대로 '1', '2', '3', '5', '6', '4' 이다.

위의 스택을 하나 지운다면 '4'가 먼저 지워질 것이다. (LIFO)

 

왼쪽부터 쌓이는 빈 스택에 아래와 같은 입력을 차례대로 했다고 해보자.

숫자 7 삽입 - 숫자 5 삽입 -  숫자 4 삽입 -  숫자 하나 삭제 - 숫자 6 삽입 - 숫자 하나 삭제

그렇다면 과정 별 결과는 아래 그림과 같을 것이다. 

 

스택을 사용하는 방법은 2가지가 있다.

첫번째는 라이브러리를 이용하는 방법이고,

두번째는 직접 구현하는 것이다.

 

스택 라이브러리의 기본 기능에는

push: 스택에 자료를 넣는 기능

pop: 자료를 스택에서 빼는 기능

top: 스택의 가장 위에 있는 자료를 보는 기능

empty: 스택이 비어있는지 아닌지를 알아보는 기능

size: 스택에 저장되어 있는 자료의 개수를 알아보는 기능

이 있다.

 

<10828번 예시 코드>

#include<iostream>
#include<string>
 
using namespace std;
 
int main(){
    int arr[1000];
    string str;
    int first = 0;
    int n;
    cin >> n;
 
    for(int i = 0; i < n; i++) {
        cin >> str;
        
        if(str == "push"){
            int X;
            cin >> X;
            arr[++first] = X;
        }
        else if (str == "pop"){
            if(first == 0){
                cout << -1 << "\n";
            }
            else{
                cout << arr[first--] << "\n";
            }
        }
        else if(str == "size"){
            cout<< first <<"\n";
        }
        else if(str == "empty"){
            if(first == 0){
                cout<<1<<"\n";
            }
            else{
                cout<<0<<"\n";
            }
        }
        else if(str == "top"){
            if(first == 0){
                cout<<-1<<"\n";
            }
            else
                cout<< arr[first] << "\n";
        }
    }
        
  
    return 0;
}

먼저 크기가 1000인 배열을 선언한 후, 문자 입력을 위해 string, 배열의 index 표시를 위해 first, 명령의 수 n를 입력 받는다.

그 다음 for 을 n까지 돌리면서, str을 입력 받는다.

1. str이 push인 경우

push X 에서 정수 X를 스택에 넣기 위해 X를 입력 받고, 배열의 ++first 칸에 대입한다.

2. str이 pop인 경우

스택에 들어있는 정수가 없는 경우(=first 가 0인 경우) -1을 출력하고, 그렇지 않은 경우 배열의 first 칸의 수를 출력하고 1을 빼준다

--> first는 가장 최신의 배열이 들어가 있는 위치를 나타내므로,,,

3. str이 size인 경우

스택에 들어있는 정수 즉, first의 값을 출력한다.

4. str이 empty인 경우

스택에 들어있는 정수가 없는 경우(=first 가 0인 경우) 1을 출력하고, 그렇지 않은 경우 0을 출력한다.

5. str이 top인 경우 

스택에 들어있는 정수가 없는 경우(=first 가 0인 경우) -1을 출력하고, 그렇지 않은 경우 스택의 가장 위에 있는 정수(배열의 first칸에 있는 정수)를 출력한다.

 

 

 

 

*유의사항

- 공부 중인 인공지능공학과 대학생이 정리해서 남긴 정리입니다.

- 정확하지 않거나, 틀린 점이 있다면 댓글로 알려주시면 감사하겠습니다.