자료구조 - 배열로 구현한 스택(Array Stack)

 

가장 마지막에 들어간 데이터가 제일 먼저 나오고(Last In - First Out, LIFO)

가장 먼저 들어간 데이터는 가장 나중에 나온다.(First In - Last Out, FILO)

이러한 자료구조를 스택(stack, 건초더미)라 하며, 요소의 삽입 삭제가 자료의 한쪽 끝에서만 이루어진다.

따라서 스택의 주요 기능은 삽입(Push), 삭제(Pop)이다.

 

먼저 배열로 구현한 스택을 구현하겠다.

 

typedef int ElementType; typedef struct tagNode{ ElementType Data; }Node;

 

typedef struct tagArrayStack{ int Capacity; //용량 int top; Node* Nodes; }ArrayStack;

   배열로 짠 스택답게 이미 Capacity가 정해져 있다.

 

 

void AS_CreateStack(ArrayStack** Stack, int Capacity){ (*Stack) = (ArrayStack*)malloc(sizeof(ArrayStack)); (*Stack)->Nodes = (Node*)malloc(sizeof(Node)*Capacity); //배열과 같이 Capcity가 정해짐 (*Stack)->Capacity = Capacity; (*Stack)->Top = 0; //초기화 }

 

 

void AS_DestroyStack(ArrayStack* Stack){ free(Stack->Nodes); free(Stack); }

주의 할 점은 먼저 스택에 잇는 노드의 메모리를 해제한 다음

스택의 메모리를 해제해야 한다는 점이다.

 

void AS_Push(ArrayStack* Stack, ElementType Data){ int Position = Stack->Top; Stack->Nodes[Position].Data = Data; Stack->Top++; }

 

ElementType AS_Pop(ArrayStack* Stack){ int Position = --(Stack->Top); return Stack->Nodes[Position].Data; }

 약간 부족한 감이 있다. 스텍이 비어있는지 확인(Top==0)을 안하고 있다.