[자료구조 C 언어] C 프로그래밍 자료구조 - 4 : 배열을 사용한 스택 (Stack)

이번 게시물에서는 배열을 사용해 스택을 구현해보겠습니다.

 

 

스택 (Stack)

 

아래가 막혀있는 원통에 물건을 담았다가 꺼내는 것을 생각하시면 됩니다.

 

가장 먼저 넣었던 것이 제일 아래에 깔리고, 가장 마지막에 있는 것이 제일 위에 위치합니다.

 

즉, 스택은 후입선출 혹은 LIFO (Last In First Output)입니다.

 

1) 스택의 ADT

 

 ADT Stack

 

- Create(max_size) : max_size만큼의 빈 스택을 생성

- IsFull(stack, max_size) : 꽉 찼는지 검사

- Push(stack, item) : 스택의 TOP에 데이터를 저장

- IsEmpty(stack) : 비었는지 검사

 

- Pop(stack) : 스택의 TOP에서 데이터를 반환

 

스택은 위와 같은 함수로 이루어집니다.

 

물론 필수는 아니고 본인의 취향에 맞게 구현하시면 됩니다.

 

저는 지금까지 배운 개념을 복습할 겸 코딩 해보는 것을 선호하기 때문에

 

일반적으로 많은 자료에서 보여주는 max_size를 받아서 고정된 스택을 생성하는 것이 아닌

 

제가 데이터를 넣으면 넣는데로 계속 늘어나는 스택을 만들어보겠습니다.

 

2) 배열을 사용한 스택의 구현

 

일단 스택과 큐에서 계속 사용할 함수를 설명하겠습니다.

 

 

#include <stdio.h>     // 프로그램의 최상단에 선언되어 있습니다.

#include <stdlib.h>    // 함수는 실제로 선언된 순서대로 설명드립니다.

 

 

int *stack;

 

int top = -1;

 

 

 

1] 데이터 입력 함수

 

함수의 목적은 "입력한 데이터를 배열로 반환해주는 것"입니다.

 

주석을 보시면 충분히 이해하실 수 있습니다.

 

 

int *InputData(void){ // 목적! 넣고싶은 데이터 갯수를 입력받고, 배열을 데이터 갯수만큼 동적할당 받아서 반환해준다.

    

    int *data;    //    동적할당 받아야해서 포인터로 선언했습니다. 포인터는 배열과 비슷한 동작을 수행할 수 있습니다. (상수와 변수의 차이!)

    int num;      //    밑에서

    

    printf("Insert number you want to push in stack:");

    scanf("%d", &num);    //    스택에 넣고싶은 데이터의 갯수를 입력합니다.

    

    printf("%d\n", num);

    

    data = (int *)malloc(sizeof(int) * ((num)+1));    // malloc : 할당된 메모리의 '주소'가 void* 형으로 리턴된다.

                                                      // data 배열의 첫번째 요소 (data[0])는 데이터 갯수를 저장합니다.

                                                      // 그렇기 때문에 동적할당 되는 크기는 num+1 입니다.

    printf("Insert data you want to push in stack\n");

 

    for(int i = 0; i < (num +1); i++){

        if(i == 0){

            printf("data[%d] = the number of data array\n", i);    // 배열의 첫번째 요소는 데이터의 갯수입니다.

            data[0] = num;

        }

        else{

            printf("data[%d] = ",i);    // 넣고싶은 데이터를 입력받아 데이터에 저장합니다.

            scanf("%d", &data[i]);

        }

 

    }

    

    printf("\n");

    

    for(int i = 0; i < (num +1); i++)    // 그냥 잘 넣었나 확인하는 구문입니다.

        printf("data[%d] = %d\n", i, data[i]);

    

    return data;    // 원하는 데이터를 저장한 포인터 변수 data를 반환합니다.

                    //해당 변수의 자료형은 (int *)이기 때문에 함수도 int *로 선언해줘야합니다.

                    //(int *InputData(void))

 

}

 

 

 

2] Push 함수

 

스택의 내부에 데이터를 밀어넣습니다. 

 

그래서 push라고 쓰는 것 같아요.

 

'top'은 스택의 최상단 데이터의 위치를 가리킵니다.

 

마찬가지로 주석을 보면서 천천히 따라오시면 됩니다.

 

모든 주석은 제가 공부하고 구현 하면서 느낀 의식의 흐름입니다.

 

 

 

void push(int *val){ // InputData로 받은 배열을 stack에 넣는다.

     // val에는 앞서 반환해줬던 data가 들어갑니다. 즉, val = data 입니다.

 

    int num;

    num = val[0]; // data[0] = the number of data array

 // data의 첫번째 요소인 사용자가 입력한 요소의 갯수를 저장합니다.

    

    int *stack_temp;    // 저는 계속 스택의 크기를 가변하므로 이전 스택의 데이터를 잠시 저장합니다.

 // 이후 새로 만든 스택에 이전에 저장한 데이터를 옮겨담습니다. 

    stack_temp = stack;

    

    free(stack);    // 이전에 할당한 stack의 메모리를 해제 해줍니다.

    stack = (int *)malloc(sizeof(int) * (num + (top+1)));    // 새로 stack의 메모리를 할당해줍니다.

// 이때 크기는 새로 들어 올 데이터 갯수(num) + 이전 스택에 남아있던 데이터의 갯수 (top+1)입니다.

 

    if(top == -1){    // top의 초기값은 0이 아니라 -1입니다. top이 0이면 stack[0]에 데이터가 있어야합니다.

        printf("It doesn't have data yet.\n");

    }

    else{

        for(int i = 0; i <= top; i++){    // 이전 스택에 남아있던 데이터 갯수 만큼 새로 만든 스택에 옮겨담습니다.

            stack[i] = stack_temp[i];

        }

    }

        

    for(int i = 1; i <= num; i++){

        stack[++top] = val[i];    // 이제 top을 하나씩 늘리며 새로 받아온 데이터를 스택에 집어넣습니다.

//        printf("stack[%d] = %d\n", top, stack[top]);

    }

    

 

}

 

 

 

 

 

3] Pop 함수

 

함수의 목적은 "원하는 갯수 만큼 스텍에서 데이터를 빼낸다."입니다.

 

 

 

void pop(unsigned int num){ // 빼내고 싶은 데이터의 갯수를 입력합니다.

    

    if(top < 0){    // top이 0 미만, 즉, -1이면 스택 내에 데이터가 없습니다.

        printf("Stack is empty.\n");

    }

    else{

        int poped_stack[num];    // 빠져나갈 데이터를 담을 배열을 선언해줍니다.

                                 // 사실 나중에 빠진 데이터를 반환 해줄까 해서 만든 배열입니다.

        for(int i = 0; i < num; i++){

            if(top < 0){    // 빠져나가는 중에 top이 -1이 되면 더이상 데이터가 없으므로 반복문을 중지합니다.

                printf("Stack is empty.\n");

                break;

            }

            poped_stack[i] = stack[top--];    // 스택에서 데이터가 빠져나갈 때마다 top을 한 단계 씩 낮춰줍니다.

            printf("poped_stack[%d] = %d\n", i, poped_stack[i]);

        }

    }

 

}

 

 

 

 

4] main 함수 및 실행 결과

 

함수 내부에 약간의 출력 함수를 추가했습니다. 

 

 

#include <stdio.h>

 

#include <stdlib.h>

 

int *stack;

int top = -1;

 

int *InputData(void){

    

    int *data;

    int num;

    

    printf("Insert number you want to push in stack:");

    scanf("%d", &num);

    

    printf("%d\n", num);

    

    data = (int *)malloc(sizeof(int) * ((num)+1)); // malloc : 할당된 메모리의 '주소'가 void* 형으로 리턴된다.

    

    printf("Insert data you want to push in stack\n");

 

    for(int i = 0; i < (num+1); i++){

        if(i == 0){

            printf("data[%d] = the number of data array\n", i);

            data[0] = num;

        }

        else{

            printf("data[%d] = ",i);

            scanf("%d", &data[i]);

        }

 

    }

    

    printf("\n");

    

    for(int i = 0; i < (num+1); i++)

        printf("data[%d] = %d\n", i, data[i]);

    

    return data;

}

 

void push(int *val){

    int num;

    num = val[0];

 

    int *stack_temp;

    stack_temp = stack;

    

    free(stack);

    stack = (int *)malloc(sizeof(int) * (num + (top+1)));

    

    puts("\nTramsplant starts");

    if(top == -1){

        printf("Stack is empty.\n");

    }

    else{

        for(int i = 0; i <= top; i++){

            stack[i] = stack_temp[i];

            printf("stack[%d] = %d\n", i, stack[i]);

        }

    }

    puts("Tramsplant is complete.\n");

    

    for(int i = 1; i <= num; i++){

        stack[++top] = val[i];

    }

    

}

 

void pop(unsigned int num){

    

    if(top < 0){

        printf("Stack is empty.\n");

    }

    else{

        int poped_stack[num];

        

        for(int i = 0; i < num; i++){

            if(top < 0){

                printf("Stack is empty.\n");

                break;

            }

            poped_stack[i] = stack[top--];

            printf("poped_stack[%d] = %d\n", i, poped_stack[i]);

        }

    }

}

 

void PrintStack(void){

    

    puts("\nPrinting stack starts.");

    if(top < 0){

        printf("Stack is empty.\n");

    }

    else{

        int num;

        num = top;

        

        while(num != -1){

            printf("stack[%d] = %d\n", num, stack[num]);

            num--;

        }

    }

    

    puts("Printing stack is complete.\n");

}

 

int main(void){

    

    push(InputData());

    

    PrintStack();

    

    push(InputData());

    

    PrintStack();

    

    pop(3);

    pop(4);

    pop(3);

    

    return 0;

 

}

 

 

 

출력결과

사용자가 원하는 수만큼 데이터를 스택에 저장하고, 저장된 스택을 잘 출력하고 있습니다.

원하는 수만큼 (3개(0, 1, 2)->4개(0, 1, 2, 3)->3개) 빠져나오다가 더이상 데이터가 없을 때 정지합니다.

 

다음 게시물에선 배열을 사용해서 큐를 규현해보겠습니다.