C++ 스택 자료구조

스택 설명

스택은 배열과 비슷하지만 기능이 제한되어 있습니다. 맨 위에 새 요소를 추가하고, 제거할 때도 맨 위의 요소를 제거 합니다. 이는 알고리즘 구현시 임시 목록에 객체를 추가한 다음 나중에 목록에서 객체를 꺼내려고 할 때 필요합니다.

스택을 가리켜 LIFO 라고도 하는데요. 이는 Last-in, First out의 약자로 마지막으로 들어온 요소가 가장 먼저 제거되는 요소라는 의미입니다.

스택 문제

출처 : 백준 알고리즘

문제

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

명령은 총 다섯 가지이다.

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

입력

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

ex)

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

출력

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

ex)

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

풀이

#include <iostream>
    
using namespace std;
    
int stack[10000];
int ind = -1;
    
void push(int x) {
    stack[++ind] = x;
}
    
int empty() {
    if (ind < 0) {
        return 1;
    } else {
        return 0;
    }
}
    
void pop() {
    if (empty() == 1) {
        cout << "-1" << "\n";
    } else {
        cout << stack[ind] << "\n";
        stack[ind--] = 0;
    }
}
 
int main() {
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        string command;
        cin >> command;
        
        if ("push" == command) {
            int x; 
            cin >> x;
            push(x);
        } else if ("top" == command) {
            if (empty() == 1) {
                cout << "-1" << "\n";
            } else {
                cout << stack[ind] << "\n";
            }
        } else if ("pop" == command) {
            pop();
        } else if ("empty" == command) {
            cout << empty() << "\n";
        } else {
            cout << ind + 1 << "\n";
        }
    }
    return 0;
}