[C++] STL 자료구조: stack

​

vector와 string은 동적 배열로 임의 위치의 접근, 수정과 마지막 위치의 삽입, 삭제가 O(1)이고,

임의 위치의 삽입, 삭제가 O(n)이라는 특징을 가지고 있어서 연속적인 정보를 저장하는데 적합하다.

stack은 두 자료구조처럼 임의 위치의 접근, 수정을 제공하지 않으며, 마지막 위치의 접근, 삽입, 삭제에만 특화된 자료형이다.

따라서 stack은 원소들을 순서대로 집어넣거나 가장 최근에 들어온 원소를 확인할 때 주로 사용된다.

 원소들은 삽입된 순서대로 가장 먼저 삽입된 원소가 맨 위에 오도록 저장되어있으며, 항상 가장 마지막에 삽입된 원소부터 접근할 수 있다. (프링글스를 뒤집어서 아래부터 감자칩을 넣는다고 생각하면 된다)이러한 특성을 LIFO(Last In First Out)이라고 한다.

vector에서 기능이 제한된건데 왜 쓸까?

stack의 연산만을 이용하는 경우에는 vector 대신 stack을 이용하는 게 의미가 더 명확할 수 있다.

하지만 stack 대신 vector를 사용해도 성능 차이는 거의 없으며 기능 또한 더 다양하게 사용할 수 있기 때문에 문제에 맞게 이용하면 된다.

 

생성자

stack<int> S;

함수

- push : 마지막 위치에 원소를 삽입. O(1)

- pop : 마지막 위치의 원소를 삭제. O(1)

- top : 마지막 위치의 원소를 reference로 반환. O(1)

​

- size : stack의 크기를 size_t 자료형으로 반환.

- empty : stack이 비어있는지 여부를 bool 자료형으로 반환.

 

백준>>

9012)

==>내코드:

int main(){

    fastio;

    int T;

    cin>>T;

    cin.ignore();

    while(T--){

        string s;

        getline(cin,s);

        stack<char> stck;

        for(int i=0; i<s.length();i++){

            if(s[i]=='(') {stck.push('(');}

            else if(s[i]==')') {stck.pop();}

        }

        if(!stck.empty() || stck.top()=='(') {cout<<"NO"<<'\n';}

        else {cout<<"YES"<<'\n';}

    }

}

==> 수정

if(!stck.empty() || stck.top()=='(') {cout<<"NO"<<'\n';}

// stck.top()에서 스택이 비어있는 경우를 처리하지 않아 런타임 오류 발생 

int main(){
    fastio;
    int T;
    cin>>T;
    cin.ignore();
    while(T--){
        string s;
        getline(cin,s);
        stack<char> stck;
        bool flag = false; // bool 변수 사용
        for(int i=0; i<s.length();i++){
            if(s[i]=='(') {stck.push('(');}
            else if(s[i]==')') {
                if(stck.empty()) {
                    flag = true; 
                    break;
                }
                stck.pop();
            }
        }
        if(!stck.empty()) {flag = true;} // 스택이 비어있지 않으면 flag를 true로 설정
        cout<<(flag? "NO":"YES")<<'\n';
    }
    return 0;
}

1873번

int main(){

    fastio;

    int N;

    cin>>N;

    stack<int> S;

    stringstream out; // 출력 문자열을 버퍼에 저장하고 마지막에 한 번에 출력

    for(int i=0, t=0; i<N; i++){

        int x; cin>>x;

        while(t<x) S.push(++t); out<<"+\n";

        if(S.empty() || S.top()!=x)

            return !(cout<<"NO"<<'\n'); //cout에 NO출력 + false문 반환(함수 종료)

        S.pop(); out<<"-\n";

    }

    cout<<out.str(); //객체 내용을 문자열로 반환하고 cout에 출력

}

 

10799번) 쇠막대기

- ')'가 입력되었을 때 레이저가 만들어지거나 / 막대기의 끝과 닿는 2가지 경우이다.

- 레이저는 앞이 (일때 생성되며 막대기는 앞이 )일때 생성된다.

- 레이저가 완성된 후 남아있는 (의 개수가 곧 만들어지는 막대기의 수이다 (stack의 크기) 

-얘도 구글링을 통해 풀었다 ㅎ;

int main(){

    fastio;

    string s;

    int ans=0;

    cin>>s;

    stack<char> st;

    for(int i=0; i<s.length();i++){

        if(s[i]=='(') {st.push(s[i]);}

        else{ // )가 들어갈때

            if(s[i-1]=='(') {

                st.pop();

                ans +=st.size();

                // )가 막대의 끝이면 ) 1개만 pop, 따라서 레이저 완성 후 남아있는 (의 개수가 곧 막대의 개수

            }

                else{ // 전 것이 )일때

                    st.pop();

                    ans++; //막대의 끝일 경우 1개만 추가

                }

        }

    }

    cout<<ans;

    return 0;

}

1406번) 에디터

커서가 왼/오로 이동 + 왼쪽 문자 삭제 / 왼쪽에 문자 추가 등의 4가지 기능이 있다.

처음엔 string s[i]를 써서 추가하고 이동하려고 했는데 stack을 쓰기로 했다. / 또한 string<char, string>을 써서 한 풀이도 있었다.

우선 커서의 위치에 따라 left-stack과 right-stack으로 나눠서 풀어보았다.

int main(){

    fastio;

    string s; cin>>s;

    int n; cin>>n;

    cin.ignore();

    stack <char> lft;

    stack <char> rgt;

    for(int i=0; i<s.length();i++){

        lft.push(s[i]);

    }

    while(n--){

        string c;

        char a; getline(cin,c);

        if (c[0]=='L'){

            if(!lft.empty()){

                a=lft.top();

                rgt.push(a);

                lft.pop();

            }

        }

        else if (c[0]=='D'){

            if(!rgt.empty()){

                a=rgt.top();

                lft.push(a);

                rgt.pop();

            }

        }

        else if (c[0]=='B') {

            if(!lft.empty()){

                lft.pop();

            }

        }

        else if (c[0]=='P'){

            lft.push(c[2]);

        }

 

    }

    string ans;

    while(!lft.empty()) {ans.push_back(lft.top()); lft.pop();}

    reverse(ans.begin(), ans.end());

    while(!rgt.empty()) {ans.push_back(rgt.top()); rgt.pop();}

    cout<<ans<<'\n';

}

내가 풀어본 코드이고 더 간단한 코드는 아래 걸 참고하면 되겠다.

int main() {

fastio;

string s, ans; cin >> s;

stack<char, string> S1(s), S2;

 

int n; cin >> n;

while (n--) {

char c; cin >> c;

if (c == 'L') { if (S1.empty()) continue; S2.push(S1.top()); S1.pop(); }

else if (c == 'D') { if (S2.empty()) continue; S1.push(S2.top()); S2.pop(); }

else if (c == 'B') { if (S1.empty()) continue; S1.pop(); }

else if (c == 'P') { char x; cin >> x; S1.push(x); }

}

 

while (S1.size()) ans.push_back(S1.top()), S1.pop();

reverse(ans.begin(), ans.end());

while (S2.size()) ans.push_back(S2.top()), S2.pop();

cout << ans << '\n';

}