[Data Structure] 자료구조(2강) - Stack

• 수식이 제대로 보이지 않는다면, 새로고침(F5)을 해주시기 바랍니다.

자료구조 포스팅은 여러 자료 구조의 개념 및 c++로의 프로그래밍을 다룰 예정입니다. 자료 구조는 비교적 널리 알려져있고, 다른 곳에서도 잘 설명된 곳이 많기 때문에 자료구조에 한해서는 간단한 개념 및 구현만을 다루겠습니다. 간단히 정리된 것을 볼 수 있는 용도로 적합할 것 같습니다.
경쟁적 프로그래밍 문제 풀이에 유용한 c++의 STL의 헤더파일도 함께 다루겠습니다.

Stack

이번에 다룰 자료구조는 stack입니다. 후입선출(LIFO) 자료구조이며, 입구가 위에 있는 박스를 생각하시면 쉽습니다. 예를 들어 데이터를 1, 3, 4, 6을 순서대로 넣는다면, 꺼낼 때는 6, 4, 3, 1 순입니다.
Stack 클래스를 구현하면 아래와 같습니다. (에 있는 모든 기능을 구현한 것은 아닙니다.)

#include <iostream>
using namespace std;

class Stack {
private:
    int* arr;
    int capacity;
    int topIndex;

public:
    Stack(int size) {
        capacity=size;
        arr = new int[capacity];
        topIndex=-1;
    }
    ~Stack() {
        delete[] arr;
    };

    void push(int item){
        if (topIndex + 1 >= capacity) {
            cout << "Stack overflow\n";
        return;
    }
    arr[++topIndex] = item;
    }
    void pop() {
        if (empty()) {
            cout << "Stack underflow\n";
            return;
        }
        --topIndex;
    }

    int top() {
        if (empty()) {
            cout << "Stack is empty\n";
            return -1;
        }
        return arr[topIndex];
    }

    bool empty() {
        return topIndex<0;
    }
    int size() {
        return topIndex+1;
    }
};

int main() {
    Stack s(5);

    s.push(10);
    s.push(20);
    s.push(30);

    cout << s.top() << '\n';
    s.pop();

    cout << s.top() << '\n';
    cout << s.size() << '\n';
    cout << (s.empty() ? "Yes" : "No") << '\n';

    s.pop();
    s.pop();
    s.pop();

    return 0;
}

C++ <stack> 사용법 요약

함수	설명	예시
push(val)	값을 스택 맨 위에 추가	s.push(10);
pop()	맨 위의 요소 제거 (반환 없음)	s.pop();
top()	맨 위의 요소를 참조	s.top();
empty()	스택이 비어 있는지 확인	s.empty();
size()	현재 스택에 있는 요소 개수	s.size();