링크드 리스트로 구현한 스택 (C언어)

1. 읽기 전 알아두면 유용한 것

1. 링크드 리스트

링크드 리스트 with C

---

2. 스택의 개념

Stack은 쌓다의 의미를 지니고 있다. 말 그대로 데이터를 쌓아서 정리하는 자료구조이다. 스택의 꼭대기에서만 연산이 이루어지는 것이다. 이외 자료구조의 중앙의 데이터 입/출력은 허용되지 않는다. 가장 나중에 들어온 데이터가 가장 먼저 나가는 자료구조(LIFO: Last In-First Out)이다. 필자는 편하게 "라이포"라고 외웠다. 가장 중요한 개념인 '삽입'과 '삭제'는 'Pop'과 'Push'라고 불리며 실제 함수 구현에도 이 같은 이름이 함수명으로 사용된다. 그림을 통해 조금 더 자세히 알아보자.

스택의 삽입과 삭제

이처럼 최 상단에서 Pop과 Push가 일어나게 되는 LIFO구조인 것을 알 수 있다.

---

3. 기본 연산

1. 노드와 자료구조 생성 및 삭제
2. 삽입 연산
3. 제거 연산

---

4. 구현

링크드 리스트로 구현한 스택 상상도

우선 링크드 리스트라는 구조체와 각 요소가 될 노드 구조체를 선언할 것이다. 이 때 우리가 구상했던 스택의 개념에 맞추기 위해 Top가 스택의 헤드를 그리고 헤드에서 꼬리까지 단일 포인터로 연결하려 한다.

0. 선언한 헤더 파일 (LinkedListStack.h)

#ifndef LINKEDLIST_STACH_H
#define LINKEDLIST_STACH_H
#define _CRT_SECURE_NO_WARNINGS

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

typedef struct tagNode
{
	char* Data;
	struct tagNode* NextNode; // 다음 노드를 가리키기 위한
}Node;

typedef struct tagLinkedListStack
{
	int Count; // 삽입/삭제 시 개수를 갱신
	Node* Top; // 스택을 가리키는 포인터 빈 스택은 NULL이다
}LinkedListStack;

void LLS_CreateStack(LinkedListStack** Stack);
void LLS_DestroyStack(LinkedListStack* Stack);

Node* LLS_CreateNode(char* NewData);
void LLS_DestroyNode(Node* _Node);

void LLS_Push(LinkedListStack* Stack, Node* newNode);
Node* LLS_Pop(LinkedListStack* Stack);

Node* LLS_Peek(LinkedListStack* Stack);
int LLS_GetSize(LinkedListStack* Stack);
int LLS_IsEmpty(LinkedListStack* Stack);

#endif // !LINKEDLIST_STACH_H

 

1. Stack과 노드 생성 및 소멸 연산

1. 생성

void LLS_CreateStack(LinkedListStack** Stack)
{
	(*Stack) = (LinkedListStack*)malloc(sizeof(LinkedListStack));
	(*Stack)->Count = 0;
	(*Stack)->Top = NULL;
}

Node* LLS_CreateNode(char* NewData)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->Data = (char*)malloc(strlen(NewData) + 1); // 문자열 끝 /0를 반영하기 위한 +1

	strcpy(newNode->Data, NewData);
	newNode->NextNode = NULL;

	return newNode;
}

malloc으로 자유 저장소에 공간을 확보한 후 데이터를 srcpy로 삽입한다. 이 때 안전한 구동을 위해 포인터는 NULL로 초기화한다.

 

2. 소멸

void LLS_DestroyStack(LinkedListStack* Stack)
{
	while (!LLS_IsEmpty(Stack)) // 스택의 내용물 비우기
	{
		Node* popped = LLS_Pop(Stack);
		LLS_DestroyNode(popped);
	}

	free(Stack); // 자유 저장소에서 해제
}

void LLS_DestroyNode(Node* _Node)
{ // 데이터 free 후 노드를 free해야한다.
	free(_Node->Data);
	free(_Node);
}

Stack 삭제 시 남아 있는 노드를 모두 삭제한 후 Stack을 삭제한다.

노드 사제 시 데이터를 삭제한 후 노드를 삭제한다.

 

2. Push 노드 삽입

void LLS_Push(LinkedListStack* Stack, Node* newNode)
{
	newNode->NextNode = Stack->Top;
	Stack->Top = newNode;
	Stack->Count++;
}

첫 요소 삽입 시 첫 요소는 Top이 된다. 이 때 자연스럽게 첫 노드는 NULL을 가리키게 된다. 그게 아닌 요소가 존재할 땐 새로운 Top으로 갱신하게 된다.

 

3. Pop 노드 삭제

Node* LLS_Pop(LinkedListStack* Stack)
{
	// Stack의 Top을 교체한 후 반환
	if (LLS_IsEmpty(Stack)) return NULL; // Stack 비었다면 return

	Node* popped = Stack->Top;
	Stack->Top = Stack->Top->NextNode; // 마지막 요소 뽑을 시 자동으로 NULL을 가리킴
	Stack->Count--;

	return popped;
}

Pop 시 외부에서 데이터를 사용할 수 있어야한다. 따라서 삭제한 노드를 반환해야 하며, 삭제할 노드를 캐싱한 후 Top을 바로 아래에 있는 요소로 갱신하게 된다. 이 때 노드가 한 개 남았다면 자연스럽게 Top은 NULL을 가리키게 된다.

 

4. 이 밖에 구현한 것

Node* LLS_Peek(LinkedListStack* Stack)
{
	return Stack->Top;
}

int LLS_GetSize(LinkedListStack* Stack)
{
	return Stack->Count;
}

int LLS_IsEmpty(LinkedListStack* Stack)
{
	return Stack->Count == 0;
}

1. Peek는 "엿보다"라는 뜻이 있듯이 Peek 함수는 최상단 노드를 반환하게 된다.

2. GetSize는 Stack의 Count를 반환하여 현재 스택의 사이즈를 알 수 있다.

3. IsEmpty는 Count가 0이 됨을 기준으로 빈 상태를 구분하였다.

 

5. 자료구조 사용 및 결과 출력

int main(void) 
{
	Node* Popped;
	LinkedListStack* Stack;
	int Count = 0;

	LLS_CreateStack(&Stack);
	// abc <- def <- efg <- hij(Top) 로 스택에 저장 (<-는 포인터 연결 방향)
	LLS_Push(Stack, LLS_CreateNode("abc"));
	LLS_Push(Stack, LLS_CreateNode("def"));
	LLS_Push(Stack, LLS_CreateNode("efg"));
	LLS_Push(Stack, LLS_CreateNode("hij"));

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

	// 모든 요소를 Pop하여 결과 확인
    	// 출력: hij, efg, def, abc 순으로
	for (int i = 0; i < Count; i++)
	{
		if (LLS_IsEmpty(Stack))
			break;

		Popped = LLS_Pop(Stack);

		printf("Popped: %s, ", Popped->Data);

		LLS_DestroyNode(Popped);

		if (!LLS_IsEmpty(Stack))
		{
			printf("Current Top: %s\n", LLS_Peek(Stack)->Data);
		}
		else
		{
			printf("Stack Is Empty.\n");
		}
	}

	LLS_DestroyStack(Stack);

	return 0;

}

 

출력 결과 LIFO순으로 출력 된다.

 

C언어는 객체지향 프로그래밍이 아니기에 캡슐화는 불가능하다. 허나 GetSize를 통한 접근으로 원본 데이터인 Count의 변형을 막을 수 있다.

 

이번 학기에 자료구조를 수강하게 되었다. 따라서 해당 강의 및 "이것이 자료구조+알고리즘이다"라는 책을 복습하기 위해 작성하였다.

책 구매 링크