스택_이론

Stack

한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조이다.

마지막으로 넣은 것이 가장 먼저 나오기때문에 Last In First Out(LIFO)라고도 한다.

기본적인 함수

 push : 스택에 자료를 넣는 연산

 pop : 스택에서 자료를 빼는 연산

 top : 스택의 가장 위에 있는 자료를 보는연산

 empty : 스택이 비어있는지 아닌지를 알아보는 연산

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

배열 같은 경우 중간 삽입/삭제는 배열의 길이만큼 걸린다. 즉 O(n)이다. 하지만 스택의 모든 연산은 O(1)이므로 스택의 가장 가까운걸(top) O(1)만에 찾을 수 있다.

 

Example

1. 재귀함수

2. 웹 브라우저 방문기록

3. ctrl + z 같은 실행취소

4. 수식의 괄호검사 (연산자 우선순위를 위한 괄호 검사)

즉 가장 가까운것에 대한 연산을 할때 많이 사용한다.

구현

배열, 링크드리스트, 벡터 중 상황에 맞게 사용하면 된다.

#include <iostream>
#include <stack>
#include <string>
using namespace std;
struct Stack {
    int data[10000];
    int size;
    Stack() :size(0) {}
    void push(int num) {
        data[size] = num;
        size += 1;
    }
    bool empty() {
        if (size == 0) {
            return true;
        }
        else {
            return false;
        }
    }
    int pop() {
        if (empty()) {
            return -1;
        }
        else {
            size -= 1;
            return data[size];
        }
    }
    int top() {
        if (empty()) {
            return -1;
        }
        else {
            return data[size - 1];
        }
    }
};
int main() {
    Stack s;
    string cmd;
 
    while (true) {
        cin >> cmd;
        if (cmd == "push") {
            int num;
            cin >> num;
            s.push(num);
        }
        else if (cmd == "top") {
            cout << (s.empty() ? -1 : s.top()) << '\n';
        }
        else if (cmd == "size") {
            cout << s.size << '\n';
        }
        else if (cmd == "empty") {
            cout << s.empty() << '\n';
        }
        else if (cmd == "pop") {
            cout << (s.empty() ? -1 : s.top()) << '\n';
            if (!s.empty()) {
                s.pop();
            }
        }
    }
    return 0;
}

출처 백준 온라인 강의_알고리즘 기초