스택(Stack)

• stack이란?

 

스택은 가장 먼저 입력된 데이터가 맨 아래에 쌓이고 가장 최근에 입력된 데이터가 가장 위에 쌓이는 구조를 가진 LIFO 형태의 자료구조이다.

 

스택의 구조

 

이 그림처럼 스택은 원소가 들어올 때마다 위에 차곡차곡 쌓이는 형태이다. 이 그림에서 원소 D를 추가하면 원소 C 위에 D가 올라가는 형태가 되고 삭제 연산을 하면 가장 위에 있는 $C$가 삭제된다. 이렇게 나중에 들어온 원소가 가장 먼저 나가게 되는 입출력 형태를 후입선출(LIFO: Last-In-First-Out)이라고 한다.

 

 

 

Stack의 기능

• push(x) : 원소 x를 스택의 맨 위에 추가한다.
• pop() : 스택에 원소가 있다면 맨 위에 있는 원소를 삭제하고 리턴한다.
• empty() : 스택이 비어있으면 1(true), 그렇지 않으면 0(false)을 리턴한다.
• top() : 맨 위에 있는 원소를 리턴한다.
• size() : 스택에 들어있는 원소의 개수를 리턴한다.

 

 

다음은 스택을 대략적으로 구현한 코드이다.

 

 

class Stack{
    int data[1001];
    int top;
    public:
        Stack(){ top=-1; }
        ~Stack(){}
        bool Empty()
        {
            return top==-1;
        }
        void push(int x)
        {
            Stack[++top]=x;
        }
        int pop()
        {
            if(Empty()){ cout << "Stack is empty\n"; return 0; }
            return Stack[top--];
        }
        int Top()
        {
            return Stack[top];
        }
        int Size()
        {
            return top+1;
        }
};
 

 

다음은 스택 STL을 사용한 코드이다.

 

 

#include <iostream>
#include <algorithm>
#include <stack> //stack 헤더파일

using namespace std;

int main()
{
    stack<int> st; //스택 선언
    st.push(7);
    st.push(3);
    st.pop();
    cout << st.size() << "\n";
    st.pop();
    cout << st.empty() << "\n";
    st.push(5);
    st.push(2);
    cout << st.top() << "\n";
    return 0;
}

 

 

 

스택은 괄호 검사 프로그램, 후위 표기 수식 계산, DFS 등에 사용된다.

 

 

---

 

스택의 사용

 

 

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

10828번: 스택

 

스택의 사용법을 배우는 문제로, 단순히 구현하거나 STL을 사용하면 된다.

 

#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

int n;
stack<int> st;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    while(n--){
        string s;
        cin >> s;
        if(s=="push"){
            int a; cin >> a;
            st.push(a);
        }
        if(s=="pop"){
            if(st.empty()){ cout << -1 << "\n"; }
            else{ cout << st.top() << "\n"; st.pop(); }
        }
        if(s=="size"){
            cout << st.size() << "\n";
        }
        if(s=="empty"){
            cout << st.empty() << "\n";
        }
        if(s=="top"){
            if(st.empty()){ cout << -1 << "\n"; }
            else{ cout << st.top() << "\n"; }
        }
    }
    return 0;
}

 

 

---

 

 

 

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

9012번: 괄호

 

입력받은 문자열에서 '('가 나오면 스택에 이를 넣어주고, ')'가 나오면 pop 해준다.

 

만약 pop할 수가 없다면(스택이 비어있다면) 올바른 괄호가 아니라는 뜻이다.

 

예를 들어 "(()))("를 해보면 처음에 '('가 두번 나오므로 스택에 push 해준다. 그리고 ')'가 세 번 나오는데 스택에는 현재 2개 밖에 없으므로 이는 올바른 괄호가 아니다. 

 

//문자열 s가 올바른 괄호 문자열인지 판별하는 함수
bool isCorrect(string &s)
{
    stack<char> st;
    for(int i=0; i<s.size(); i++){
        if(s[i]=='('){
            st.push('(');
        }
        else{
            if(st.empty()){
                return 0;
            }
            st.pop();
        }
    }
    if(st.empty()){ return 1; }
    return 0;
}

 

 

---

 

 

 

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

2493번: 탑

 

스택을 응용하는 대표 문제이다.

 

$i$에 대해 $a_{j}$≥$a_{i}$, $j<i$를 만족하는 $j$의 최댓값을 출력하는 문제이다. 즉 배열에서 $i$번째 값보다 앞에 있는 값들 중 $i$번째 값보다 크거나 같은 값을 찾는 것이다. 완전 탐색으로 문제를 푼다면 시간복잡도 $O(N^{2})$로 시간초과가 난다. 따라서 다른 방법을 찾아야한다.

 

예졔를 보면 탑이 6 9 5 7 4로 구성되어 있다.

 

 

$1$번 탑은 신호를 수신해줄 탑이 없기 때문에 0을 출력한다. $2$번 탑은 $1$번 탑이 수신하지 못하므로 $2$번 탑도 0을 출력한다. 이 때 $2$번째 위치에 높이가 9인 탑이 있기 때문에 $1$번째에 있는 높이가 6인 탑의 정보는 더 이상 필요가 없을 것이다.(왜냐면 높이가 더 낮기 때문에 1번째 탑까지 탐색할 일이 없기 때문이다)

 

그러면 9 5 7 4가 되고, $3$번 탑은 $2$번탑과 수신하므로 2를 출력한다. $4$번 탑도 $2$번 탑과 수신하므로 2를 출력한다. 이 때 $4$번째 위치에 높이가 7인 탑이 있기 때문에 $3$번째 탑의 정보는 더 이상 필요가 없다.

 

따라서 9 7 4가 되고, $5$번 탑은 $4$번 탑과 수신하므로 4를 출력한다.

 

 

필요 없는 탑의 정보는 제거하는 것이 핵심이다. 따라서 스택에 정보를 넣어주면서 조건에 만족하는 원소가 나올 때까지 pop을 해준다.

 

 

#include <iostream>
#include <stack>

using namespace std;

int N;
stack< pair<int, int> > st;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N;
	for(int i=1; i<=N; i++){
        int a; cin >> a;
        while(!st.empty() && st.top().first<a){
            st.pop();
        }
        if(st.empty()){ cout << 0 << " "; }
        else{ cout << st.top().second << " "; }
        st.push({a, i});
	}
    return 0;
}

 

 

---

 

 

 

후위 표기식

 

수식은 일반적으로 3가지 방법으로 표기할 수 있다. 바로 전위 표기법(prefix notation), 중위 표기법(infix notation), 후위 표기법(postfix notation)이다. 중위 표기법은 A*(B+C)와 같이 우리가 사용하는 표기법으로 피연산자(A, B 등) 사이에 연산자(+, - 등)이 위치하는 표기법이고, 전위 표기법은 연산자가 피연산자 앞에, 후위 표기법은 연산자가 피연산자 뒤에 위치하는 표기법이다. 예를 들어 중위 표기법 A+B를 전위 표기법으로 나타내면 +AB이고 후위 표기법으로 나타내면 AB+이다. 이제 중위 표기법을 후위 표기법으로 바꾸는 방법을 알아볼 것인데, 이 때 스택이 사용된다.

 

후위 표기식의 장점은 사칙 연산 우선순위를 고려하여 표시할 수 있어 괄호가 필요하지 않다. 예를 들어 A*(B+C)는 후위 표기법으로 나타내면 ABC+*가 된다. 후위 표기식으로 나타내는 방법은 먼저 식을 입력받고, 식을 처음부터 살펴보면서 피연산자는 그냥 출력하고, 사칙연산이나 (는 스택에 넣는다. 만약 )가 나타나면 스택에서 (가 있는 부분까지 모두 출력한다.