[자료구조] Stacks

• ADT( abstract data type): 자료구조의 추상화(요약)
  
  • data가 저장되어 있어야 함
  • data에 대한 기능이 나타나야 함
  • 예외처리가 나타나야 함

---

• Stack ADT: 임의의 객체를 저장하는 ADT, 추가와 삭제는 후입선출(LIFO,last in first out)을 따른다.
• 주요 기능
  • push: 객체를 삽입
  • pop: 객체를 삭제

• 부가 기능
  • top: 가장 최근에 push된 객체를 반환
  • size: stack의 저장된 data의 수를 반환
  • empty: stack이 비어있는 지 판단
• 예외 처리
  • top -> stack이 비어 있는 경우
  • push -> stack의 size가 array가 수용가능한 공간 보다 커지는 경우 (array 기반 stack인 경우)
  • pop -> stack이 비어 있는 경우
• 수행 시간
  • stack에 들어있는 구성요소를 n이라 할때
  • 공간의 사용은 O(n)
  • 각 연산의 수행 시간은 O(1)

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

class stack{
public:
    int stack_size = 0;
    int capa = 10;//스택의 수용가능한 크기의 수에 대한 변수를 선언 임의의 값으로 선언
    int *arr = new int[capa];//capa만큼 저장할 수 있는 배열 선언
    stack(int t){//stack 생성자
        capa = t;//capa의 값을 받음
    }
    bool empty(){
        return (!stack_size);//stack_size가 0이 이면 true
    }
    void top(){//맨위에 있는 값 출력
        if(empty()){//스택이 비어있는 경우
            cout<< -1 <<endl;//-1출력
        }
        else{//스택이 비어있지 않은 경우
            cout<< arr[stack_size-1]<< endl;//arr의 stack_size-1번째 값 출력
        }
    }
    void push(int x){//top에 x 넣기
        if(stack_size<capa){//stack_size가 capa보다 작은 경우
            arr[stack_size] = x;//stack_size번째에 x추가
            stack_size++;//stack_size 추가
        }
        else{//stack_size가 capa보다 크거나 같은 경우
            cout<< "FULL"<< endl;
        }
    }
    void pop(){//top 삭제
        if(empty()){
            cout<< -1 <<endl;
        }
        else{
            top();
            arr[stack_size] = NULL;//top값을 NULL로
            stack_size--;//stack_size감소
        }
    }
};
int main() {
    int t = 0;//capa
    int n = 0;//명령어 수
    cin >> t >> n;
    stack st = stack(t);

    for (int i = 0; i < n; i++) {
        string cmd;
        cin >> cmd;
        int x;

        if (cmd == "empty") {
            if (st.empty()) {
                cout << "1\n";
            } else {
                cout << "0\n";
            }
        } else if (cmd == "top") {
            st.top();
        } else if (cmd == "push") {
            cin >> x;
            st.push(x);
        } else if (cmd == "pop") {
            st.pop();
        }
    }

    return 0;
}