[자료구조 - C언어] 스택(Stack)

Stack - LIFO형식

스택에서는 자료를 넣고 빼는 곳이 하나만 있는 LIFO(Last In First Out) 형식이다. 

즉, 제일 처음 들어간 자료가 가장 마지막에 나오게 된다. 

 

push

pop

 

<stack.h>

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

typedef struct node{
        char value;
        struct node *next;
}NODE;

NODE *stack_push(NODE *top_node, char value){

        NODE *new_top_node = NULL;
        new_top_node = (NODE*)malloc(sizeof(NODE));

        new_top_node->value = value;
        new_top_node->next = top_node;

        return new_top_node;
}

NODE *stack_pop(NODE *top_node, char *value){

        NODE *new_top_node = NULL;

        new_top_node = top_node->next;
        *value = top_node->value;

        free(top_node);
        return new_top_node;
}

 

• stack_push 함수

-> Linked List에서 사용했던 prepend 함수를 참고하여 새로 들어오는 자료를 top_node로 설정합니다. 그리고 push 함수에서는 새로운 자료형이 언제까지 들어올지 모르기 때문에 동적 메모리 할당이 필요합니다. 

 

• stack_pop 함수

-> 스택에서는 가장 나중에 들어온 자료가 제일 먼저 나가기 때문에 top_node에 있는 자료를 반환하고, top_node의 next를 top_node로 지정해줍니다. 그리고 pop 함수에서는 메모리를 비워내는 과정이므로 메모리 할당이 필요하지 않습니다. 또한, 마지막에 top_node를 free 하여 메모리 낭비를 방지합니다. 

 

<main.c>

#include"stack.h" #include"stack.h"
#include<stdio.h>

int main(int argc, char *argv[]){

        NODE *top_node = NULL;
        char c;

        for(c='A'; c<='Z'; c++){
                top_node = stack_push(top_node, c);
                printf("push : %c\n", c);
        }

        while(top_node != NULL){
                top_node = stack_pop(top_node, &c);
                printf("pop : %c\n", c);
        }

        return 0;
}

 

<출력창>

push

A~Z까지 push됨

 

pop

Z~A까지 pop됨

* push 된 순서 반대로 pop 된 걸 알 수 있다.

 

다음 글에서는 큐(Queue)에 대해 설명하겠습니다.

감사합니다!

 

2021.08.24