Aidengoldkr – Tech Blog

자료구조를 배우게 되면 가장 먼저 배우는 스택, 우리가 일상 속 많이 들어보는 용어이기도 하다. 흔히 스택을 쌓는다 라고 표현을 하는데, 쌓는다 라는 동사는 스택의 성질에서 유래되었다.

 

스택은 선입후출 FILO(First-In-Last-Out), 후입 선출 LIFO(Last-In-First-Out) 규칙을 따른다. 쉽게 설명하면, 마지막에 들어간 것이 처음으로 나오는 것으로, 젠가통에 젠가를 하나씩 꺼낼때 가장 마지막(위)에 있는 젠가 먼저 꺼내는 것과 같은 로직이다.

 

스택을 사용하는 명령어는 크게 5가지가 있다

• push(n) : stack의 최상단 (마지막)에 값을 넣는다.
• pop() : stack의 최상단 값을 꺼내고 반환한다.
• peek(), top() : stack 최상단 값을 반환한다. (pop에서 꺼내는 과정 생략)
• isEmpty() : stack이 비어있는지 확인한다.
• size() : stack에 저장된 값의 개수 반환한다.

C 언어에서 stack을 사용하는 법은 크게 두 가지가 있는데,

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    int N;
    cin >> N;
    
    stack<int> s;
    string cmd;
    
    while (N!=0) {
        cin >> cmd;
        
        if (cmd == "push") {
            int x;
            cin >> x;
            s.push(x);
        }
        else if (cmd == "pop") {
            if (s.empty()) cout << -1 << '\n';
            else {
                cout << s.top() << '\n';
                s.pop();
            }
        }
        else if (cmd == "size") {
            cout << s.size() << '\n';
        }
        else if (cmd == "empty") {
            cout << (s.empty() ? 1 : 0) << '\n';
        }
        else if (cmd == "top") {
            if (s.empty()) cout << -1 << '\n';
            else cout << s.top() << '\n';
        }
        N--;
    }
}

10828번 스택 1 - 실버4

 

위 예제처럼 내장 함수를 사용하여 구현 할 수 도 있으며,

#include <iostream>

using namespace std;;
int array[1000000] = {};
int top = 0;
void pop() {
    if (top != 0) {
        cout << array[top-1] << "\n";
        array[top-1] = 0;
        top--;
    }
    else {
        cout << -1 << "\n";
    }
}

void push(int x) {
    array[top] = x;
    top++;
}

void isEmpty() {
    if (top == 0) {
        cout << 1 << "\n";
    }
    else {
        cout << 0 << "\n";
    }
}

void peek() {
    if (top != 0) {
        cout << array[top-1] << "\n";
    }
    else {
        cout << -1 << "\n";
    }
}

void len() {
    cout << top << "\n";
}

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

    int n, commend, x;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> commend;
        if (commend == 1) {
            cin >> x;
            push(x);
        }
        else if (commend == 2) {
            pop();
        }
        else if (commend == 3) {
            len();
        }
        else if (commend == 4) {
            isEmpty();
        }
        else {
            peek();
        }
    }
}

28278 스택 2 - 실버 4

 

직접 배열에 각 명령어를 함수로 구현하는 방법이 있다.