C언어를 통한 자료 구조(1)-stack

스택(stack)이란 각각의 원소들의 push와 pop을 리스트의 한쪽 끝에서만 이루어지게 만들어진 선형 자료구조이며 push와 pop이 이뤄지는 리스트의 끝을 top이라 부른다.

이 자료구조 형태에서 스택의 top에 새로운 원소를 삽입하는 것을 push라 하고, 가장 최근에 삽입된 원소를 의미하는 스택의 top으로부터 한 원소를 제거하는 것을 pop이라 한다. 이와 같이 스택은 항상 스택의 top에서만 발생하게 됨으로 top 포인터의 값을 1씩 증가 또는 감소시킴으로써 수행된다.

----Stack with linkedlist

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

typedef struct _node {
  int value;
  struct _node* next;
}node;

typedef node* nptr;

typedef struct _stack {
  int count;
  nptr top;
}stack;

void init(stack* sptr) {
  sptr->count = 0;
  sptr->top = NULL;
}

void push(stack* sptr, int value) {
  nptr new_nptr = (nptr)malloc(sizeof(_node));
  new_nptr->next = sptr->top;
  new_nptr->value = value;
  sptr->top = new_nptr;
  sptr->count++;
}

int pop(stack* sptr) {
  if (sptr->top != NULL) {
    nptr temp = sptr->top;
    sptr->top = temp->next;
    int pop_value = temp->value;
    free(temp);
    sptr->count--;
    return pop_value;
  }
  else {
    printf("No item is in this stack");
    return -1;
  }
}

int get_count(stack* sptr) {
  return sptr->count;
}

void free_stack(stack* sptr) {
  while (sptr->top != NULL) {
    pop(sptr);
  }
  free(sptr);
}

int main() {
  stack* mystack = (stack*)malloc(sizeof(stack));
  init(mystack);

  push(mystack, 1);
  push(mystack, 2);
  push(mystack, 3);
  push(mystack, 4);
  push(mystack, 5);
  push(mystack, 6);

  printf("count: %d.\n", get_count(mystack));

  printf("%d\n", pop(mystack));
  printf("%d\n", pop(mystack));
  printf("%d\n", pop(mystack));
  printf("%d\n", pop(mystack));
  printf("%d\n", pop(mystack));

  free_stack(mystack);
}