[자료구조] 스택 - 03 . 링크드 리스트로 구현하는 스택

[스택과 스택의 노드 표현하기]

[노드]

링크드 리스트로 구현하는 스택의 노드는 자신의 위에 위치한 노드에 대한 포인터가 필요하다 .

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

=>데이터 필드가 char*이기에 문자열이 저장되어 있는 주소만을 담을 수 있어야 한다.

또한 해당 문자열은 자동 메모리가 아닌 자유 저장소에 저장 되어야 한다.

[스택]

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

=>List 포인터는 스택이 기반하고 있는 링크드 리스트에 접근

=>Top 포인터는 최상위 노드에 대한 정보를 유지

 

[스택의 기본 연산 구현하기]

[스택의 생성]

void LLS_CreateStack(LinkedListStack** Stack)
{
	//스택을 자유저장소에 생성
	(*Stack)=(LinkedListStack)malloc(sizeof(LinkedListStack));
    (*Stack)->List=NULL;
    (*Stack)->Top=NULL;
}

[스택 노드의 생성]

=>참고 : strcpy , strcpy의 이유 , strlen 

Node* LLS_CreateNode(Char* NewData)
{
    //자유 저장소에 노드를 할당
    Node* NewNode=(Node*)malloc(sizeof(Node));
    
    //입력받은 문자열의 크기만큼을 자유 저장소에 할당
    NewNode->Data=(char*)malloc(strlen(NewData)+1);
    
    //자유 저장소에 문자열 복사
    strcpy(NewNode->Data,NewData);
    
    //다음 노드에 대한 포인터는 NULL로 초기화
    NewNode->NextNode=NULL;
    
    //노드의 주소를 반환한다.
    return NewNode;
}

[스택의 소멸]

void LLS_DestroyStack(LinkedListStack*Stack)
{
    while(!LLS_IsEmpty(Stack))	//Stack이 빌 때까지 반복
    {
    	Node*Popped=LLS_Pop(Stack);	//노드를 스택에서 제거한 다음
        LLS_DestroyNode(Popped);	//자유 저장소에서 노드를 해제한다
    }
    free(Stack);	//자유 저장소에서 스택을 해제한다
}

[스택 노드의 소멸]

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

[삽입 (Push) 연산]

void LLS_Push(LinkedListStack*Stack,Node*NewNode)
{
	if(Stack->List==NULL)
    {
    	Stack->List=NewNode;
    }
    else
    {
    	//최상위 노드를 찾아 NewNode를 연결(쌓는다).
    	Node* OldTop=Stack->List;
        while(OldTop->NextNode!=NULL)
        {
        	OldTop=OldTop->NextNode;
        }
        OldTop->NextNode=MEwMode;
    }
    //스택의 Top필드에 새 노드의 주소를 등록한다
    Stack->Top=NewNode;
}

[제거 (Pop) 연산]

=>링크드 리스트로 구현한 스택은 4단계로 수행된다.

• 현재 최상위 노드의 주소를 다른 포인터에 복사해 둔다.
• 새로운 최상위 노드, 현재 최상위 노드의 바로 이전(아래)노드를 찾는다
• LinkedListStack 구주체의 Top필드에 새로운 최상위 노드의 주소를 등록한다
• 옛 최상위 노드의 주소를 반환한다

Node* LLS_Pop(LinkedListStack* Stack)
{
    //현재 최상위 노드의 주소를 다른 포인터에 복사한다.
    Node* TopNode=Stack->Top;
    
    //대상이 처음 노드라면
    if(Stack->List==TopNode)
    {
    	Stack->List=NULL;
        Stack->Top=NULL;
    }
    else
    {
    	Node* CurrentTop=Stack->List;
        //Top전 노드를 찾는다
        while(CurrentTop!=NULL&&CurrentTop->NextNode!=TopNode)
        {
        	CurrentTop=CurrentTop->NextNode;
        }
        Stack->Top=CurrentTop;
        CurrentTop->NextNode=NULL;
    }
    return TopNode;
}

[링크드 리스트로 구현하는 스택 예제 프로그램]

[LinkedListStack.h]

#ifndef LINKEDLISTSTACK_H
#define LINKEDLISTSTACK_H
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
//노드
typedef int ElementType;

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

//스택
typedef struct tagLinkedListStack
{
	Node* List;		//리스트
	Node* Top;		//탑노드
}LinkedListStack;

#include "LinkedListStack.h"

//스택 생성
void LLS_CreateStack(LinkedListStack** Stack);
//노드 생성
Node* LLS_CreateNode(const char*Data);
//스택 소멸
void LLS_DestroyStack(LinkedListStack* Stack);
//노드 소멸
void LLS_DestroyNode(Node* Destroy);
//Push
void LLS_Push(LinkedListStack* Stack, Node* NewNode);
//Pop
Node* LLS_Pop(LinkedListStack* Stack);
//스택이 비었는지 체크
bool LLS_IsEmpty(LinkedListStack* Stack);
//최상위 노드 반환
Node* LLS_Top(LinkedListStack* Stack);
//개수 반환
int LLS_GetSize(LinkedListStack* Stack);

#endif // !LINKEDLISTSTACK_H

[LinkedListStack.cpp]

#include "LinkedListStack.h"

//스택 생성
void LLS_CreateStack(LinkedListStack** Stack)
{
	//스택을 자유 저장소에 저장
	(*Stack) = (LinkedListStack*)malloc(sizeof(LinkedListStack));
	(*Stack)->List = NULL;
	(*Stack)->Top = NULL;
}

//노드 생성
Node* LLS_CreateNode(const char*   NewData)
{
	Node* NewNode = (Node*)malloc(sizeof(Node));
	NewNode->Data = (char*)malloc(strlen(NewData) + 1);

	strcpy_s(NewNode->Data,strlen(NewData)+1, NewData);

	NewNode->NextNode = NULL;
	return NewNode;
}

//스택 소멸
void LLS_DestroyStack(LinkedListStack* Stack)
{
	while (!LLS_IsEmpty)
	{
		Node* Popped = LLS_Pop(Stack);
		LLS_DestroyNode(Popped);
	}
	free(Stack);
}
//노드 소멸
void LLS_DestroyNode(Node* Destroy)
{
	free(Destroy->Data);
	free(Destroy);
}
//Push
void LLS_Push(LinkedListStack* Stack,Node* NewNode)
{
	if (Stack->List == NULL)
	{
		Stack->List = NewNode;
	}
	else
	{
		Node* OldTop = Stack->List;
		while (OldTop->NextNode != NULL)
		{
			OldTop = OldTop->NextNode;
		}
		OldTop->NextNode = NewNode;
	}
	Stack->Top = NewNode;
}
//Pop
Node* LLS_Pop(LinkedListStack* Stack)
{
	Node* TopNode = Stack->Top;

	if (Stack->List == TopNode)
	{
		Stack->List = NULL;
		Stack->Top = NULL;
	}
	else
	{

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

//스택이 비었는지 체크
bool LLS_IsEmpty(LinkedListStack* Stack)
{
	return (Stack->List == NULL);
}
//최상위 노드 반환
Node* LLS_Top(LinkedListStack* Stack)
{
	return Stack->Top;
}
//개수 반환
int LLS_GetSize(LinkedListStack* Stack)
{
	Node* CurrentNode = Stack->List;
	int count = 0;
	while (CurrentNode != NULL)
	{
		CurrentNode = CurrentNode->NextNode;
		count++;
	}
	return count;
}

[LinkedListStackTest.cpp]

#include "LinkedListStack.h"

int main(void)
{
	int i = 0;
	int count = 0;
	Node* Popped;

	LinkedListStack* Stack;

	LLS_CreateStack(&Stack);

	LLS_Push(Stack, LLS_CreateNode("abc"));
	LLS_Push(Stack, LLS_CreateNode("def"));
	LLS_Push(Stack, LLS_CreateNode("ghi"));
	LLS_Push(Stack, LLS_CreateNode("jkl"));

	count = LLS_GetSize(Stack);
	printf("Size : %d , Top : %s\n\n", count, LLS_Top(Stack)->Data);

	for (i = 0; i < count; i++)
	{
		if (LLS_IsEmpty(Stack))
			return 0;

		Popped = LLS_Pop(Stack);
		printf("Popped : %s\n", Popped->Data);
		LLS_DestroyNode(Popped);

		if (LLS_IsEmpty(Stack))
		{
			printf("Stack is Empty\n");
		}
		else
		{
			printf("Current Top : %s\n", LLS_Top(Stack)->Data);
		}
	}
	LLS_DestroyStack(Stack);
	return 0;
}

 

 

출처

• [C언어/C++] strcpy, strncpy 함수(문자열 복사)에 대해서 (tistory.com)
• 문자열 배열의 초기화와 strcpy의 존재이유 : 네이버 블로그 (naver.com)
• [C언어/C++] strlen 함수(문자열 길이)에 대해서 (tistory.com)