Stack

스택의 성질

1. LIFO(Last In First Out), 후입선출의 구조
2. 원소의 추가가 O(1)
3. 원소의 제거가 O(1)
4. top의 원소 확인이 O(1)
5. top이 아닌 다른 원소들의 확인/변경이 불가능

스택

스택을 배열로 구현하는 것은 아주 간단합니다.

스택 https://github.com/Geniemo/PracticalAlgo/blob/master/Stack.cpp

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

const int MX = 1000005;
int dat[MX];
int pos = 0;

void push(int x) {
    dat[pos++] = x;
}

void pop() {
    pos--;
}

int top() {
    return dat[pos - 1];
}

bool isEmpty() {
    return pos == 0;
}

bool isFull() {
    return pos == MX;
}

void stack_test() {
    push(1);    
    push(2);
    push(3);
    while (!isEmpty()) {
        cout << top() << " ";
        pop();
    }
}

int main(void) {
    stack_test();
    return 0;
}

활용 예제

스택은 많은 곳에서 활용될 수 있습니다.
대표적으로 전위, 후위, 중위 표기법 변환, DFS 등에 사용됩니다.

이 포스트에서는 중위 표기식을 후위 표기식으로 바꾸는 문제를 다뤄보겠습니다.

백준 1918번 https://www.acmicpc.net/problem/1918

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

const int MX = 105;
int dat[MX];
int pos = 0;

void push(int x) {
    dat[pos++] = x;
}

void pop() {
    pos--;
}

int top() {
    return dat[pos - 1];
}

bool isEmpty() {
    return pos == 0;
}

int priority(char c) {
    if (c == '(')
        return 0;
    else if (c == '+' || c == '-')
        return 1;
    else if (c == '*' || c == '/')
        return 2;
    return -1;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    string infix, postfix;
    cin >> infix;
    for (char c : infix) {
        if (isalpha(c))
            postfix += c;
        else if (c == '(')
            push(c);
        else if (c == ')') {
            while (top() != '(') {
                postfix += top();
                pop();
            }
            pop();
        }
        else {
            while (!isEmpty() && priority(c) <= priority(top())) {
                postfix += top();
                pop();
            }
            push(c);
        }
    }
    while (!isEmpty()) {
        postfix += top();
        pop();
    }
    cout << postfix;
    return 0;
}