자료구조 - 링크드리스트로 구현한 스택(Linked List Stack)

배열로 구현한 스택과(Array Stack)의 코드 부분에서 이 부분만 주의해서 고치면 된다.

1. 인덱스 대신 포인터를 이용해 값을 참조한다. -> Push,Pop함수 부분

2. 링크드 리스트로 구현했으므로 크기는 정해져 있지 않다. -> 노드 생성 함수 부분 

 

 

typedef struct tagNode{ char* Data; struct tagNode* NextNode; }Node;

제가 보고 있는 책이 이제 데이터가 정수가 아닌 문자열로 돼 있네요.

 

 

typedef struct tagLinkedListStack{ Node* List; Node* Top; }LinkedListStack

 

 

void LLS_CreatStack(LinkedListStack** Stack){ (*Stack) = (LinkedListStack*)malloc(sizeof(LinkedListStack); (*Stack)->List = NULL; (*Stack)->Top = NULL; }

  

 

void LLS_DestroyStack(LinkedListStack* Stack){ while( !LLS_ISEmpty(Stack) ){ Node* Popped = LLS_Pop(Stack); LLS_DestoryNode(Popped); } free(Stack); }

  

 

Node* LLS_CreatNode(Char* NewData){ Node* NewNode = (Node*)malloc(sizeof(Node)); NewNode->Data = (char*)malloc(strlen(NewData)+1); strcpy(NewNode->Data,NewData); NewNode->NextNode = NULL; return NewNode; }

 여기서 strlen()함수는 문자열의 갯수를 세는 함수인데

문자열의 마지막 \0은 개수에서 제외 하기 때문에 실제 메모리 동적 할당할 때 공간을 +1해야 한다.

 

 

void* LLS_DestroyNode(Node* Remove){ free(Remove->Data); free(Remove); }

 

 

void* LLS_Push(LinkedListSatack* Stack, Node* NewNode){ if(Stack->List = NULL) Stack->List = NewNode; else{ Node* Temp = Stack->Top; Temp->NextNode=NewNode; } Stack->Top = NewNode; }

 

 

Node* LLS_Pop(LinkedListSatack* Stack){    Node* TopNode = Stack->Top;    if(Stack->List == Stack->Top){       Stack->List = NULL;       Stack->Top = NULL;    }    else{       Node* Current = Stack->List;       while(Current != NULL && Current->NextNode != Stack->Top)          Current = Current->NextNode;            Stack->Top = Current;      Current->NextNode = NULL;    }    return TopNode; }

 

 

int LLS_GetSize(LinkedListStack* Stack){ unsigned int Count = 0; Node* Current = Stack->List; while(Current != NULL){ Current = Current->NextNode; Count++; } return Count; }