스택(Stack)

스택이 뭐에요

스택은 가장 늦게 넣은 값이 가장 먼저 빠져나오는 LIFO(Last-In-First-Out)의 자료구조입니다. 스택에 push 연산을 하면 원소가 추가되고, pop 연산을 하면 가장 늦게 넣은 원소가 삭제됩니다. 그 외에도 size(스택의 크기), top(가장 위에 있는 원소), empty(비었는지) 연산이 있습니다.

구현은 어케 해요

구현은 연결 리스트를 사용해서 직접 구현하는 방법과 STL의 내장 기능을 사용하는 방법이 있습니다.

구현은 생각보다 복잡하기 때문에 별로 추천하지는 않습니다.(STL을 사용할 수 없는 환경일 때만 사용합시다.)

(코드)

template<typename T>
struct Stack {
    struct Node {
        T num;
        Node*next;
        Node() {
            num=0; next=NULL;
        }
        Node(T nd,Node*np) {
            num=nd; next=np;
        }
    };
    int cnt;
    Node*head;
    Stack() {
        cnt=0;
        head=NULL;
    }
    int size() {return cnt;}
    bool empty() {return cnt==0;}
    T top() {return head->num;}
    void push(T nd) {
        cnt++;
        head=new Node(nd,head);
    }
    void pop() {
        cnt--;
        Node*tmp=head;
        head=head->next;
        tmp->next=NULL;
        delete tmp;
    }
};

STL에는 stack 자료구조가 내장되어 있습니다. stack<자료형> 이름; 과 같은 방식으로 선언해서 push(원소), pop, top, empty, size 같은 함수를 사용할 수 있습니다. 스택이 비어있을 때 pop, top을 사용하면 런타임 에러가 나므로 주의해야 합니다.

(사용 예시)

#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> S;
    S.push(1);
    S.push(2);
    S.push(3);
    S.pop();
    cout<<S.size()<<" "<<S.empty()<<" "<<S.top();
}

예시 1

https://www.acmicpc.net/problem/9012

9012번: 괄호

풀이

문제를 풀다 보면 '올바른 괄호 문자열'이라는 말이 많이 나옵니다.

 "("와 ")"로 구성된 문자열 중, "()"는 올바른 괄호 문자열이고, x가 올바른 괄호문자열이면 "(x)"도 올바른 괄호 문자열이고, x와 y가 올바른 괄호문자열이면 xy도 올바른 괄호문자열입니다.

주어진 괄호 문자열이 올바른 괄호 문자열인지 판별하는 것을 스택을 사용해서 할 수 있습니다.

1. 현재 문자가 "("라면 스택에 넣습니다.

2. 현재 문자가 ")"라면 스택에 있는 "("를 뺍니다.(스택이 비어 있다면 올바르지 않은 괄호 문자열입니다.)

3. 모든 문자에 대해 반복한 후 스택이 비어 있지 않다면 올바르지 않은 괄호 문자열이고, 스택이 비어있다면 올바른 괄호 문자열입니다.

소스코드

#include <bits/stdc++.h>
using namespace std;

int t;
string s, ans[5]={"YES", "NO"};
stack<char> S;

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>t;
    while(t--) {
        int flag=0;
        cin>>s;
        for(int i=0;i<s.size();i++) {
            if(s[i]=='(') {
                if(S.empty()) S.push(s[i]);
                else if(S.top()=='(') S.push(s[i]);
                else {flag=1; break;}
            }
            else {
                if(S.empty()) {flag=1; break;}
                else if(S.top()==')') S.push(s[i]);
                else S.pop();
            }
        }
        if(!S.empty()) flag=1;
        cout<<ans[flag]<<"\n";
        while(!S.empty()) S.pop();
    }
    return 0;
}

예시 2

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

풀이

후위 표기식은 a+b를 ab+와 같은 형식으로 표현하는 형태입니다.

다음과 같은 방식으로 동작합니다.

1. 피연산자를 만났다면 출력합니다.(피연산자들끼리의 순서는 불변이기 때문)

2. 여는 괄호를 만났다면 스택에 넣습니다.

3. 닫는 괄호를 만났다면 여는 괄호를 만날때까지 스택에 있는 연산자들을 출력/pop하고, 여는 괄호도 pop합니다.

4. 사칙연산자를 만났다면 자신보다 스택이 비지 않고, 여는 괄호가 나오지 않고, top의 연산자가 자신보다 우선순위가 높을 동안 연산자들을 출력/pop하고 자신을 스택에 넣습니다.

5. 모든 문자에 대해 반복한 후 스택에 남아있는 연산자들을 모두 출력/pop해줍니다.

소스코드

#include <bits/stdc++.h>
using namespace std;

string S;
stack<char> Stk;
map<char, int> r;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    r['+']=r['-']=1, r['*']=r['/']=2;
    cin>>S;
    for(int i=0; i<S.size(); i++) {
        if('A'<=S[i] && S[i]<='Z') cout<<S[i];
        else if(S[i]=='(') Stk.push('(');
        else if(S[i]==')') {
            while(Stk.top()!='(') {
                cout<<Stk.top(); Stk.pop();
            }
            Stk.pop();
        }
        else {
            while(!Stk.empty() && Stk.top()!='(' && r[S[i]]<=r[Stk.top()]) {
                cout<<Stk.top(); Stk.pop();
            }
            Stk.push(S[i]);
        }
    }
    while(!Stk.empty()) {
        cout<<Stk.top(); Stk.pop();
    }
    return 0;
}

예시 3

https://www.acmicpc.net/problem/1935

1935번: 후위 표기식2

풀이

후위 표기식을 줬을 때 식의 값을 계산하는 과정은 더 쉽습니다.

1. 수가 나오면 스택에 push합니다.

2. 연산자가 나오면 스택의 가장 위에 있는 두 수를 pop하고 해당 연산자로 연산한 결과를 stack에 넣습니다.

3. 마지막에는 스택에 수 1개만 남아있을 것이고, 그 값을 출력하면 됩니다.

소스코드

#include <bits/stdc++.h>
using namespace std;
using ld=long double;

int N, A[30];
string S;
stack<ld> Stk;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>S;
    for(int i=1; i<=N; i++) cin>>A[i];
    for(int i=0; i<S.size(); i++) {
        if('A'<=S[i] && S[i]<='Z') Stk.push(A[S[i]-'A'+1]);
        else {
            ld a=Stk.top(); Stk.pop();
            ld b=Stk.top(); Stk.pop();
            if(S[i]=='+') Stk.push(a+b);
            else if(S[i]=='-') Stk.push(b-a);
            else if(S[i]=='*') Stk.push(a*b);
            else Stk.push(b/a);
        }
    }
    cout.setf(ios::fixed);
    cout.setf(ios::showpoint);
    cout.precision(2);
    cout<<Stk.top();
    return 0;
}

예시 4

https://www.acmicpc.net/problem/1725

1725번: 히스토그램

풀이

풀이가 많고 굉장히 유명한 문제입니다.

히스토그램의 높이를 쭉 훑으면서

1. 현재의 높이가 스택의 top의 높이보다 높다면 push합니다.

2. 현재의 높이가 스택의 top의 높이보다 낮다면 그렇게 되지 않을 때까지 pop하면서 생기는 직사각형의 넓이들을 모두 갱신합니다.

3. 끝까지 다 훑었으면 스택에 있는 나머지 높이들에 대해서 계산합니다.

이 방법이 성립하는 이유는 스택은 높이가 오름차순으로 정렬된 상태로 들어가고, 스택의 가장 높은 높이, 즉 top보다 낮은 높이가 나오면 top에서부터 쭉 빼면 그 높이보다 큰 모든 높이들을 뺄 수 있기 때문입니다.

스택 문제들은 이렇게 쭉 훑으면서 진행하는 방식(스위핑)이 많습니다.

소스코드

#include <bits/stdc++.h>
using namespace std;

struct data {int h,s;};
int n,h[100010];
long long ans;
stack<data> S;

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    ans=0;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=1;i<=n;i++) {
        int m=i;
        while(!S.empty() && S.top().h>h[i]) {
            ans=max(ans,(long long)S.top().h*(i-S.top().s));
            m=min(m,S.top().s); S.pop();
        }
        S.push({h[i],m});
    }
    while(!S.empty()) {
        ans=max(ans,(long long)S.top().h*(n+1-S.top().s));
        S.pop();
    }
    cout<<ans;
    return 0;
}