<뇌를 자극하는 알고리즘 #3>: 배열로 구현된 스택(AS) 퀴즈풀이

Vitamin Quiz

---

문제) 위 예제의 AS_IsFULL(ArrayStack *Stack) 함수를 추가하라. 스택을 생성할 때 정한 용량이 가득 차 있는지 체크하는 기능이다. 함수의 원형은 다음과 같다.

int AS_IsFULL(ArrayStack *Stack);

풀이 // 이 글은 드래그 및 복붙이 안되므로 아래 첨부한 파일을 다운받아 보시기 바랍니다. 첫 번째는 교재의 소스코드 및 헤더파일, 두 번째는 데브맷의 풀이입니다.

---

 문제가 굉장히 쉽다. 왜냐하면, 애초에 ArrayStack 구조체를 정의할 때, Capacity라는 변수도 추가해줬기 때문이다. 따라서 스택이 가득 차 있는지 확이하려면 현재 배열에 들어온 원소의 갯수를 나타내는 Top 변수와 Capacity가 같은지 여부만 체크해주면 된다.

/*************************************************
 ** ArrayStack Vitamin Quiz
*************************************************/

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

typedef int ElementType;

typedef struct tagNode
{
	ElementType Data;
} Node;

typedef struct tagArrayStack
{
	int Capacity;
	int Top;
	Node *Nodes;
} ArrayStack;

void AS_CreateStack(ArrayStack **Stack, int Capacity)
{
	// 스택을 동적할당
	(*Stack) = (ArrayStack *)malloc(sizeof(ArrayStack));

	// 입력된 Capacity 만큼의 노드를 동적할당
	(*Stack)->Nodes = (Node *)malloc(sizeof(Node) * Capacity);

	// Capacity 및 Top 초기화
	(*Stack)->Capacity = Capacity;
	(*Stack)->Top = 0;
}

void AS_DestroyStack(ArrayStack *Stack)
{
	free(Stack->Nodes);
	free(Stack);
}

void AS_Push(ArrayStack *Stack, ElementType Data)
{
	int Position = Stack->Top;
	Stack->Nodes[Position].Data = Data;
	Stack->Top++;
}

ElementType AS_Pop(ArrayStack *Stack)
{
	int Position = --(Stack->Top);
	return Stack->Nodes[Position].Data;
}

// 배열의 특성상 인덱스 값은 Top - 1 이 되어야 한다.
ElementType AS_Top(ArrayStack *Stack)
{
	int Position = Stack->Top - 1;
	return Stack->Nodes[Position].Data;
}

// Stack에 존재하는 원소의 갯수를 리턴
int AS_GetSize(ArrayStack *Stack)
{
	return Stack->Top;
}

int AS_IsEmpty(ArrayStack *Stack)
{
	return (Stack->Top == 0);
}

int AS_IsFull(ArrayStack *Stack)
{
	return (Stack->Top == Stack->Capacity);
}

void main()
{
	int i = 0;
	ArrayStack *Stack = NULL;
	AS_CreateStack(&Stack, 10);

	AS_Push(Stack, 3);
	AS_Push(Stack, 37);
	AS_Push(Stack, 11);
	AS_Push(Stack, 12);
	AS_Push(Stack, 13);
	AS_Push(Stack, 14);
	AS_Push(Stack, 15);
	AS_Push(Stack, 16);
	AS_Push(Stack, 17);
	AS_Push(Stack, 128);

	printf("Capacity: %d, Size: %d, Top: %d\n\n", Stack->Capacity, AS_GetSize(Stack), AS_Top(Stack));
	printf("IsFullStack ? %s\n", AS_IsFull(Stack) == 1 ? "TRUE" : "FALSE");
	for (i = 0; i < 10; i++)
	{
		if (AS_IsEmpty(Stack))
			break;
		printf("Poped: %d, ", AS_Pop(Stack));
		if (!AS_IsEmpty(Stack))
			printf("Current Top: %d\n", AS_Top(Stack));
		else
			printf("Stack Is Empty.\n");
	}

	AS_DestroyStack(Stack);
}
/*************************************************
 ** End Line
*************************************************/

ArrayStack.zip

데브맷 풀이.c