스택 이론 - C++ (백준 9012 문제풀이)

[1] 스택이란?

 

스택은 쌓는다라는 의미로 먼저 들어온 데이터가 마지막에 제일 나중에 들어온 데이터가 처음으로 꺼낼 수 있는 구조를 말합니다. 이를 LIFO(Last In First Out) 구조라고 합니다.

✏️ Note
스택을 삽입하는 연산을 PUSH, 스택에 있는 데이터를 꺼내는 행위를 POP이라고 부릅니다.

[2] 스택의 ADT(Abstract Data Type)

ADT는 구현하는 구조(Stack)에 대해서 구현 방법을 명시하지 않고 어떠한 데이터의 구조와 연산들을 하는지에 대한 설명(명세)을 말합니다. 스택의 연산에는 push, pop, isFull, isEmpty, top과 같은 연산들이 존재합니다. 아래의 설명을 보도록 하겠습니다.

• push()
  push는 스택에 데이터를 넣는 연산을 수행합니다.
• pop()
  pop은 가장 최근에 스택에 push 한 데이터를 꺼내어, 데이터를 반환합니다.
• isFull()
  isFull은 스택에 데이터가 더 들어갈 공간이 있는지 확인합니다. 공간이 없다면 True를 반환 있다면 False를 반환합니다.
• isEmpty()
  isEmpty는 스택의 공간에 데이터가 하나 이상이라도 있는지를 확인하는 것이며, 있다면 False, 없다면 True를 반환합니다.
• top()
  top은 가장 최근에 push 한 데이터를 확인합니다.
• size()
  size는 스택의 최대 크기를 확인할 수 있습니다.

 

[3] 스택 사용해 보기 - C++

#include <iostream>
#include <stack>

using namespace std;
int main() {
    stack<int> st;
    // push  연산
    st.push(1);
    st.push(2);
    st.push(3);


    // 스택이 isEmpty에 대해서 True를 반환할 때까지 pop 수행

    while(!st.empty()) {
        cout << st.top() << " "; // 가장 최근에 넣은 데이터 출력
        st.pop(); // // 데이터를 pop 수행
    }
}

[4] 괄호 짝 맞추기 문제

• 원본 링크
  https://www.acmicpc.net/problem/9012

 

(1) 설명

괄호 문자열은 두 개의 괄호 기호인 (, ) 만으로 구성되어 있는 문자열입니다. ( 문자열을 스택에 넣어두고, ) 문자열이 있을 때에 스택에 (가 있는지 확인 후 없다면 NO를 출력하거나 있다면 (을 pop을 수행하고 다음 문자열을 검사합니다. N의 길이만큼 스택을 이용해서 시간제한은 점근 표기법 O(n)에 됩니다.

(2) 코드

#include <iostream>
#include <stack>

using namespace std;



bool solution (string brakets) {
    stack<char> st;

    for (int i = 0; i < brakets.length(); i++) {
        if (brakets[i] == '(') {
            st.push('(');
        } else {
            if (st.empty()) return false;
            st.pop();
        }
    }
    // 스택이 비어있다면 모든 괄호가 닫힌 것으로 확인한다.
    if (st.empty()) return true;
    // 스택이 비어있지 않다면 모든 괄호가 닫히지 않은 것으로 확인한다
    return false;
}

int main() {
    int n;
    cin >> n;

    string brakets;
    for (int i = 0; i < n; i++) {
        cin >> brakets;
        bool isBraket = solution(brakets);
        if (isBraket) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

 

 

✏️ Note
stack의 push와 pop은 시간복잡도가 O(1)입니다.

[4] 참고문헌

• 박경록, 코딩 테스트 합격자 되기 C++편
• 박경록 저자님의 스터디에 참가하여 정리하며 작성한 글입니다.