[자료구조] 배열로 구현한 스택(stack)

1. 스택(stack)이란?

- 컴퓨터에서 많이 사용되는 자료구조 중 하나이다.

- 후입선출(LIFO : Last In First Out) 구조를 가지고 있다.

- 스택의 기본적인 연산으로 스택에 삽입하는 push 연산과 삭제하는 pop 연산이 있다.

- 스택의 맨 상단은 stack top이라 하고 맨 하단을 stack bottom이라 한다.

  스택의 입출력은 top에서만 일어난다. 

  즉 스택의 한쪽 끝에서만 삽입, 삭제하는 구조이다.

- 함수 호출 시 함수 실행이 끝나면 자신을 호출한 지점으로 다시 돌아가야 하기 때문에

  스택을 이용해 복귀할 주소를 저장한다.

 

2. 배열로 스택 구현하기

- 정수형 배열을 이용하여 스택을 구현해본다.

- push, pop 모두 배열의 top에서 이뤄진다.

#include <stdio.h>
#define STACK_SIZE 5

int stack[STACK_SIZE] = {0,};
int top = 0;

//스택이 다 찼는지 확인하는 함수.
int is_full(void){
    if(top >= STACK_SIZE){
        return 1;
    }else{
        return 0;
    }
}

//스택이 비었는지 확인하는 함수.
int is_empty(void){
    if(top <= 0){
        return 1;
    }else{
        return 0;
    }
}

//스택에 삽입
void push(int data){
    if(is_full()){
        printf("stack is full...\n");
    }else{
    	//스택의 top에 데이터를 삽입
        stack[top++] = data;
        printf("complete...\n");
    }
}

//스택에서 삭제
void pop(void){
    if(is_empty()){
        printf("stack is empty...\n");
    }else{
        //스택의 top 데이터 삭제
        top--;
        printf("complete...\n");
    }
}

//스택 배열 출력
void print_stack(int* stack_p){
    printf("stack data [ ");
    for(int i=0; i<top; i++){
        printf("%d ", stack_p[i]);
    }
    printf("]\n");
}

int main(int argc, const char * argv[]) {
    int input;
    int data;
    
    do{
        printf("1. push 2. pop 3. print 4. end\n");
        scanf("%d", &input);
        
        if(input == 1){
            printf("data : ");
            scanf("%d", &data);
            push(data);
        }else if(input == 2){
            pop();
        }else if(input == 3){
            print_stack(stack);
        }
        
    }while(input != 4);
    printf("end."); 
}