Stack/스택

스택은 데이터를 일시적으로 저장하기 위한 자료구조로 후입선출(LIFO, Last In First Out)이다.

말그대로 데이터를 쌓는다는 느낌으로 이해하면 된다 가장 나중에 쌓은 접시를 제일 먼저 사용하게 된다고

생각하면 이해하기 편할것이다.

 

#include <iostream>
using namespace std;

struct stk{
    int max;
    int ptr;
    int *stk;
};

int stk_init(stk* s, int max){ // 스택을 초기화
    s->ptr = 0;
    if((s->stk = new int[max]) == NULL){
        s->max = 0;
        return -1;
    }
    s->max = max;
    return 0;
}

int push(stk* s, int data){ // 스택에 데이터를 추가
    if(s->ptr >= s->max){
        return -1;
    }
    s->stk[s->ptr++] = data;
    return 0;
}

int pop(stk* s){ // 꼭대기에 있는 Data 제거
    if(s->ptr <= 0){
        return -1;
    }
    s->stk[--s->ptr];
    return 0;
}

int peek(const stk* s){  // 스택 꼭대기의 값을 반환
    if(s->ptr <= 0){
        return -1;
    }
    return s->stk[s->ptr-1];
}

void Clear(stk* s){ // 스택을 비우는 함수
    s->ptr = 0;
}

int capacity(const stk* s){ // 스택의 용량을 확인하는 함수
    return s->max;
}

int size(const stk* s){ // 스택의 현재 크기를 확인하는 함수
    return s->ptr;
}

int isEmpty(const stk* s){ // 스택이 비어있는지 확인하는 함수
    return s->ptr <= 0;
}

int isFull(const stk* s){ // 스택이 가득차있는지 확인하는 함수
    return s->ptr >= s->max;
}

int search(const stk* s, int key){ // 스택 안에서 데이터를 찾는 함수
    for(int i = s->ptr - 1; i >= 0; i--){
        if(s->stk[i] == key){
            return i;
        }
    }
    return -1;
}

void stk_terminate(stk* s){ // 스택을 삭제하는 함수
    if(s->stk != NULL){
        delete s->stk;
    }
    s->max = s->ptr = 0;
}

int main(){
    stk* s = new stk;
    stk_init(s,10);
    for(int i = 0; i < 10; i++){
        push(s,i);
        cout << peek(s) << " is push" << endl;
    }
    for(int i = 0; i < 10 ; i++){
        cout << peek(s) << " is pop" << endl;
        pop(s);
    }
    stk_terminate(s);
    return 0;
}

편하게 사용하려면 c++ stl에서 stack 헤더를 include 하면 된다. #include <stack>