Stack(연결리스트)

1. Stack을 연결리스트로 구현

Stack을 배열로 구현했을 때의 장점과 연결리스트로 구현했을 때의 장점은 배열과 연결리스트의 장점과 매우 유사합니다. 따라서 진짜 데이터에 따라 자유롭게 구현하시면 됩니다.

헤더파일

먼저 헤더파일부터 바로 보겠습니다.

LinkedListStack.h

#ifndef LINKEDLIST_STACK_H
#define LINKEDLIST_STACK_H
#define _CRT_SECURE_NO_WARNINGS

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

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

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

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

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

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

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

#endif

연결리스트의 종류는 단방향, 양방향, 환형이 있는데, 왜 Stack을 구현할 때 양방향을 사용했는지 궁금할 수 있습니다. 그럼 만약 단방향을 이용했다고 생각해보겠습니다.

단방향을 사용했을 때, 효율적이지 못한 이유는 Pop함수일 때 입니다. Pop을 하면 Top노드가 삭제가 되는데, Top노드를 밑에 노드로 옮기기 위해서는 Head부터 탐색을 다시 해야 합니다.

환형은 양방향에서 Head와 Tail을 연결한 것인데, Stack에서는 Top과 Tail을 굳이 연결할 필요가 없습니다. 따라서 양방향을 이용한 Stack이 가장 효율적이라고 생각합니다.

void LLS_CreateStack(LinkedListStack** Stack); -> Stack 생성함수
void LLS_DestroyStack(LinkedListStack* Stack); -> Stack 삭제함수
Node* LLS_CreateNode(char* Data); -> Node 생성함수
void LLS_DestroyNode(Node* _Node); ->Node 삭제함수
void LLS_Push(LinkedListStack* Stack, Node* NewNode); ->Push 함수
Node* LLS_Pop(LinkedListStack* Stack); -> Pop 함수
Node* LLS_Top(LinkedListStack* Stack); -> Top 함수
int LLS_GetSize(LinkedListStack* Stack); -> Node개수를 반환하는 함수
int LLS_IsEmpty(LinkedListStack* Stack); -> Stack이 비어있는지 알려주는 함수

Stack 배열과 다른 점은 IsFull함수가 빠졌다는 것입니다.

소스파일

LinkedListStack.c

#include "LinkedListStack.h"

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

void LLS_DestroyStack(LinkedListStack* Stack) {
	while (!LLS_IsEmpty(Stack)) {
		Node* Popped = LLS_Pop(Stack);
		LLS_DestroyNode(Popped);
	}

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

Node* LLS_CreateNode(char* NewData) {
	Node* NewNode = (Node*)malloc(sizeof(Node));
	NewNode->Data = (char*)malloc(strlen(NewData) + 1);

	strcpy(NewNode->Data, NewData); //데이터를 저장한다.

	NewNode->NextNode = NULL; //다음 노드에 대한 포인터는 NULL로 초기화한다.
	NewNode->PrevNode = NULL;

	return NewNode; //노드의 주소를 반환한다.
}

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

void LLS_Push(LinkedListStack* Stack, Node* NewNode) {
	if (Stack->List == NULL) {
		Stack->List = NewNode;
	}
	else {
		//스택의 Top에 신규 노드를 연결한다.
		Stack->Top->NextNode = NewNode;
		Stack->Top->NextNode->PrevNode = Stack->Top;
	}

	//스택의 Top 필드에 새 노드의 주소를 등록한다.
	Stack->Top = NewNode;

	Stack->Count++;
}

Node* LLS_Pop(LinkedListStack* Stack) {
	//LLS_Pop() 함수가 반환할 최상위 노드 저장
	Node* TopNode = Stack->Top;

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

	Stack->Count--;
	return TopNode;
}

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

int LLS_GetSize(LinkedListStack* Stack) {

	return Stack->Count;
}

int LLS_IsEmpty(LinkedListStack* Stack) {
	return (Stack->List == NULL);
}

Push함수와 Pop함수를 제외하면, 나머지 함수들은 해석에 어려움이 없습니다. 그래서 Push함수와 Pop함수만 보겠습니다.

Push 함수

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

	Stack->Top = NewNode;

	Stack->Count++;
}

첫번째 if문을 보면 Stack->List == NULL이라고 되어있는데 이 뜻은 Stack에 노드가 없는지를 물어보는 조건문입니다. 즉, Stack->List를 Head라고 생각하시면 됩니다. 따라서 Stack에 Head에 NewNode를 추가하는 모습입니다. Stack에 Node가 1개 이상일 경우 else구문으로 넘어가게 되는데, Top->NextNode를 NewNode로 바꾸고 NewNode의 PrevNode를 Top으로 바꾸는 모습입니다. 그리고 Top을 NewNode로 갱신합니다.

Pop 함수

Node* LLS_Pop(LinkedListStack* Stack) {
	Node* TopNode = Stack->Top;

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

	Stack->Count--;
	return TopNode;
}

Top Node를 새로운 변수에 저장한 후 삭제합니다. 그리고 저장된 값을 반환하는 구조입니다. 저장한 후에는 Stack자체에서 제외시키기 위해서 연결된 주소값을 모두 바꿔줍니다.
제외시키는 Node도 바꿔줘야 그 Node를 통해서 Stack의 값을 바꾸지 못합니다.

실행예시

그럼 적당한 main함수를 작성하고 실행시켜 보겠습니다.
LinkedListStackMain.c

#include "LinkedListStack.h"

int main() {
	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("efg"));
	LLS_Push(Stack, LLS_CreateNode("hij"));

	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)) {
			break;
		}

		Popped = LLS_Pop(Stack);

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

		LLS_DestroyNode(Popped);

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

	LLS_DestroyStack(Stack);

	return 0;
}

결과

Size: 4, Top: hij

Popped: hij, Current Top: efg
Size: 3
Popped: efg, Current Top: def
Size: 2
Popped: def, Current Top: abc
Size: 1
Popped: abc, Stack Is Empty.
Size: 0