자료구조 - 스택

자료구조 - 스택

지금까지 구현해왔던 list와 다를 바가 없다.

stack은 LIFO(Last In - First Out)구조로 list 구현하는 것과 같다. 물론 배열로도 구현 가능하다.

기존 list 구조체에서는 노드를 가르키는 head, tail 포인터로 구성되어 있지만

stack은 Node의 삽입, 삭제가 일어나는 Top, 처음 Node를 가르키는 Bottom을 가지고 있다. 

삽입을 Push, 삭제를 Pop으로 구현한다.

편의상 이중 링크드 리스트로 구현하였다. 원하는 것으로 구현해도 상관없다. 

1. 구조체 구현

기존에 구현했던 node, list 구조체와 동일하지만 stack에서 top, bottom 포인터의 이름만 변경하여 구현하였다.

(무조건 이런 이름으로 구현하라는 것은 아니다.)

typedef struct _node{

    int value;

    struct _node *next;

    struct _node *prev;

}node, *nptr;

typedef struct _stack{

    nptr top;

    nptr bottom;

    int count;

}stack;

2. init 구현

stack *init_stack()

{

    stack *sptr = (stack*)malloc(sizeof(stack));

    sptr->top = NULL;

    sptr->bottom = NULL;

    sptr->count = 0;

    return sptr;

}

3. push 구현

- new_node를 생성하고 값들을 정해준다.

- 처음 추가될 때는 top, bottom 모두 new_node를 가르킨다.

- 2개 이상일 때는 top이 가르키는 노드의 next, new_node->prev, 현재 top이 가르키는 노드를 update 시켜주면 된다.

void push_stack(stack *sptr, int _value)

{

    node *new_node = (node*)malloc(sizeof(node));

    new_node->value = _value;

    new_node->next = NULL;

    new_node->prev = NULL;

    if(sptr->count == 0)

    {

        sptr->top = new_node;

        sptr->bottom = new_node;

    }

    else

    {

        sptr->top->next = new_node;

        new_node->prev = sptr->top;

        sptr->top = new_node;

    }

    sptr->count++;

}

4. pop  구현

- 삭제할 노드를 더미로 저장하고 삭제할 노드 전 노드의 next만 NULL 로 변경해주고 메모리 해제해주면 깔끔히 삭제된다.

void pop_stack(stack *sptr)

{

    nptr remove;

    if(sptr->count == 0)

    {

        printf("out of range\n");

    }

    else if(sptr->count == 1)

    {

        remove = sptr->top;

        sptr->top = NULL;

        sptr->bottom = NULL;

        sptr->count--;

        free(remove);

    }

    else

    {

        remove = sptr->top;

        remove->prev->next = NULL;

        sptr->top = remove->prev;

        free(remove);

        sptr->count--;

    }

}

5. print  구현

void printf_stack(stack *sptr)

{

    nptr tmp;

    if(sptr->count == 0)

    {

        printf("No Value\n");

    }

    else

    {

        tmp = sptr->bottom;

        printf("Value : ");

        while(tmp != NULL)

        {

            printf("%d ", tmp->value);

            tmp = tmp->next;

        }

        printf("\ncount value : %d\n",sptr->count);

    }

}