[c언어] 스택(Stack)

안녕하세요 업글입니다! 이번 포스팅에서는 스택에 대해서 설명드리겠습니다.

 

스택에 대한 설명

스택은 입력된 데이터들을 저장하고 저장된 순서와 반대로 데이터를 출력하는 자료구조입니다. 큐의 가장 큰 특징은 먼저 들어온 데이터는 가장 마지막에 나가는 것입니다. 이것을 후입선출 또는 LIFO이라고 주로 표현합니다. 쉽게 예를 들어서 접시 쌓기를 생각하시면 될 것 같습니다. 가장 먼저 정리한 접시가 가장 아래에 쌓여있고 가장 최근에 정리한 접시가 가장 위에 쌓여있기 때문에 가장 최근 쌓은 접시를 가장 먼저 사용하게 되는 것과 같이 데이터가 관리되게 됩니다. 스택 또한 큐와 동일하게 배열과 링크드리스트를 사용하여 구현할 수 있습니다.

 

스택 사용 이유

스택은 dfs(depth first search)와 같은 알고리즘에서 사용되며 후입선출을 해야하는 상황에서 유용하게 사용하게 됩니다.

 

대표적인 예로 redo, undo가 있을 것입니다. 파워포인트에서 ctrl+z를 누르게 되면 현재 작성된 상황에서 이전 상황으로 돌아가게 됩니다. 이러한 상황을 구현할 때 스택을 유용하게 사용할 수 있습니다. 스택에 작성 데이터들을 순차적으로 입력해놓으면 ctrl+z를 누를때마다 스택에서 이전에 작성된 상황(가장 최근에 입력된 작성 데이터)을 쉽게 불러올 수 있을 것입니다.

 

또 이름에서부터 느껴지듯이 스택메모리에서도 사용됩니다. a, b라는 함수가 있고 a함수에서 b함수를 호출한다고 가정해보겠습니다.

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#define NO (0)
#define YES (!NO)

void FunctionB()
{
    int32_t data[] = { 3, 4 };

    printf("FunctionB data1=%d, data2=%d, dataSum=%d\n", data[0], data[1], data[0] + data[1]);
}

void FunctionA()
{
    int32_t data[] = { 1, 2 };

    FunctionB();

    printf("FunctionA data1=%d, data2=%d, dataSum=%d\n", data[0], data[1], data[0] + data[1]);
}

int main()
{
    FunctionA();

    return 0;
}

FunctionA 호출 시 순서

1. FunctionA 호출

2. FunctionA의 data배열 스택에 저장

3. FunctionA의 현재주소(복귀주소) 스택에 저장

4. FucntionB 호출

5. FunctionB의 data배열 스택에 저장

6. FunctionB printf문 실행

7. FunctionB의 data배열 스택에서 삭제

8. FunctionA의 복귀주소 스택에서 읽기 및 삭제

9. FunctionA의 복귀주소로 복귀

10. FunctionA printf문 실행

11. Functionㅁ data배열 스택에서 삭제

 

위의 예시는 쉽게 설명하기 위한 예시이며 실제 함수가 분기될 때에는 추가적인 절차가 있음을 참고바랍니다.

 

 

배열을 이용한 스택 코드

typedef struct {
    int32_t* buf;
    uint32_t back;
    size_t size;
    size_t bufSize;
}ST_Stack;

int32_t StackInit(ST_Stack* stack, size_t stackSize)
{
    int32_t result;

    stack->buf = (int32_t*)malloc(sizeof(int32_t) * stackSize);

    if (stack->buf == NULL) {
        result = NO;
    }
    else {
        stack->back = 0;
        stack->size = 0;
        stack->bufSize = stackSize;

        result = YES;
    }
    
    return result;
}

void StackDelete(ST_Stack* stack)
{
    free(stack->buf);
    stack->back = 0;
    stack->size = 0;
    stack->bufSize = 0;
}

int32_t IsStackEmpty(ST_Stack* stack)
{
    int32_t result;

    if (stack->size == 0) {
        result = YES;
    }
    else {
        result = NO;
    }
    
    return result;
}

int32_t IsStackFull(ST_Stack* stack)
{
    int32_t result;

    if (stack->size == stack->bufSize) {
        result = YES;
    }
    else {
        result = NO;
    }

    return result;
}

void StackPush(ST_Stack* stack, int32_t data)
{
    if (IsStackFull(stack) == YES) {
        printf("stack is full\n");
    }
    else {
        stack->buf[stack->back] = data;
        stack->back++;
        stack->size++;
    }
}

int32_t StackPop(ST_Stack* stack)
{
    int32_t result = 0;

    if (IsStackEmpty(stack) == YES) {
        printf("stack is empty\n");
    }
    else {
        stack->back--;
        result = stack->buf[stack->back];
        stack->size--;
    }

    return result;
}

void StackPrint(ST_Stack* stack)
{
    int32_t i;

    for (i = 0; i < stack->size; i++) {
        printf("i=%d, %d\n", i, stack->buf[i]);
    }
}

int main()
{
    #define STACK_SIZE (8)
    #define POP_SIZE (4)

    ST_Stack stack;
    int32_t i;
    int32_t popData[POP_SIZE];

    StackInit(&stack, STACK_SIZE);

    StackPop(&stack);

    for (i = 0; i < STACK_SIZE; i++) {
        StackPush(&stack, i);
    }
    StackPush(&stack, 8);

    StackPrint(&stack);
    
    for (i = 0; i < POP_SIZE; i++) {
        popData[i] =  StackPop(&stack);
        printf("pop=%d\n", popData[i]);
    }

    StackPrint(&stack);
}

 

링크드리스트를 이용한 스택 코드

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#define NO (0)
#define YES (!NO)

typedef struct ST_Node {
    int32_t data;
    struct ST_Node* next;
    struct ST_Node* prev;
}ST_Node;

typedef struct {
    ST_Node* front;
    ST_Node* back;
    int32_t size;
}ST_Stack;

int32_t IsStackEmpty(ST_Stack* stack)
{
    int32_t result;

    if (stack->size == 0) {
        result = YES;
    }
    else {
        result = NO;
    }

    return result;
}

int32_t StackInit(ST_Stack* stack)
{
    int32_t result = YES;

    stack->front = NULL;
    stack->back = NULL;
    stack->size = 0;

    return result;
}

void StackDelete(ST_Stack* stack)
{
    int32_t i;
    ST_Node* temp;

    for (i = 0; i < stack->size; i++) {
        temp = stack->front;
        stack->front = stack->front->next;
        free(temp);
    }

    stack->front = NULL;
    stack->back = NULL;
    stack->size = 0;
}

void StackPush(ST_Stack* stack, int32_t data)
{
    ST_Node* addNode;

    addNode = (ST_Node*)malloc(sizeof(ST_Node));

    if (addNode == NULL) {
        printf("heap is full\n");
    }
    else {
        addNode->data = data;
        addNode->next = NULL;

        if (IsStackEmpty(stack) == YES) {
            addNode->prev = NULL;
            stack->front = addNode;
            stack->back = addNode;
        }
        else {
            addNode->prev = stack->back;
            stack->back->next = addNode;
            stack->back = addNode;
        }
        stack->size++;
    }
}

int32_t StackPop(ST_Stack* stack)
{
    int32_t result = 0;
    ST_Node* del;

    if (IsStackEmpty(stack) == YES) {
        printf("stack is emtpy\n");
    }
    else {
        result = stack->back->data;
        del = stack->back;
        stack->back = stack->back->prev;
        stack->size--;

        free(del);
    }

    return result;
}

void StackPrint(ST_Stack* stack)
{
    int32_t i;
    ST_Node* temp;

    temp = stack->front;
    for (i = 0; i < stack->size; i++) {
        printf("i=%d, %d\n", i, temp->data);
        temp = temp->next;
    }
}

int main()
{
#define POP_SIZE (4)

    ST_Stack stack;
    int32_t i;
    int32_t popData[POP_SIZE];

    StackInit(&stack);

    StackPop(&stack);

    StackPush(&stack, 0);
    StackPop(&stack);

    for (i = 0; i < STACK_SIZE; i++) {
        StackPush(&stack, i);
    }

    StackPrint(&stack);

    for (i = 0; i < POP_SIZE; i++) {
        popData[i] = StackPop(&stack);
        printf("pop=%d\n", popData[i]);
    }

    StackPrint(&stack);
}

이상 스택에 대한 설명을 마치도록 하겠습니다.