Stack 자료구조 예제 및 정리

Stack

자료 구조 중 하나인 stack의 사전적 정의는 '쌓다', '더미'이다. 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있다. stack은 나중에 들어간 것이 먼저 나오는 (Last In First Out)의 형태를 띠는 자료구조이다. 이 방식이 stack의 가장 큰 특징이자 스택을 사용하는 이유라고 할 수 있다. stack은 C++ 표준 라이브러리(Standard Template Library)에 있는 정의되어 있어 필요할 때마다 만들어 사용하지 않고 include 하여 사용하면 편리하다.

 

Stack의 특징

1. 먼저 들어간 자료가 나중에 나옴 LIFO(Last In First Out) 구조
2. 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 함 
3. 인터럽트처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등에 쓰임
4. 그래프의 깊이 우선 탐색(DFS)에서 사용
5. 재귀적(Recursion) 함수를 호출 할 때 사용

---

아래는 스택 자료구조를 활용한 백준 기본 구현문제 #28278 스택2의 소스코드이다.

#include <iostream>
#include <stack>

using namespace std;

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

    int N;
    cin >> N;

    stack<int> s;
    while(N-->0) {
        int num;
        cin >> num;

        if (num==1) {
            int a;
            cin >> a;

            s.push(a);
        }
        else if (num==2) {
            if (s.empty()) {
                cout << -1 << '\n';
                continue;
            }
            cout << s.top() << '\n';
            s.pop();
        }
        else if (num==3) cout << s.size() << '\n';
        else if (num==4) s.empty() ? cout << 1 << '\n' : cout << 0 << '\n';
        else if (num==5) {
            if (s.empty()) {
                cout << -1 << '\n';
                continue;
            }
            cout << s.top() << '\n';
        }
    }

    return 0;
}