[C로 만드는 자료구조]스택(Stack) - 동적할당

스택(Stack) - 동적할당

이번에는 동적할당을 통해서 스텍을 구현해 보겠습니다. 우선 구현에 앞서서 동적 스택 구현에 사용된 구조체부터 보고 가겠습니다.

#include<cstdio>
#include<malloc.h>
typedef struct ELEMENT
{
    int item;
    ELEMENT *LINK = NULL;
}ELEMNT;
typedef struct STACK
{
    int top = 0;
    ELEMENT *HEADER = NULL;
}STACK;

아까와 같지만 이번에는 포인터를 이용하여 다음 노드를 가르킵니다. 연결 리스트와 같은 원리를 이용하는 것입니다. 이번엔 ADT 구현을 하나하나 살펴 보겠습니다. 이번에는 배열에서 구현한 것과는 다르게 앞에서 넣고 앞에서 빼는 형태입니다. 또한 배열과는 다르게 동적할당은 순차적으로 이루어 져 있지 않기 때문에 각 스택들의 첫 번째를 구분하기 위한 header 포인터도 추가되었습니다.

• PUSH()
  

  void PUSH(STACK *S,int ITEM)
  {
      if (S->HEADER == NULL)//첫 노드가 없는 경우
      {
          ELEMENT *NEW = (ELEMENT *)malloc(sizeof(ELEMENT));
          NEW->item = ITEM;
          NEW->LINK = NULL;
          S->HEADER = NEW;
          S->top += 1;
      }else//어떤 노드라도 있는 경우
      {
          ELEMENT *NEW = (ELEMENT *)malloc(sizeof(ELEMENT));
          NEW->LINK = S->HEADER;
          S->HEADER = NEW;
          NEW->item = ITEM;
          S->top += 1;
      }
  }

  헤더 포인터를 할당해주어야 하기 떄문에 제일 처음에 요소를 추가할 때와 그 이후의 추가에 대해서 구분을 하였습니다.
  
  

• POP()
  
  

  void POP(STACK *S)
  {
      if (S->HEADER == NULL)
      {
          printf("STACK is Empty\n");
          return;
      }
      ELEMENT *CUR = S->HEADER;
      S->HEADER = CUR->LINK;
      free(CUR);
      S->top -= 1;
  }

  앞에서 추가하기 때문에 header를 뒤로 옮겨주고 기존의 header가 가르키던 요소를 동적해제하여 주면 됩니다.
  
  

• PRINT()
  
  

  void PRINT(STACK *S)
  {
      ELEMENT *CUR = S->HEADER;
      while (CUR != NULL)
      {
          printf("%d->", CUR->item);
          CUR = CUR->LINK;
      }
      printf("\n");
  }

  연결 리스트와 같습니다. header를 움직이게 되면 나중에 다시 접근 할 수 없어지기 때문에 header값을 받아와서 다른 포인터로 수행하게 됩니다.
  
  

• PEEK()
  
  

  int PEEK(STACK *S)
  {
      return S->HEADER->item;
  }

  가장 위에 있는 값을 얻어오는 함수입니다. 앞쪽에 출입구가 있기 때문에 header 에 있는 값을 보여주게 됩니다.
  
  
   

다음 포스팅에서는 규(Queue)에 대해서 포스팅하겠습니다.