뇌를 자극하는 알고리즘 2. 스택 - Linked List Stack

구현소스

LinkedListStack.h

#ifndef LINKEDLISTSTACK_H
#define LINKEDLISTSTACK_H

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

// 데이터를 가지는 Node 구조체
typedef struct tagNode
{
	char* Data; // ArrayStack과 다르게 데이터를 문자열로 지정했다.
	// Node 생성시 Node 구조체 타입의 메모리 생성뿐만 아니라 문자열의 메모리도 생성 및 파괴 해줘야 한다.
	struct tagNode* NextNode;
	// 다음 노드를 가리키는 NextNode

} Node;

typedef struct tagLinkedListStack
{
	Node* List; // 최하위 노드를 가리키는 List
	Node* Top;  // 최상위 노드를 가리키는 Top
} LinkedListStack;

void LLS_CreateStack(LinkedListStack** Stack); // stack 생성
void LLS_DestroyStack(LinkedListStack* Stack); // stack 해제 - 모든 node들의 pop연산 수행후 메모리 해제

Node* LLS_CreateNode(char* Data); // node 생성
void LLS_DestroyNode(Node* _Node); // node 파괴

void LLS_Push(LinkedListStack* Stack, Node* NewNode); // stack의 push 연산 수행
Node* LLS_Pop(LinkedListStack* Stack);				  // stack의 pop 연산 수행
													// - 연산 수행 후 NextNode 수정 및 pop되는 node의 메모리 해제 기능까지 구현

Node* LLS_Top(LinkedListStack* Stack); // stack의 Top node를 구하는 함수
int LLS_GetSize(LinkedListStack* Stack); // stack의 node 개수를 구하는 함수
int LLS_IsEmpty(LinkedListStack* Stack); // stack이 비어있는지 여부를 구하는 함수.
#endif

---------------------------------------------------------------------------------------

LinkedListStack.cpp

#include "LinkedListStack.h"

// stack 생성
void LLS_CreateStack(LinkedListStack** Stack){

	printf("*** Stack is created ***\n");
	(*Stack) = (LinkedListStack*) malloc(sizeof(LinkedListStack));
	// Stack의 메모리 할당

	(*Stack)->Top = (*Stack)->List = NULL;
	// Top, List를 NULL로 초기화
}
// stack 해제 - 모든 node들의 pop연산 수행후 메모리 해제
void LLS_DestroyStack(LinkedListStack* Stack){
	
	while( !LLS_IsEmpty(Stack) ){ // Stack의 Node가 Empty 상태가 될때까지 loop문 수행
		Node* Popped = LLS_Pop(Stack);
		LLS_DestroyNode(Popped);
	}
	// 모든 node의 pop 연산을 마친 후 stack의 메모리 해제
	printf("*** Stack is deleted ***\n");
	free(Stack);
}

// node 생성
// - 생성과 동시에 push연산을 수행하려면
//  LLS_Push(Stack, LLS_CreateNode("문자열")) 이런식으로 쓰면 된다.
Node* LLS_CreateNode(char* Data){
	Node* NewNode = (Node*) malloc(sizeof(Node)); // 새로운 노드의 메모리 할당

	NewNode->Data = (char*) malloc( strlen(Data) + 1); // 문자열의 경우 \0까지 들어가야되므로...+1

	strcpy(NewNode->Data , Data); // 문자열 카피 수행

	NewNode->NextNode = NULL; // NextNode는 NULL로 초기화

	return NewNode; // 생성된 노드의 주소 반환
}
// node 파괴
void LLS_DestroyNode(Node* _Node){
	printf("*** Node is deleted - Data : %s\n", _Node->Data);
	free(_Node->Data); // 문자열부터 해제하고...
	free(_Node);	   // 그다음 node 해제.
}

// stack의 push 연산 수행
void LLS_Push(LinkedListStack* Stack, Node* NewNode){
	if( LLS_IsEmpty(Stack) ){ // 비어있는 stack의 경우라면
		Stack->List = NewNode;		
	}
	else{ // 비어있지않는 stack의 경우라면
		// 최상위 노드를 찾아 NewNode를 연결
		Node* Current_Top = Stack->Top;
		Current_Top->NextNode = NewNode;
	}

	printf("  - Pushed Node's Data : %s\n",NewNode->Data);
	NewNode->NextNode = NULL;
	Stack->Top = NewNode;
}

// stack의 pop 연산 수행
// - 연산 수행 후 NextNode 와 Top 이 가리키는 링크 수정 기능 제공.
// - Pop되는 Node의 주소를 리턴해야되니 pop되는 node의 메모리 해제는 
//  LLS_DestroyNode(LLS_Pop(Stack)) 이런 식으로 쓰면 될듯.
Node* LLS_Pop(LinkedListStack* Stack){
	Node* TopNode = Stack->Top;
	// stack이 비어있을 경우 pop연산을 수행할때 예외처리
	if(LLS_IsEmpty(Stack)){
		printf("* Error - Stack is empty !! *\n");
		return NULL;
	}
	// node가 한개 남았을시 pop연산을 수행할때
	else if( Stack->List == Stack->Top){
		Stack->List = NULL;
		Stack->Top = NULL;
	}
	else{ // 그외의 경우 - 새로운 Top노드 설정
		Node* CurrentTop = Stack->List;

		while( CurrentTop != NULL && CurrentTop->NextNode != Stack->Top){
			// 새로운 Top을 구하기
			CurrentTop = CurrentTop->NextNode;
		}
		// Loop문 수행후 원래의 Top 바로 아래에 있는 Node가 CurrentTop이 된다
		Stack->Top = CurrentTop;
		CurrentTop->NextNode = NULL; // 링크 해제		
	}
	printf("  - Poped Node's Data : %s\n",TopNode->Data);
	return TopNode;
}

// stack의 Top node를 구하는 함수
Node* LLS_Top(LinkedListStack* Stack){
	printf("  - Top node's Data : %s \n",Stack->Top->Data);
	return Stack->Top;
}
// stack의 node 개수를 구하는 함수
int LLS_GetSize(LinkedListStack* Stack){
	int Count=0;
	Node* Current = Stack->List;

	while( Current != NULL){
		Current = Current->NextNode;
		Count++;
	}

	return Count;
}

// stack이 비어있는지 여부를 구하는 함수.
int LLS_IsEmpty(LinkedListStack* Stack){
	// List는 항상 최하위의 Node를 가리키므로 List가 NULL일시 stack이 비어있는 상태가 된다.

	return ( (Stack->List) == NULL );
}

--------------------------------------------------------------------------------

main.cpp

 
#include "LinkedListStack.h"

int main(){

	LinkedListStack* Stack = NULL;
	int i, Count;

	// 스택의 생성
	LLS_CreateStack(&Stack);

	// 노드의 push연산
	printf(" *** Push Function Check *** \n");
	LLS_Push(Stack, LLS_CreateNode("Kim"));
	LLS_Push(Stack, LLS_CreateNode("LEE"));
	LLS_Push(Stack, LLS_CreateNode("PARK"));

	// 최상위 node
	printf(" *** Top Node Check *** \n");
	LLS_Top(Stack);

	printf(" *** The Number of Nodes = %d\n" , Count = LLS_GetSize(Stack));


	// 노드의 pop 연산
	printf(" *** Pop Function Check *** \n");

	for(i=0;i<Count;i++)
		LLS_DestroyNode(LLS_Pop(Stack)); // Pop연산 수행후 바로 Node삭제
	printf(" *** Exceptional Process Check ***\n");
	LLS_Pop(Stack); // 예외처리 확인

	printf(" *** The Number of Nodes = %d\n" , Count = LLS_GetSize(Stack));

	// 노드의 push연산
	printf(" *** Push Function Check *** \n");
	LLS_Push(Stack, LLS_CreateNode("김"));
	LLS_Push(Stack, LLS_CreateNode("이"));
	LLS_Push(Stack, LLS_CreateNode("박"));

	printf(" *** The Number of Nodes = %d\n" , Count = LLS_GetSize(Stack));

	printf(" *** DestroyStack Function Check *** \n");
	LLS_DestroyStack(Stack);



	return 0;
}

---------------------------------------------------------------------------

실행 결과