스택 (Stack)

---

저번 포스트 요약 — 배열과 벡터

---

• 배열은 고정 크기, 벡터는 동적 크기 (내부적으로 2배씩 확장)
• push_back: Amortized O(1), 중간 삽입/삭제: O(n)
• unique()는 연속된 중복만 제거 → erase()와 함께 써야 적용됨
• size()는 unsigned 타입 → size() - 1 언더플로우 주의

스택이란

---

자료구조 중 하나로, LIFO(Last In, First Out)의 구조를 가진다.
접시 쌓기 같은 곳에서 쓰인다.

기본 연산

---

push(val)은 스택의 맨 위에 val을 추가한다.
pop()은 가장 위에 있는 원소를 제거한다.
top()은 가장 위에 있는 원소를 반환한다.(단, 제거하지는 않음)
empty()는 비어있는지를 반환한다. 비어있다면 true.
size()는 스택의 원소 개수를 반환한다.

pop을 사용할 때 주의사항은 원소를 반환하지 않으니, 원소의 값이 필요하다면 top()을 먼저 사용해야 한다.

코딩테스트 활용

---

스택은 코테에서도 많이 쓰이는 자료구조이다.

예시를 몇 개 들어보자면,

1. 괄호검사

   bool IsValid(string s)
   {
    stack<char> st;
    for(char c : s)
    {
        if(c == '(' || c == '{' || c == '[')
        {
            st.push(c);
        }
        else
        {
            if(st.empty()) return false;
            char top = st.top();
            st.pop();
            if(c == ')' && top != '(') return false;
            if(c == '}' && top != '{') return false;
            if(c == ']' && top != '[') return false;
        }
    }
   
    return st.empty();
   }
   

2. 연속 중복 제거(unique 함수와 동일)
   ```cpp stack st;

for(int x : arr) { if(!st.empty() && st.top() == x) continue; st.push(x); } ```

마치며

---

벡터의 push_back()기능과 pop_back() 기능을 사용하면 스택과 동일하게 사용할 수 있을 것 같다. 만약 인덱스에 접근하는 기능이 필요하다면 vector를 쓰는 게 좋을 것 같다.

• algorithm
• stack
• codingtest