C언어 | 스택(Stack) 만들기 | 동적 할당 | POP, PUSH 함수 |자료구조

스택(Stack) 자료구조

스택은 우리 생활에서 흔히 보이는 자료구조다.

접시를 쌓아놓은 모습을 스택이라고 한다.

맨 아래 접시를 사용하기 위해서는 꽤 많은 사람이 식사를 해야 한다.

웹브라우저의 URL 도 스택을 사용한다. 뒤로가기를 누르면 마지막에 열람한 인터넷 주소로 돌아간다. Ctrl-Z 로 되돌리기도 스택이다. 마지막에 한 행동을 기억해놨다가 그 행동을 취소한다. 스택의 구조를 LIFO 라고 한다. LAST IN FIRST OUT 마지막에 온 데이터가 먼저 나온다. FIFO FIRST IN FIRST OUT 먼저 온 사람이 먼저 서비스를 받는다. FIFO 를 사용하는 큐와 대비된다.

살다 보면 항상 먼저 일어난 일이 나중에 끝난다는 법이 없는 것 처럼 Stack 은 가장 최근에 일어난 일을 소환한다.

(벼락치기 시험공부도 스택에 가깝다. 마지막에 본 내용이 기억이 더 잘난다)

스택의 구현

이 포스팅은 C언어로 스택을 구현한다.

구현하기 쉬운 자료구조에 속하지만 알아두면 유용하다.

스택에서 중요한 기능은 Push 와 Pop 이다. Push 는 값을 맨 위에 입력하고 Pop 은 맨 위의 값을 빼낸다.

데이터의 교환이 맨위에서 일어나기 때문에 입력과 출력 시간이 짧다. 시간복잡도가 O(1)

검색이나 정렬이 가능하나 적합하지는 않다. 스택의 목적이 검색이 아니니까...

* 스택 구조는 컴퓨터 애플리케이션에서도 다양하게 쓰이고 있다.

- 프로그래밍 언어의 스택메모리

- 함수호출시 (재귀함수도 사용)

- 역추적 (BackTracing)

- 십진수를 이진수로 변환할 때 등...

스택구현하기 (동적 메모리 할당)

- 배열로도 만들 수 있지만 동적 메모리를 사용할 것이다. 그러면 스택이 아니라 히프(heap) 영역에 생성된다. 배열은 크기제한이 있지만 히프영역을 사용하면 크기를 늘리거나 줄일 수 있다. (realloc 함수 사용)

자료형을 만든다.

- top 은 맨위의 인덱스이다.

- *data 포인터로 배열을 사용할 것이다.

- max는 스택의 최대 크기이다.

*스택을 초기화한다.

stk->data 에 메모리를 할당 받아 둔다. top 은 -1 이다. 배열의 인덱스로 사용할 것이다. stk->top +1 이되면 배열 0번째(첫번째)다. stk->max 는 매개변수로 받아 스택의 크기를 입력한다.

* PUSH 다.

top 이 max-1 인 경우: 스택의 크기 5인 경우 max-1 = 4 top 은 -1, 0, 1, 2, 3 까지 입력할 수 있다. 6번째가 되면 스택사이즈를 두배로 재할당하여 값을 입력한다.

* POP 은 맨위에 있는 자료를 꺼낸다. stk->top 은 1개의 자료가 있을 때 값이 0이다. 즉 0보다 크면 실행한다.

stk->data[stk->top] 에서 top은 맨위 인덱스가 된다. 값을 하나 꺼내면 top을 하나 내려야 한다. 메모리 할당과는 상관이 없다. 스택에 사용할 공간은 그대로 남아있어서 또 PUSH 와 POP을 하면 된다.. POP의 특징은 하나의 값을 받아올 때 자료에서는 삭제하고 와야한다. 그래야 다음 자료를 사용할 수 있다. 다른 구조는 하나의 값을 가져온다고 삭제하지는 않는다. 이것은 스택의 특징적인 부분이다.

위의 Push 와 Pop 을 구현했다면 스택을 보여주는 함수도 만들 수 있다. 데이터를 보여줄 때 역순으로 보여줘야 한다. 역순이 곧 꺼내오는 순서이다.

그외 다른 함수들은 한두줄로 어렵지 않으니 전체 소스코드를 참고한다.

* 전체 소스코드 - 스택 구현

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


#define print(x) printf("%d\n", x)
#define printp(x) printf("%p\n", x)
#define Line printf("/* ----------------------------- */\n\n")
#define toString(name) #name



typedef struct stack{
    int top;
    int *data;
    int max;
}Stack;


void StackInitialize(Stack* stk, int size);
void StackPush(Stack* stk, int value);
int StackPop(Stack* stk);
int StackPeek(Stack* stk);
int StackSize(Stack* stk);
int StackIsEmpty(Stack* stk);
int StackShow(Stack* stk);
int getRandomInt(int from, int to);
void deleteStack(Stack* stk);

int main(int argc, char const *argv[])
{
    srand(time(NULL));

    Stack s;
    StackInitialize(&s, 5);

    StackShow(&s);
    Line;

    for (int i = 1; i <= 12; i++)
    {
        int random = getRandomInt(1,50);
        StackPush(&s, random);
    }
    
    Line;

    StackPop(&s);
    StackPop(&s);
    StackPop(&s);

    StackShow(&s);
    deleteStack(&s);

    return 0;
}

/* ------------ 함수영역 ------------ */


// 초기화

void StackInitialize(Stack* stk, int size)
{
stk->data = (int*)malloc(size*sizeof(int));
stk->top = -1;
stk->max = size;
}

// Push

void StackPush(Stack* stk, int value)
{
    if (stk->top < stk->max-1)
    {
        stk->top++;
        stk->data[stk->top] = value;
        printf("-> value pushed: %d\n", value);
    }
    else
    {
        // 스택이 떨어진 경우 사이즈를 2배로 메모리 재할당. Push
        stk->max = stk->max*2;
        stk->data = (int*)realloc(stk->data, stk->max*sizeof(int));
        printf("[Memory reallocation] ");
        printf("Stack size doubled... size : %d\n", stk->max);
        StackPush(stk, value);
    }
}

// Pop

int StackPop(Stack* stk)
{
    if(stk->top >= 0)
    {
        int value = stk->data[stk->top];
        stk->top--;
        printf("-> value popped: %d\n", value);
        return value;
    }
    printf("*stack is empty...\n");
    return 0;
}

int StackPeek(Stack* stk)
{
    int value = stk->data[stk->top];
    return value;
}

int StackSize(Stack* stk)
{
    return(stk->top+1);
}

int StackIsEmpty(Stack* stk)
{
    return(stk->top == -1);
}

int StackShow(Stack* stk)
{
    if (StackIsEmpty(stk)){
        printf("stack is empty...\n");
    } else{
        printf("\n[Show Stack]\n");
        printf("*Stack Size: %d, Max Stack Size %d\n", StackSize(stk), stk->max);
        StackIsEmpty(stk) ? printf("(stack is empty)\n") :
                            printf("(stack is not empty)\n");
        printf("*top of the Stack : %d\n", StackPeek(stk));

        printf("[ ");
        for (int i = 0; i <= stk->top; i++)
        {
            printf("%d, ", stk->data[stk->top-i]);
        }
        printf(" ]\n");
        
    }
}

int getRandomInt(int from, int to)
{
    int random = rand() % (to-from+1) + from;
    return random;
}

void deleteStack(Stack* stk)
{
    free(stk);
    Line;
    printf("Stack [%s] is deleted...", toString(stk));
}