개념

• 선형 자료구조
• LIFO(Last-In-First-Out, 후입선출)
• 탑(top): 가장 최근에 스택에 삽입된 자료

연산

푸시(Push)

• 자료 삽입
• 넘침(Overflow) 현상 고려

팝(Pop)

• 자료 제거
• 부족(Underflow) 현상 고려

피크(Peek)

• 스택 맨 위 원소(top) 반환

구현

배열 리스트

• 최대 크기 지정
• 추가한 순서대로 배열에 삽입
  👉 top은 currentElementCount -1번째 노드

구조체와 함수 원형

typedef struct ArrayStackNodeType {
	char	data;
}	ArrayStackNode;

typedef struct ArrayStackType {
	int				maxElementCount;
	int				currentElementCount;
	ArrayStackNode	*pElement;
}	ArrayStack;

ArrayStack*		createArrayStack(int maxElementCount);				// 스택 생성
int				pushAS(ArrayStack* pStack, ArrayStackNode element);	// 노드 추가
ArrayStackNode*	popAS(ArrayStack* pStack);							// 노드 제거
ArrayStackNode*	peekAS(ArrayStack* pStack);							// 노드 반환
void			deleteArrayStack(ArrayStack** pStack);				// 스택 제거
int				isArrayStackFull(ArrayStack* pStack);				// 스택이 찼는지 확인
int				isArrayStackEmpty(ArrayStack* pStack);				// 스택이 비었는지 확인
void			displayArrayStack(ArrayStack* pStack);

create

ArrayStack*	createArrayStack(int maxElementCount)	// 스택 생성
{
	ArrayStack *stack;

	if (maxElementCount < 0)
		return (NULL);
	stack = (ArrayStack*)malloc(sizeof(ArrayStack));
	if (stack == NULL)
		return (NULL);
	stack->maxElementCount = maxElementCount;
	stack->currentElementCount = 0;
	stack->pElement = (ArrayStackNode*)malloc(sizeof(ArrayStackNode) * maxElementCount);
	if (stack->pElement == NULL)
	{
		free(stack);
		stack = NULL;
		return (NULL);
	}
	return (stack);
}

push

int	pushAS(ArrayStack* pStack, ArrayStackNode element)	// 노드 추가
{
	if (pStack == NULL)
		return (FALSE);
	if (isArrayStackFull(pStack))
		return (FALSE);
	pStack->pElement[pStack->currentElementCount] = element;
	pStack->currentElementCount++;
	return (TRUE);
}

pop

ArrayStackNode*	popAS(ArrayStack* pStack)		// 노드 제거
{
	ArrayStackNode	*new;
	ArrayStackNode	*element;

	element = peekAS(pStack);
	if (element == NULL)
		return (NULL);
	new = (ArrayStackNode *)malloc(sizeof(ArrayStackNode));
	if (new == NULL)
		return (NULL);
	*new = *element;
	pStack->currentElementCount--;
	return (new);
}

peek

ArrayStackNode*	peekAS(ArrayStack* pStack)		// 노드 반환
{
	if (pStack == NULL)
		return (NULL);
	if (isArrayStackEmpty(pStack))
		return (NULL);
	return (&pStack->pElement[pStack->currentElementCount - 1]);
}

🔗 배열 리스트 스택 전체 코드

연결 리스트

• 최대 크기 지정 불필요
• 스택은 top 노드 포인터를 가지고, top은 이전 노드를 가리킴
  제일 처음 push한 노드는 NULL을 가리킴

구조체와 함수 원형

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);					// 노드 반환
void			deleteLinkedStack(LinkedStack** pStack);		// 스택 제거
int				isLinkedStackEmpty(LinkedStack* pStack);		// 스택이 비었는지 확인
void			displayLinkedStack(LinkedStack* pStack);

create

LinkedStack*	createLinkedStack()		// 스택 생성
{
	LinkedStack	*stack;

	stack = (LinkedStack *)malloc(sizeof(LinkedStack));
	if (stack == NULL)
		return (NULL);
	stack->currentElementCount = 0;
	stack->pTopElement = NULL;
	return (stack);
}

push

int	pushLS(LinkedStack* pStack, StackNode element)	// 노드 추가
{
	StackNode	*new;
	StackNode	*prev;

	if (pStack == NULL)
		return (FALSE);
	new = (StackNode *)malloc(sizeof(StackNode));
	if (new == NULL)
		return (FALSE);
	*new = element;
	prev = peekLS(pStack);
	new->pLink = prev;
	pStack->pTopElement = new;
	pStack->currentElementCount++;
	return (TRUE);
}

pop

StackNode*	popLS(LinkedStack* pStack)						// 노드 제거
{
	StackNode	*element;

	element = peekLS(pStack);
	if (element == NULL)
		return (NULL);
	if (pStack->currentElementCount == 1)
		pStack->pTopElement = NULL;
	else
		pStack->pTopElement = element->pLink;
	pStack->currentElementCount--;
	return (element);
}

peek

StackNode*	peekLS(LinkedStack* pStack)					// 노드 반환
{
	if (pStack == NULL)
		return (NULL);
	if (isLinkedStackEmpty(pStack))
		return (NULL);
	return (pStack->pTopElement);
}

🔗 연결 리스트 스택 전체 코드