[자료구조론/C] 자료구조론 3편 스택

스택

LIFO구조의 자료구조라고 할 수 있겠다. 요즘 C++ STL을 배우고 있는데 vector 컨테이너로 stack을 구현하면 맛깔나게, 아니 vector 컨테이너가 스택구조를 기반으로 만들어졌다고 보는게 맞는 것 같다.

스택의 ADT

Push, Pop, Peek 이 세가지. 각각 넣고 빼고 확인하는 오퍼레이션이다. C로 구현한다고 하면

void StackInit(Stack * pstack);
int SIsEmpty(Stack * pstack);
void SPush(Stack * pstack, Data data); // C++이었다면 템플릿쓰면 되는데 아쉽
Data SPop(Stack * pstack);
Data SPeek(Stack * pstack);

정도가 되겠고 클래스가 없는 C의 경우 적절한 헤더파일과 구조체를 설계하면 된다. 배열기반으로 만드는 것이 편하기는 하지만, 연결리스트로 만드는게 더 연습에 도움될 것 같다.

연결리스트 기반의 스택 구현

• 헤더 파일

#ifndef __LB_STACK_H__
#define __LB_STACK_H__
#define TRUE 1
#define FALSE 0

typedef int Data;

typedef struct _node
{
  struct _node *next;
  Data data;
} Node;

typedef struct _listStack
{
  Node *head;
} ListStack;

typedef ListStack Stack;

void StackInit(Stack * pstack);
int SIsEmpty(Stack * pstack);
void SPush(Stack * pstack, Data data);
Data SPop(Stack * pstack);
Data SPeek(Stack * pstack);

#endif

• 첫번째 c파일

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

void StackInit(Stack *pstack)
{
  pstack->head = NULL;
}

int SIsEmpty(Stack* pstack)
{
  if(pstack->head == NULL) return TRUE;
  else return FALSE;
}

void SPush(Stack *pstack, Data data)
{
  Node *newNode = (Node*)malloc(sizeof(Node));
  
  newNode->data = data;
  newNode->next = pstack->head->next;
  pstack->head = newNode;
}

Data SPop(Stack * pstack)
{
  Data rdata;
  Node * rnode;
  
  if(SIsEpty(pstack)) {
    printf("Stack is Empty");
    exit(-1);
  }
  
  rdata = pstack->head->data;
  rnode = pstack->head;
  
  pstack->head = rnode->next;
  free(rnode);
  return rdata;
}

Data SPeek(Stack * pstack)
{
  if(SIsEmpty(pstack)) {
    printf("Stack is Empty");
    exit(-1);
  }
  
  return pstack->head->data;
}

• main file

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

int main(void)
{
  Stack stack;
  StackInit(&stack);
  
  SPush(&stack, 1);
  SPush(&stack, 2);
  SPush(&stakc, 3);
  
  while(!SIsEmpty(&stack))
    printf("%d ", SPop(&stack));
    
  return 0;
}

3 2 1이 출력될 것이다.

끝