스택(Stack)

스택이란?

후입선출(LIFO)의 자료구조로 재귀함수가 동작하는 방식과 비슷하다.

프링글스 통과 비슷하게 맨 아래에 있는 감자칩을 먹기 위해서 맨 위에 있는 감자칩부터 순서대로 먹어야 됨

스택은 배열 또는 연결리스트로 구현 할 수 있지만 보통은 배열로 구현을 한다.

스택이 top에서만 삽입과 삭제가 일어나기 때문에 맨 아래쪽에 있는 데이터는 맨 마지막에 삭제된다.
재귀함수도 처음으로 호출 한 함수가 먼저 종료되지 않고 호출 한 함수안의 마지막 재귀함수의 실행이 종료되고 순차적으로 그 다음 재귀함수가 종료되야지 처음으로 호출한 재귀함수가 종료된다.

스택 구현과 STL 사용법

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

const int MX = 1000005;
int dat[MX];
int pos = 0; // 다음 원소가 추가될 때 삽입해야 되는 위치(스택의 길이, 원소의 개수를 의미)

void push(int x) {
    dat[pos++] = x;
}

// top위치에 있는 데이터 삭제
void pop() {
    // push 연산시 들어오는 값으로 덮어써질거기 때문에 pos위치에 있는 데이터를 변경할 필요가 없음
    pos--;
}

// 맨 위에 있는 데이터 확인
// pos는 데이터가 삽입되는 위치를 가리키고 있기 때문에 그 아래칸의 데이터를 확인해야 함
int top() {
    return dat[pos - 1];
}

void test() {
    push(10);
    push(20);    
    pop();
    cout << top();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);    

    // STL로 Stack 사용
    stack<int> s;
    s.push(10);
    s.push(20);
    s.pop(); // top 위치에 있는 데이터 삭제
    cout << s.top() << '\n';
    s.push(30);
    cout << s.top() << '\n';
    s.pop();    
    s.pop();     
    // s.pop(); // 런타임 에러(스택이 비어있는데 데이터를 삭제함, top의 경우도 마찬가지로 런타임 에러 발생)

    // 런타임 에러를 방지하기 위해서 데이터가 있는 경우에만 수행하도록 변경
    // empty() 비어있으면 1을 반환
    if (!s.empty()) {
        s.pop();
    }

    return 0;
}

백준 10828

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);    

    stack<int> s;
    int orderNum;
    cin >> orderNum;

    for (int i = 0; i < orderNum; i++) {
        string command;
        cin >> command;

        if (command == "push") {
            int num;
            cin >> num;
            s.push(num);
        }
        else if (command == "pop") {
            if (s.empty()) {
                cout << -1 << '\n';
            }
            else {
                cout << s.top() << '\n';
                s.pop();                
            }            
        }
        else if (command == "size") {
            cout << s.size() << '\n';
        }
        else if (command == "empty") {
            cout << (int)s.empty() << '\n';
        }
        else if (command == "top") {
            if (s.empty()) {
                cout << -1 << '\n';
            }
            else {                
                cout << s.top() << '\n';
            }
        }
    }


    return 0;
}