[자료구조]스택(Stack) - 배열

스택은 제한된 접근 방식의 행위적 측면을 부여받은 자료 구조이다. 

이러한 자료구조를 추상적 자료 구조(Abstract Data Structure)라고 한다. 

스택이 어떤 제한된 접근 방식과 행위적 부여 받았는지 지금부터 살펴보도록 하겠다. 

스택의 구조는 매우 간단한다. 스택은 밑이 막힌 긴 통이라고 보면 되겠다. 밑이 막힌긴 통은 무언가를 넣는 곳과 무언가를 통에서 빼내는 곳이 같다. 

입구와 출구가 같기 때문에 먼저 들어간 것은 밑에 있게 되고 나중에 들어간 것이 위에 있다.

그러면 제일 나중에 들어간 것이 제일 먼저 나오게 된다. 그래서 스택을 LIFO(Last In First Out) 구조라고 한다. 

스택을 프로그램에서 구현할 때에는 여러가지 방법이 있지만 가장 많이 사용되는 방법은 배열과 연결 리스트인 듯한다. 

그래서 오늘은 배열을 이용한 스택을 만들어 보도록 하겠다. 

#include <stdio.h>
 
//전역변수 
#define MAX 10    // 스택 길이
int stack[MAX]; // 스택 배열
int top;        // 스택 현위치
 
 
// 스택 초기화
void init_stack(void){
    // 스택을 초기화하는 함수이다. 
    // 스택에 아무 data가 없을 때를 초기화 해줘야 한다. 
    // 여기서 한가지 약속을 해야 한다. 스택의 현위치를 어떻게 결정할 것인가. 
    // 두가지 경우가 있을 수 있다. 
    // 첫째, 갯수로 현위치를 이용할 것인지
    // 둘째, 마지막 데이터가 들어있는 배열의 위치를 이용할 것인지
    // 두가지중 아무거나 사용해도 관계는 없다. 
    // 하지만 이번 예제에서는 배열을 이용하여 스택을 구현할 것이므로 후자를 선택하겠다. 
    // 그래서 배열의 시작 "0" 보다 1작은 "-1"을 데이터가 없는 것으로 하겠다. 
    
    top = -1;
}
 
// 데이터 추가 
int push(int addData){
    // 데이터를 추가할 때는 배열을 사용하고 있기 때문에 추가 가능한지 확인해야 한다. 
    // top이 (MAX - 1)보다 크거나 같을 경우 데이터를 추가 할 수 없다. 
    // 논리적으로 같은 경우만 확인하면 될 것같지만 안전하게 "이상"으로 추가여부를 판단하기로 하자. 
    if (top >= (MAX - 1)){
        printf("\n데이터를 더이상 추가할 수 없습니다.\n");
        return -1;
    }
 
    // ++top를 한 이유는 top는 마지막 데이터가 추가된 위치이기 때문에 
    // 새로운 데이터가 추가될 위치는 top의 증가 값이기 때문이다. 
    // 풀어서 쓰면
    // top = top + 1;
    // stack[top] = addData;
    stack[++top] = addData;
 
    return addData;
}
 
// 데이터 삭제
int pop(void){
    // 데이터를 삭제할 때는 배열을 사용하고 있기 때문에 삭제 가능한지 확인해야 한다. 
    // top가 -1이면 삭제할 데이터가 없는 것이다. 
    // 하지만 여기선 안전하게 0미만인 경우로 판단하기로 하자.
    if (top < 0){
        printf("\n삭제할 데이터가 없습니다.\n");
        return -1;
    }
 
    // top--를 한 이유는 top는 삭제되기전 데이터가 있는 자리이기 때문이다. 
    // 풀어서 쓰면
    // int removeData = stack[top]
    // top = top - 1;
    // return removeData;
    return stack[top--];
}
 
void print_stack(void){
    int i = 0;
    for (i = 0; i <= top; i++){
        printf("%d,", stack[i]);
    }
 
    printf("\n");
}
 
void main(void){
    int i = 0;
    init_stack();
 
    for (i = 0; i < MAX + 1; i++){
        if (push(i + 1) != -1){
            printf("%d를 추가하였습니다.\n", (i + 1));
        }        
        print_stack();
    }
 
    for (i = 0; i < MAX + 1; i++){
        if (pop() != -1){
            printf("데이터가 삭제되었습니다.\n");
        }        
        print_stack();
    }
 
    
 
}

소스에 이해를 돕기 위한 주석을 많이 달았다. 차근 차근 읽어 보면 알 수 있을 듯 싶다.