스택(Stack), c언어 구현 코드, 연결 리스트 기반 스택, 자료구조

들어가기 앞서

 

 

이전 게시물은, 스택을 배열 기반으로 구성해 봤습니다.

이전 배열 기반으로 했을 때 단점은 capacity라는 건데요.

즉 용량을 넘어서는 안된다는 점!

 

따라서 용량에 구애받지 않는 스택을 구성하기 위해서는 연결 리스트를 기반하는 방법이 있습니다.

 

스택 개념을 모르겠다면 이전 게시물을 보고와주세요.

https://8ehrmin.tistory.com/8

스택(Stack), c언어 구현 코드, 배열 기반 스택, 자료구조

 

아 연결 리스트 모르겠다면 이전 게시물 보고와주세요.

https://8ehrmin.tistory.com/5

연결 리스트(Linked List), C언어 구현, 코드(너 ㅋ 이해하고 싶어?)

 

---

 

연결 리스트 기반 스택 노드

 

스택에서 사용하는 노드와 달리 크기에 대한 지정이 필요 없기 습니다.

그렇다면 뭐가 필요할까요?

 

바로 노드는 자신 위에 어떤 노드가 있는지 알아야 합니다.

추가적으로 가장 상위에있는 노드에 대한 필드도 필요할 것 입니다.

왜냐하면? 굳이 없어도 연결 리스트를 가리키는 포인터를 이용하여 구할 수 있지만 100번째가 Top이자 Tail이라면 100까지 징검다리 건너 알아야하기 때문이죠.

 

따라서 구조체는 다음과 같습니다.

---

typedef struct tagNode
{
	char* data;
	struct tagNode* nextNode;

}Node;

typedef struct tagLikedListStack
{
	Node* list;
	Node* top;

} likedListStack;

---

즉 보면, likedListStack는 스택 자체가 될 것이며, top필드는 top에 있는 노드를 가리키는 포인터입니다.

구성을 하면 위와 같겠죠?

tail 즉 top인 점만 파악해도 좋습니다.

 

---

스택 노드의 생성과 소멸

 

스택 노드에 동적으로 메모리를 할당하며 생성하기 위한 연산이 필요할 것 입니다.

또한 동적으로 메모리를 할당했다면? 

개발자는 책임지고 이를 해제해야 하죠.

그에 대한 설명입니다.

(추가적인 설명이 필요하다면 이전 게시물을 참고하고 와주세여)

---

Node* createNodeLIS(char* data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = (char*)malloc(sizeof(data) + 1);

	strcpy(newNode->data, data);

	newNode->nextNode = NULL;
	
	return newNode;
}

void destroyNodeLIS(Node* node)
{
	free(node->data);
	free(node);
}

 

이전에 **를 사용하는 이유와 더불어 함수가 종료되면서 저장되지 않은 데이터로 인해 발생하는 문제들을 설명하였습니다.

여기서요

 

따라서 노드의 문자열 필드에 동적 메모리를 할당하여 해당 문제를 바로잡아 줍니다.

이하 모두 이전 게시물들에서 다루었던 내용과 동일합니다.

 

---

 

 

배열 리스트도 노드와 마찬가지이며 생성 또한, 동일한 내용입니다.

---

void createStackLIS(likedListStack** stack)
{
	(*stack) = (likedListStack*)malloc(sizeof(likedListStack));
	(*stack)->list = NULL;
	(*stack)->top = NULL;
}

int isEmptyLIS(likedListStack* stack)
{
	return stack->list == NULL;
}

Node* popNodeLIS(likedListStack* stack)
{
	//스택 top에 위치한 노드를 POP하는 과정
	//해당 과정에서 Top의 포인터와 관련된 정보를 수정
	//추후 작성 및 설명

	return popNode;
}

void destroyStack(likedListStack* stack)
{
	while (!isEmptyLIS(stack))
	{
		Node* popNode = popNodeLIS(stack);
		destroyNodeLIS(popNode);
	}
	free(stack);
}

---

생성은 동일하니, 소멸 연산을 확인하겠습니다.

 

먼저 stack 포인터가 담고있는 데이터와 노드가 담고 있는 데이터가 각각 다른 것을 알고 계셔야 합니다.

당연하겠죠?

 

필드를 다시 보면

stack : ListPointer, TopPointer

node : charPointer, NextPointer

 

각각 해제해야하는 것이 있으나 node에 경우 char 포인터에 동적으로 메모리를 할당하였었습니다.

따라서 추가적인 코드가 필요하기 때문에 소멸 코드가 길어질 수 밖에 없습니다.

 

또한 동시에 소멸은 LIFO, FILO 즉 스택을 따르기 때문에 tail부터 POP이 되며 소멸되는 코드를 볼 수 있습니다.

void destroyStack(likedListStack* stack)
{
	while (!isEmptyLIS(stack))
	{
		Node* popNode = popNodeLIS(stack);
		destroyNodeLIS(popNode);
	}
	free(stack);
}

---

스택 노드의 삽입 연산

 

노드를 삽입하는 연산을 PUSH이라고 하였습니다.

이전에 배열 기반 스택은, 단지 PUSH 을 한 후 TOP에 있는 노드만을 가리키면 되었습니다.

 

리스트 기반 스택도 마찬가지지만 PUSH이전 TOP의 nextNode를 현 노드로 가리켜야 합니다.

왜냐하면 리스트 기반 스택은, 자신의 위에있는 노드를 알아야 하니까요.

그 후 TOP에 있는 노드가 현 NODE를 가리키면 됩니다.

 

---

void pushNodeLIS(likedListStack* stack, Node* node)
{
	if (stack->list == NULL)
	{
		stack->list = node;
	}
	else
	{
		stack->top->nextNode = node;
	}
	stack->top = node;
}

---

스택 노드의 삭제 연산

 

스택 노드의 삭제 및 제거 연산은 POP이라고 하였습니다.

POP된 노드는 데이터를 반환해야 한다는 특징까지 있었죠.

 

이전 과는 다르게 리스트 기반 스택은 네단계로 이루어집니다.

 

1. 현재 최상위 노드의 주소를 다른 포인터에 복사한다.

2. 새로운 최상위 노드의 바로 아래 노드를 찾는다.

3. 스택 구조체에 최상위 노드의 주소를 등록한다.

4. 1단계에서 저장했던 예전 최상위 노드의 주소를 반환한다.

 

코드로 먼저 보겠습니다.

---

Node* popNodeLIS(likedListStack* stack)
{
	Node* popNode = stack->top;
	Node* current = stack->list;

	if (stack->top == stack->list)
	{
		stack->top = NULL;
		stack->list = NULL;
	}
	else
	{
		while (current != NULL && current->nextNode != stack->top)
		{
			current = current->nextNode;
		}
		stack->top = current;
		stack->top->nextNode = NULL;
	}

	return popNode;
}

---

 

사실 인과관계를 생각하면 쉽죠. 

1. 현재 최상위 노드의 주소를 다른 포인터에 복사한다.

    1.1 ) POP을 했다면 나가리되는 노드 하나 있을거고.

    1.2 ) 나가리를 저장할 노드를 복사해 놓는다.

 

2. 새로운 최상위 노드의 바로 아래 노드를 찾는다.

    2.1 ) list가 head라고 계속 설명했죠? head서 부터 nextNode가 나가리 노드인지 반복문으로 찾아줍시다.

 

3. 스택 구조체에 최상위 노드의 주소를 등록한다.

    3.1 ) nextNode가 나가리 노드인 tail-1노드가 Top이 되도록, stack->top에 해당 노드를 등록하면 됩니다.

 

4. 1단계에서 저장했던 예전 최상위 노드의 주소를 반환한다.

    4.1 ) 나가리노드 리턴해야하는 함수니까 줘야겠죠.

 

이걸 몰라도 연결 리스트의 조건과 스택의 특징을 같이 생각해주면

안보고도 작성할 수 있을거라 믿습니다.

 

1. POP을 해야된데.. 근데 POP은 스택에서 TOP이 나가는거야...

2. 스택에서 나갔더니.. 어라 연결 리스트에서 TOP의 흔적을 지워야하는데...

3. TOP의 흔적을 가지고 있는 애는.. tail 바로 뒤에있는 애가 nextNode 필드로 가지고 있겠지...

4. head서부터 천천히 찾아서 NULL로 바꿔줘야겠다..

 

이런식으로 생각이 이어지게 됩니다. (제가 그랬어요)

---

연결 리스트 기반 스택 예제 프로그램

지금까지 배운 연산을 모두 활용할 수 있는 프로그램을 작성해 보겠습니다.

---

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#pragma warning(disable:4996)


void printfBar()
{
	printf("================================================================\n");
}

typedef struct tagNode
{
	char* data;
	struct tagNode* nextNode;

}Node;

typedef struct tagLikedListStack
{
	Node* list;
	Node* top;

} likedListStack;

typedef int elementType;

Node* createNodeLIS(char* data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = (char*)malloc(sizeof(data) + 1);

	strcpy(newNode->data, data);

	newNode->nextNode = NULL;
	
	printf("[data : %s] 노드 생성중.. \n", data);
	return newNode;
}

void destroyNodeLIS(Node* node)
{
	free(node->data);
	free(node);
}

void createStackLIS(likedListStack** stack)
{
	(*stack) = (likedListStack*)malloc(sizeof(likedListStack));
	(*stack)->top = NULL;
	(*stack)->list = NULL;
	printf("stack 생성 완료..\n");
}

int isEmptyLIS(likedListStack* stack)
{
	return stack->list == NULL;
}

Node* popNodeLIS(likedListStack* stack)
{
	Node* popNode = stack->top;
	Node* current = stack->list;

	if (stack->top == stack->list)
	{
		stack->top = NULL;
		stack->list = NULL;
	}
	else
	{
		while (current != NULL && current->nextNode != stack->top)
		{
			current = current->nextNode;
		}
		stack->top = current;
		stack->top->nextNode = NULL;
	}

	return popNode;
}

void destroyStackLIS(likedListStack* stack)
{
	while (!isEmptyLIS(stack))
	{
		Node* popNode = popNodeLIS(stack);
		destroyNodeLIS(popNode);
	}
	free(stack);
}

void pushNodeLIS(likedListStack* stack, Node* node)
{
	if (stack->list == NULL)
	{
		stack->list = node;
	}
	else
	{
		stack->top->nextNode = node;
	}
	stack->top = node;
	printf("[data : %s] 노드를 PUSH 합니다.. \n\n", node->data);
}

int getSizeLIS(likedListStack* stack)
{
	Node* curr = stack->list;
	int size = 1;
	while (curr != NULL && curr != stack->top)
	{
		size++;
		curr = curr->nextNode;
	}

	return size;
}



void main()
{
	likedListStack* stack = NULL;
	printfBar();
	printf("stack을 생성합니다.\n");
	createStackLIS(&stack);

	printfBar();
	printf("stack요소를 만들고 PUSH 합니다.....\n");
	
	for (char i = 'A'; i < 'I'; i++)
	{
		char string[4];
		sprintf(string, "%c%c%c", i, i+1, i+2);
		pushNodeLIS(stack, createNodeLIS(string));
	}

	
	printfBar();
	printf("TOP의 데이터를 출력합니다.....\n");
	printf("Top : [%s]\n", stack->top->data);
	
	
	printfBar();
	printf("stack요소를 POP합니다.....\n");

	int size = getSizeLIS(stack);
	for (int i = 0; i < size + 1; i++)
	{
		if (!isEmptyLIS(stack)) printf("POP data : %s\n", popNodeLIS(stack)->data);
		else printf("[%d] error : stack is empty\n", i + 1);

	}
	printfBar();
	printf("stack을 해제합니다.\n");
	destroyStackLIS(stack);
}

 

추가된게 쭤금 있긴하네요.

 

---

끝으로

 

틀린 점이 있다면 알려주세요

 

이해 안가는 부분이 있다면 장문으로 물어도 좋으니 언제든 물어봐주시길 바랍니다.

 

참고

이것이 자료구조 알고리즘이다 with C언어