스택

: 한 쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조; 먼저 들어간 원소가 가장 나중에 나옴. FILO(First In Last Out)

1. 성질

1. 원소의 추가 O(1)
2. 원소의 제거 O(1)
3. 제일 상단의 원소 확인 O(1)
4. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

2. 구현

배열 or 연결리스트로 가능하지만 배열이 더 쉬우므로 배열로 구현

스택 push, pop과 top 연산 구현
push: 현재 pos자리에 원소를 추가하고 pos를 증가시킨다.
pop: pos가 0이 아니면(스택이 비어있지 않으면) pos를 1 감소시킨다. 이전 pos자리에 원소를 변경시킬 필요가 없음
top: pos-1 위치의 원소를 반환한다.

#include <iostream>
using namespace std;

const int MX = 1000005;
int dat[MX];
int pos = 0;

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

void pop(){
    if(pos != 0)
        pos--;
}

int top(){
    if(pos != 0)
        return dat[pos-1];
}

3. STL Stack

push, pop, top, empty와 size 연산을 사용한다.

stack이 비었을 때 top이나 pop 호출시 런타임 에러 발생

4. 연습문제

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

STL stack을 사용하여 풀이

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

int main() {
    stack<int> s;
    int n;
    cin >> n;
    while(n--) {
        string op;
        cin >> op;
        if(op == "push") {
            int a;
            cin >> a;
            s.push(a);
        }
        else if(op == "top") {
            if(!s.empty())
                cout << s.top() << '\n';
            else {
                cout << -1 << '\n';
            }
        }
        else if(op == "size") {
            cout << s.size() << '\n';
        }
        else if(op == "pop") {
            if(!s.empty()) {
                cout << s.top() << '\n';
                s.pop();
            }
            else {
                cout << -1 << '\n';
            }
        }
        else if(op == "empty") {
            if(s.empty())
                cout << 1 << '\n';
            else
                cout << 0 << '\n';
        }
    }
}

ii) 배열로 stack을 구현하여 풀이

#include <iostream>
using namespace std;
const int MX = 1000005;
int dat[MX];
int pos = 0;

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

void pop() {
    pos--;
}

int top() {
    return dat[pos-1];
}

int main() {
    int n;
    cin >> n;
    while(n--) {
        string op;
        cin >> op;
        if(op == "push") {
            int a;
            cin >> a;
            push(a);
        }
        else if(op == "pop") {
            if(pos != 0) {
                cout << top() << '\n';
                pop();
            }
            else {
                cout << "-1" << '\n';
            }
        }
        else if(op == "size") {
            cout << pos << '\n';
        }
        else if(op == "empty") {
            if(pos == 0) {
                cout << 1 << '\n';
            }
            else
                cout << '0' << '\n';
        }
        else {
            if(pos != 0) {
                cout << top() << '\n';
            }
            else {
                cout << "-1" << '\n';
            }
        }
    }
}

pop과 top연산시 stack이 비었는지 확인하는 작업을 해준다.

참고 자료: https://blog.encrypted.gg/933