[자료구조] 간단한 스택을 만들어보자 1

종종 우리가 메모리 구조를 보게 되는 경우가 있다. 그 중 스택이라는것을 많이 들어보았을 것이다. 

대표적인 선형구조의 자료구조인 스택에 대해서 간단하게 구현해보자.

 

스택을 구현하기 전 간단하게 스택에 대한 개념을 잡고 가자.

먼저 사진을 밑 사진을 보자

사진을 보면, 빈 스택에 데이터가 차곡차곡 쌓이는것을 볼 수 있다. 이것을 우리는 스택에서 push라고 부른다. 

그리고 다시 스택에 있던 데이터가 밖으로 나가는것을 볼 수 있다. 이것을 우리는 pop이라고 부르자.

 

위 사진을 자세히 보았다면 스택의 특이한 점을 알 수 있을 것이다. 

 

보는것처럼 스택에는 출입구가 한곳밖에 없다. 

우리는 이것을 LIFO(Last In First Out)이라고 부르기로 했어요.

 

말그대로 가장 늦게 들어온 데이터가 가장 먼저 나간다는 의미이다. 

 

추가로 스택의 push와 pop에 대해서 주의할 점이 있다. 

스택의 크기보다 더 많은 데이터가 push 된다면, 스택은 Stack Overflow가 발생한다.

#include <stdio.h>

void a(){
	a();
}

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

예를 들어보자면 위 코드처럼 끊임없이 재귀를 호출한다면, Stack Overflow가 발생한다.

 

반대로 스택에 데이터가 없는데, pop을 한다면, 스택은 Stack Underflow를 출력한다. 

 

이제 본격적으로 코드를 구현해보자. 

 

직접 코드를 실행하여보고, 스택의 개념을 생각해보며, 코드를 따라가보자. 

#include <stdio.h>
#include <stdlib.h>

int input(const char* msg);
void push(int* stack, int* ESP, int data, int SIZE);
void pop(int* stack, int* ESP);
void peek(int* stack, int* ESP);

int main(){
    int ESP = 0;
    int stack_size = input("stack size: ");
    int* stack = (int *)malloc(sizeof(int)*stack_size);

    // stack control
    push(stack, &ESP, stack_size, 20);
    peek(stack, &ESP);
    pop(stack, &ESP);

    free(stack);
    return 0;
}

void push(int* stack, int* ESP, int SIZE, int data){
    if(SIZE == (*ESP)){
        printf("Stack OverFlow!\n");
        return ;
    }
    stack[(*ESP)++] = data;
}

void pop(int* stack, int* ESP){
    if((*ESP) == 0){
        printf("Stack UnderFlow\n");
        return ;
    }
    printf("pop : %d\n", stack[--(*ESP)]);
}

void peek(int* stack, int* ESP){
    if((*ESP) == 0){
        printf("None");
        return ;
    }
    printf("peek : %d\n",stack[(*ESP)-1]);
}

int input(const char* msg){
    int number;
    printf("%s", msg);
    scanf("%d", &number);
    return number;
}

 

배열과 동적할당을 이용하여 간단하게 스택을 구현해보았다. 

자료구조 중 첫번째인 스택에 대해서 구현을 해보았다.