스택!

스택은 아주 중요한 자료구조라서, 시스템 내부의 기본 동작에서부터 고오오오급 알고리즘 까지 다양하게 활용된다.

스택을 구현할때에는 여러가지 방법들이 있겠지만, 배열과 리스트를 이용해서 구현을 해볼 생각이고 이번에는 먼저 스택의 기본적인 개념과 함께 먼저 배열로 구현을 해보려고 한다!

---

스택의 개념

스택의 구조는 매우매우매우매우매우 간단하다!

스택은 그냥 바닥이 막힌 긴 통이라고 생각하면 된다.
따라서 바닥이 막힌 긴통은 무언가를 넣는곳과 무언가를 빼내는 곳이 같다. 즉 입구와 출구가 동일하다는 소리!

이 말은, 먼저 들어간 것은 아래쪽에 위치하게되고, 나중에 들어간 것은 위쪽에 위치하게 된다.

그러면 가장 나중에 들어간것이 가장 먼저 빠져나올 수 있게되는 구조인데, 이걸 LIFO(Last In First Out) 구조라고 한다.

---

배열로 구현하는 스택

배열로 스택을 구한할때는 위에 그림과 같은 모양이 된다! (keynote로 한땀한땀 그리는거 쉽지않은듯 ㅠ)

스택의 긴 통은 배열로 정의하고, 스택의 가장 상단은 Top이라는 인덱스를 통해서 유지 및 관리한다.

배열의 성격상 스택의 길이(배열의 크기)가 미리 정해져 있어야 하는데, 편의상 최대 크기를 10이라고 하자.

#define MAX 10

int STACK[MAX];
int TOP;

여기서 신경써야 할 부분은 바로 Top이 가르키는 위치가 정확히 어디인지 엄밀하게 규정되어야 한다는것이다.

어떤 경우에는 Top이 스택의 가장 윗부분의 데이터를 가리키는게 아니라 그 바로 위, 즉 다음의 데이터가 들어올 공간을 가리킬수도 있고 아니면 스택의 가장 윗 자료의 위치를 가리키기도 할거다.

이건 선택의 문제이긴 하지만 명확하게 해야할 필요가 있다.

극단적으로 생각해보면 스택은 완전히 비어있을수도, 가득차있을수도 있는데 완전히 비어있을 경우를 생각해보면 Top은 0이 아니라 -1을 가리켜야 한다.

왜냐면 배열의 시작은 0부터 시작하게되고, Top이 0이라는건 스택에 하나의 자료가 있다는 의미가 되기 때문이다.

그래서 스택을 초기화 할때는 Top이 -1이 되도록 설정해주면되고, 나는 Top은 스택의 가장 윗부분을 가리키도록 해서 사용할 예정이다.

그리고 스택에 데이터를 넣는 Push 동작과, 저장된 데이터를 꺼내오는 Pop 동작만 있다면 배열로 구현하는 Stack 구현은 끝난다!

---

Push

Push동작은 말 그대로 스택에 어떤 값을 밀어넣는걸 의미한다.

따라서 Push 함수를 작성할때 스택에 집어넣고 싶은 값을 함수의 인자로 같이 받아야 한다.

int push(int value) {
    if(TOP >= MAX - 1) {
        printf("\nstack overflow\n");
        return -1;
    }
    STACK[++TOP] = value;
    return value;
}

참고로 스택은 양의 정수만 저장한다고 가정하고 작성해서, 반환값이 음수라면 에러를 의미한다.

푸시 함수에서 신경써야 할 부분은 바로 Stack Overflow이다.

말 그대로 스택이 넘쳐버리는걸 의미하는데, 스택에 더 이상 데이터를 저장할 수 없음에도 불구하고 저장하려는 시도를 하게되면 스택이 넘치게 된다.

따라서 배열의 마지막 인덱스는 배열의 길이 - 1 이므로, 현재 스택의 가장 최상단의 인덱스를 가리키는 Top의 값을 항상 확인하고 푸시 동작을 해야한다.

---

Pop

Pop은 Push와 반대되는 동작이다.

Push가 스택에 데이터를 밀어넣는 동작이라면 Pop은 스택에서 데이터를 꺼내오는 동작을 의미한다.

Pop의 동작은 매우 간단한데, Stack[Top] 과 같이 현재 스택의 가장 최상단에 위치한 값을 반환하고 Top의 값을 1 감소시켜주면 된다.

한가지 신경써줘야할 부분은 바로 Stack Underflow인데, 말 그대로 스택이 텅 비어있는 경우를 의미한다.

이 경우는 스택에서 꺼내올 값이 하나도 없는 상태이기 때문에 stack underflow에 맞는 동작을 처리해주면 된다.

int pop(void) {
    if(TOP < 0) {
        printf("\nstack underflow");
        return -1;
    }
    return STACK[TOP--];
}

---

전체코드

//
//  main.c
//  Stack_Array
//
//  Created by 박재현 on 2024/05/07.
//

#include <stdio.h>

#define MAX 10

int STACK[MAX];
int TOP;

void init_stack(void) {
    TOP = -1;
}

int push(int value) {
    if(TOP >= MAX - 1) {
        printf("\nstack overflow\n");
        return -1;
    }
    STACK[++TOP] = value;
    return value;
}

int pop(void) {
    if(TOP < 0) {
        printf("\nstack underflow");
        return -1;
    }
    return STACK[TOP--];
}

void print_stack(void) {
    printf("\nValues of stack from Top to Bottom as below\n");
    for(int i = TOP; i >= 0; i--) {
        printf("%-6d", STACK[i]);
    }
    printf("\n");
}

int main(int argc, const char * argv[]) {
    int n;
    init_stack();
    
    printf("\nPush 5, 4, 7, 8, 2, 1\n");
    push(5);
    push(4);
    push(7);
    push(8);
    push(2);
    push(1);
    print_stack();
    
    printf("\nPop!");
    n = pop();
    print_stack();
    printf("Pop value is %d\n", n);
    
    printf("\nPush 3, 2, 5, 7, 2");
    push(3);
    push(2);
    push(5);
    push(7);
    push(2);
    print_stack();
    
    printf("\nCurrently stack is full, then try to push 3!!");
    push(3);
    print_stack();
    
    printf("Initialize stack");
    init_stack();
    print_stack();
    
    printf("\nCurrently stack is empty, then try to pop something!!");
    n = pop();
    print_stack();
    printf("\nPop value is %d\n", n);
    
    return 0;
}

실행결과