3. 스택

스택

빠른 설명

스택은 나중에 넣은 원소가 먼저 나오는 LIFO 구조다. 괄호 검사, 되돌리기, DFS, 재귀 호출 구조를 이해할 때 자주 쓰인다.

언제 쓰는가

• 최근 상태를 먼저 처리해야 할 때
• 괄호가 올바르게 닫히는지 확인할 때
• 뒤에서부터 되돌아가며 처리할 때

시간복잡도

• push: $O(1)$
• pop: $O(1)$
• top 확인: $O(1)$

참고자료

• Wikipedia - Stack
• cppreference - std::stack
• Python Tutorial - Using Lists as Stacks
• 나무위키 - 스택

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
int main() {
    stack<int> st;
 
    st.push(1);
    st.push(2);
    st.push(3);
 
    while (!st.empty()) {
        cout << st.top() << ' ';
        st.pop();
    }
}

Python 코드

st = []
 
st.append(1)
st.append(2)
st.append(3)
 
while st:
    print(st[-1], end=" ")
    st.pop()