[Data Structure] 7. Linked Stack

특징

1. 후입선출 (LIFO: Last-In-First-Out)

• 가장 나중에 들어온 자료가 먼저 pop 됨

2. 선형 자료구조

개념

1. 탑: 가장 최근에 스택에 삽입된 자료
   

2. 스택의 3가지 연산

   2-1. PUSH(푸시)
   

   • Overflow 현상이 발생할 수 있음

   2-2. POP(팝)
   

   • Underflow 현상이 발생할 수 있음

   2-3. PEEK(피크)
   

   • 스택의 맨 위에 있는 원소(top)를 반환
   • pop처럼 스택에서 원소를 제거하거나 하지는 않음

3. Linked List로 구현한 스택
   

새로 추가 되는 노드를 Top으로 두고 그 노드를 가리키는 포인터를 둠

바텀 노드가 NULL 포인터를 가리키며, Top노드 부터 먼저 pop 됨

구현

1. linkedstack.c

#include "linkedstack.h"
 
LinkedStack* createLinkedStack()
{
	LinkedStack	*new;
	
	new = calloc(1, sizeof(LinkedStack)); // 현재 노드 개수 및 Top 노드에 대한 포인터 위치 초기화
	if (!new) // 에러처리
		return (NULL);
	return (new);
}

int pushLS(LinkedStack* pStack, StackNode element)
{
	StackNode	*new;

	if (!pStack) // 에러 처리
		return (FALSE);
	new = malloc(sizeof(StackNode));
	if (!new) // 에러 처리
		return (FALSE);
	*new = element; // 역참조를 통한 삽입 노드 정보 저장
	new->pLink = pStack->pTopElement; // 삽입 노드의 pLink에 기존 top 노드에 연결
	pStack->pTopElement = new; // top 포인터에 삽입 노드 연결
	pStack->currentElementCount++; // 현재 원소 개수 갱신
	return (TRUE);
}

StackNode* popLS(LinkedStack* pStack)
{
	StackNode	*ret;

	if (!pStack || pStack->currentElementCount == 0) // 에러 처리 및 스팩 언더플로우 방지
		return (NULL);
	ret = pStack->pTopElement; // 현재 top 노드를 반환 노드에 저장
	pStack->pTopElement = ret->pLink; // top 포인터에 현재 top 노드의 다음 노드 정보를 저장하여 top 노드 갱신
	ret->pLink = NULL; // 스택리스트와 반환 노드 연결 끊기
	pStack->currentElementCount--; // 현재 원소 개수 갱신
	return (ret); // 노드 자체가 반환되기 때문에 이 함수를 호출한 쪽에서 알맞게 free 해 주어야 함
}

StackNode* peekLS(LinkedStack* pStack)
{
	if (!pStack) // 에러 처리
		return (NULL);
	return (pStack->pTopElement); // 탑 노드 반환
}

LinkedStack* reverseLS(LinkedStack* pStack) // 노드 pLink 재연결을 통한 역순 리스트만들기가 아닌 스택구조를 이용한 역순 리스트 만들기
{
	LinkedStack*	reverse;
	StackNode*		node;
	StackNode*		tmp;
	StackNode*		pop;

	if (!pStack) // 에러 처리
		return (NULL);
	reverse = createLinkedStack(); // 역순 리스트 생성
    if (!reverse) // 에러 처리
    	return (NULL);
	node = pStack->pTopElement; // Top 노드 저장
	while(node) // 마지막 노드까지
	{
		tmp = node->pLink; // 현재 노드의 다음 노드 임시 저장
		pop = popLS(pStack); // 기존 스택에서 top 노드 pop
		pushLS(reverse, *pop); // pop 된 노드를 역참조하여 reverse 스택에 push -> 역순 리스트 생성
		free(pop); // reverse 스택에 새 노드가 생성되었기 때문에 기존 스택 pop 노드 free
		node = tmp; // 임시 저장해 두었던 tmp 노드를 받아 다음 노드로 이동
	}
	deleteLinkedStack(pStack); // 기존 스택 delete
	return (reverse); // reverse 스택 반환
}

void	displayStack(LinkedStack *pStack)
{
	StackNode	*cur;
	int			i;

	if (!pStack) // 예외 처리
	{
		printf("No List\n\n");
		return ;
	}
	printf("(1) Current Element count: %d\n", pStack->currentElementCount);
	if (pStack->currentElementCount == 0)
		printf("(2) Element: No Element");
	else
		printf("(2) Element: \n");
	cur = pStack->pTopElement;
	i = 0;
	while (cur)
	{
		printf("[%d]: %c", i++, cur->data);
		if (i != pStack->currentElementCount)
			printf(", ");
		cur = cur->pLink;
	}
	printf("\n\n");
}

int isLinkedStackFull(LinkedStack* pStack)
{
	return (FALSE); // Array List 기반 스택과 달리 Linked list 기반 스택의 경우 메모리 부족을 제외하고는 FULL에 해당 될 수 없음
}

int isLinkedStackEmpty(LinkedStack* pStack)
{
	if (!pStack) // 예외 처리
		return (-1);
	return (pStack->currentElementCount == 0); // 원소 개수 비교하여 반환
}

void deleteLinkedStack(LinkedStack* pStack)
{
	StackNode	*node;
	StackNode	*tmp;

	if (!pStack) // 예외 처리
		return ;
	pStack->currentElementCount = 0; // 현재 원소 개수 갱신
	node = pStack->pTopElement; // top 노드부터 순환하며 free하기 위해 top 노드 저장
	while (node) // 마지막 노드까지
	{
		tmp = node->pLink; // 현재 노드의 다음 노드 임시 저장
		node->pLink = NULL; // free 된 노드를 통해 접근할 수 없도록 스택과 노드 연결 끊기
		free(node); // 노드 free 
		node = tmp; // 임시 저장해 두었던 tmp  노드를 받아 다음 노드로 이동
	}
	free(pStack); // 스택 free
}

2. linkedstack_main.c

#include "linkedstack.h"

int main(void)
{
	LinkedStack	*pStack;
	StackNode	*node;
	StackNode	stackNode;
	int			loop;
	int			opt;

	pStack = NULL;
	loop = 1;
	while (loop)
	{
		printf("[1] Create [2] Push [3] Pop [4] Peek [5] Reverse [6] Check Full [7] Check Empty [8] Display [9] Delete [10] Exit ");
		scanf("%d", &opt);
		switch (opt)
		{
			case 1:
				if (pStack)
				{
					printf("Stack already exists.\n\n");
					break;
				}
				pStack = createLinkedStack();
				if (pStack)
					printf("Create linked stack: Success\n\n");
				else
					printf("Create linked stack: Fail\n\n");
				break;
			case 2:
				if (!pStack)
				{
					printf("There is no stack. Please create first.\n\n");
					break;
				}
				printf("Data: ");
				scanf(" %c", &stackNode.data);
				if (pushLS(pStack, stackNode))
				{
					printf("Push: Success\n\n");
					displayStack(pStack);
				}
				else
					printf("Push: Fail\n\n");
				break;
			case 3:
				node = popLS(pStack);
				if (node)
				{
					printf("Pop: %c\n\n", node->data);
					free(node); // pop 노드 free
					node = NULL; // free 된 노드를 통해 접근 할 수 없도록 초기화
					displayStack(pStack);
				}
				else
					printf("Pop: fail\n\n");
				break;
			case 4:
				node = peekLS(pStack);
				if (node)
					printf("Peek: %c\n\n", node->data);
				else
					printf("Peek: Fail\n\n");
				break;
			case 5:
				pStack = reverseLS(pStack);
				if (pStack)
				{
					printf("Reverse: Success\n\n");
					displayStack(pStack);
				}
				else
					printf("Reverse: Fail\n\n");
				break;
			case 6:
				if (isLinkedStackFull(pStack))
					printf("Yes\n\n");
				else
					printf("No\n\n");
				break;
			case 7:
				if (isLinkedStackEmpty(pStack) == -1)
					printf("No Stack\n\n");
				else if (isLinkedStackEmpty(pStack))
					printf("Yes\n\n");
				else
					printf("No\n\n");
				break;
			case 8:
				if (!pStack)
				{
					printf("There is no stack. Please create first.\n\n");
					break;
				}
				displayStack(pStack);
				break;
			case 9:
				if (!pStack)
					printf("Delete: There is no stack.\n\n");
				else
				{
					deleteLinkedStack(pStack);
					pStack = NULL;
					printf("Delete: Success\n\n");
				}
				break;
			case 10:
				loop = 0;
				break;
			default:
				printf("Please enter a valid option\n\n");
				break;
		}
	}
}

3. linkedstack.h

#ifndef _LINKED_STACK_
#define _LINKED_STACK_

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

typedef struct StackNodeType
{
	char data;
	struct StackNodeType* pLink;
} StackNode;

typedef struct LinkedStackType
{
	int currentElementCount;
	StackNode* pTopElement;
} LinkedStack;

LinkedStack* createLinkedStack();
int pushLS(LinkedStack* pStack, StackNode element);
StackNode* popLS(LinkedStack* pStack);
StackNode* peekLS(LinkedStack* pStack);
LinkedStack* reverseLS(LinkedStack* pStack);
void displayStack(LinkedStack *pStack);
int isLinkedStackFull(LinkedStack* pStack);
int isLinkedStackEmpty(LinkedStack* pStack);
void deleteLinkedStack(LinkedStack* pStack);

#endif

#ifndef _COMMON_STACK_DEF_
#define _COMMON_STACK_DEF_

#define TRUE		1
#define FALSE		0

#endif