스택 Stack

스택(Stack) : LIFO (Last-In-First-Out) = 후입선출                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    

- 리스트와 마찬가지로 선형 자료구조 but 리스트와 다르게 자료의 추가, 제거가 스택의 맨위(top)에서만 이루어짐

 

스택의 연산

푸시(push) : 스택의 맨 위에 새로운 자료를 추가, 스택의 크기를 초과해 push하면 오버플로우

팝(pop) : 스택의 맨 위의 자료를 제거하고 반환, 빈 스택에 pop하면 언더플로우

피크(peek) : 스택의 맨 위의 자료를 제거하지 않고 반환

 

배열을 이용한 스택

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

typedef struct ArrayStackNodeType {		// 노드
	char data;
} ArrayStackNode;

typedef struct ArrayStackType {			// 스택
	int maxCount;
	int curruntCount;
	ArrayStackNode *pData;
} ArrayStack;

ArrayStack	*creatArrayStack(int size)
{
	ArrayStack	*pReturn = NULL;
	pReturn = (ArrayStack *)malloc(sizeof(ArrayStack));
	memset(pReturn, 0, sizeof(ArrayStack));
	pReturn->maxCount = size;

	pReturn->pData = (ArrayStackNode *)malloc(sizeof(ArrayStackNode) * size);
	memset(pReturn->pData, 0, sizeof(ArrayStackNode) * size);

	return (pReturn);
}

int	isArrayStackFull(ArrayStack *pStack)
{
	int	ret = 0;
	if (pStack != NULL)
	{
		if (pStack->curruntCount == pStack->maxCount)
			ret = 1;
	}

	return (ret);
}

int	pushAS(ArrayStack *pStack, char data)
{
	int	ret = 0;
	if (isArrayStackFull(pStack) == 0)
	{
		pStack->pData[pStack->curruntCount].data = data;
		pStack->curruntCount++;
		ret = 1;
	}
	else
		printf("오류, 스택이 가득 찼습니다, pushAS()\n");

	return (ret);
}

int	isArrayStackEmpty(ArrayStack *pStack)
{
	int ret = 0;
	if (pStack != NULL)
	{
		if (pStack->curruntCount == 0)
			ret = 1;
	}

	return (ret);
}

ArrayStackNode	*popAS(ArrayStack *pStack)
{
	ArrayStackNode *pReturn = NULL;
	if (isArrayStackEmpty(pStack) == 0)
	{
		pReturn = (ArrayStackNode *)malloc(sizeof(ArrayStackNode));
		if (pReturn != NULL)
		{
			pReturn->data = pStack->pData[pStack->curruntCount - 1].data;
			pStack->curruntCount--;
		}
		else
			printf("오류, 메모리 할당, popAS()\n");
	}

	return (pReturn);	//	동적할당주소를 반환-> 메모리 해제는 호출한 곳에서
}

ArrayStackNode	*peekAS(ArrayStack *pStack)
{
	ArrayStackNode *pReturn = NULL;
	if (pStack != NULL)
	{
		if (isArrayStackEmpty(pStack) == 0)
			pReturn = &(pStack->pData[pStack->curruntCount - 1]);
	}

	return (pReturn);	//peek은 자료를 제거하지 않기 때문에 메모리 해제 X
}

/*
	pop	: 노드 동적할당주소 반환 (호출한 쪽에서 메모리 해제)
	peek : 탑노드 주소반환 (메모리 해제 X)
*/

void	deleteArrayStack(ArrayStack *pStack)
{
	if (pStack != NULL)
	{
		if (pStack->pData != NULL)
			free(pStack->pData);
		free(pStack);
	}
}

void	displayArrayStack(ArrayStack *pStack)
{
	int i = 0;
	if (pStack != NULL)
	{
		int size = pStack->maxCount;
		int top = pStack->curruntCount;
		printf("스택 크기: %d, 현재 노드 개수:%d\n",
			pStack->maxCount, pStack->curruntCount);
		for (i = size - 1; i >= top; i--)
			printf("[%d]-[Empty]\n", i);
		for (i = top - 1; i >= 0; i--)
			printf("[%d]-[%c]\n", i, pStack->pData[i].data);
	}
}

int main(void)
{
	ArrayStack *pStack = NULL;
	ArrayStackNode *pNode = NULL;

	pStack = creatArrayStack(6);
	if (pStack != NULL)
	{
		pushAS(pStack, 'A');
		pushAS(pStack, 'B');
		pushAS(pStack, 'C');
		pushAS(pStack, 'D');

		displayArrayStack(pStack);

		pNode = popAS(pStack);
		if (pNode != NULL)
		{
			printf("pop 값-[%c]\n", pNode->data);
			free(pNode);
		}

		displayArrayStack(pStack);

		pNode = peekAS(pStack);
		if (pNode != NULL)
			printf("peek 값-[%c]\n", pNode->data);

		displayArrayStack(pStack);

		deleteArrayStack(pStack);
	}

	return (0);
}

 

포인터를 이용한 스택

- 스택의 maxcount를 정하지 않아도 됨

- 배열을 이용한 스택의 탑노드 접근에 걸리는 시간 복잡도 : O(1)

  포인터를 이용한 스택의 탑노드 접근에 걸리는 시간 복잡도 : O(n)

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

typedef struct LinkedStackNodetype {
	char data;
	struct LinkedStackNode *pLink;		//링크
}	LinkedStackNode;

typedef struct LinkedStacktype {
	int currentCount;
	LinkedStackNode *pTop;				// 탑 노드의 포인터
}	LinkedStack;

LinkedStack	*createLinkedStack(void)
{
	LinkedStack *pReturn = NULL;
	pReturn = (LinkedStack *)malloc(sizeof(LinkedStack));
	memset(pReturn, 0, sizeof(LinkedStack));

	return (pReturn);
}

int	pushLS(LinkedStack *pStack, char data)
{
	int ret = 0;
	LinkedStackNode *pNode = NULL;
	if (pStack != NULL)
	{
		pNode = (LinkedStackNode *)malloc(sizeof(LinkedStackNode));
		if (pNode != NULL)
		{
			pNode->data = data;
			pNode->pLink = pStack->pTop;		// 새로 추가한 노드의 이전 노드를 기존 탑노드로 지정
			pStack->pTop = pNode;				// 탑노드를 새로 추가한 노드로 변경

			pStack->currentCount++;
			ret = 1;
		}
		else
			printf("오류, 메모리 할당, pushLS()\n");
	}

	return (ret);
}

int	isLinkedStackEmpty(LinkedStack *pStack)
{
	int ret = 0;
	if (pStack != NULL)
	{
		if (pStack->currentCount == 0)
			ret = 1;
	}

	return (ret);
}

LinkedStackNode *popLS(LinkedStack *pStack)
{
	LinkedStackNode *pReturn = NULL;
	if (pStack != NULL)
	{
		if (isLinkedStackEmpty(pStack) == 0)
		{
			pReturn = pStack->pTop;
			pStack->pTop = pReturn->pLink;		// 새로운 탑노드를 기존의 탑노드 이전 노드로 지정
			pReturn->pLink = NULL;				// 반환 노드의 이전 노드 정보를 초기화

			pStack->currentCount--;
		}
	}

	return (pReturn);							// 동적할당 주소를 반환-> 메모리 해제는 호출한 곳에서
}

LinkedStackNode *peekLS(LinkedStack *pStack)
{
	LinkedStackNode *pReturn = NULL;
	if (pStack != NULL)
	{
		if (isLinkedStackEmpty(pStack) == 0)
			pReturn = pStack->pTop;
	}

	return (pReturn);							// 노드의 주소를 반환-> 메모리 해제X
}

void	deleteLinkedStack(LinkedStack *pStack)
{
	LinkedStackNode *pNode = NULL;
	LinkedStackNode *pDelNode = NULL;
	if (pStack != NULL)
	{
		pNode = pStack->pTop;
		while (pNode != NULL)
		{
			pDelNode = pNode;
			pNode = pNode->pLink;
			free(pDelNode);
		}
		free(pStack);
	}
}

void	displayLinkedStack(LinkedStack *pStack)
{
	LinkedStackNode *pNode = NULL;
	int i = 1;
	if (pStack != NULL)
	{
		printf("현재 노드 개수: %d\n", pStack->currentCount);
		pNode = pStack->pTop;
		while (pNode != NULL)
		{
			printf("[%d]-[%c]\n",
				pStack->currentCount - i, pNode->data);
			i++;
			pNode = pNode->pLink;
		}
	}
}

int main(void)
{
	LinkedStack *pStack = NULL;
	LinkedStackNode *pNode = NULL;

	pStack = createLinkedStack();
	if (pStack != NULL)
	{
		pushLS(pStack, 'A');
		pushLS(pStack, 'B');
		pushLS(pStack, 'C');
		pushLS(pStack, 'D');

		displayLinkedStack(pStack);

		pNode = popLS(pStack);
		if (pNode != NULL)
		{
			printf("pop-[%c]\n", pNode->data);
			free(pNode);
		}

		displayLinkedStack(pStack);

		pNode = peekLS(pStack);
		if (pNode != NULL)
			printf("peek-[%c]\n", pNode->data);

		displayLinkedStack(pStack);

		deleteLinkedStack(pStack);
	}

	return (0);
}