배열로 구현한 스택 - 2024.08.19(월)

스택 - 후입 선출, LIFO(List in First Out)

나중에 들어온 요소가 가장 먼저 나가는 자료구조다.

 

다음과 같은 원통에 요소를 채워넣고 위에서 부터 꺼낸다고 생각하면 편하다.

 

 

typedef struct tagNode
{
	int Data;
}Node;


typedef struct tagStack
{
	int Capacity; // 용량
	int Top; // 최상위 인덱스 캐싱
	Node* Nodes; // 노드 포인터
}Stack; // 스택 정의

typedef enum
{
	false = 0,
	true = 1
}BOOL;

 

노드의 데이터는 int 값이며 스택 필드의 멤버 변수로는 배열의 용량을 알기위한 Capacity, 최상단 노드를 카리키기 위한 Top, 그리고 배열을 가리킬 노드 포인터 이렇게 3개의 맴버 변수를 지정했다. 그리고 가독성을 높이기 위해서 BOOL enum을 만들었다.

스택 초기화 함수

void Stack_Init(Stack** stack, int capacity) // 스택을 초기화합니다.
{
	*stack = (Stack*)malloc(sizeof(Stack));// 스택 포인터 초기화

	if (*stack == NULL)
	{
		printf("스택 포인터가 할당되지 않았습니다.\n");
		return;
	}

	(*stack)->Nodes = (Node*)malloc(sizeof(Node) * capacity); // 배열의 크기를 설정

	if ((*stack)->Nodes == NULL)
	{
		printf("배열이 할당되지 않았습니다.\n");
		return;
	}

	(*stack)->Capacity = capacity;
	// 배열의 크기를 할당
	(*stack)->Top = -1;
	// 배열의 시작 index는 0이므로 현재 요소가 없으므로 Top은 -1
	return;
}

 

 

스택 소멸 함수

void Stack_Destroy(Stack* stack) // 스택 소멸
{
	free(stack->Nodes);
	free(stack);
}

스택 Push, Pop 함수

Node Stack_Pop(Stack* stack)
{
	int position = stack->Top; // 현재 Top 노드 위치

	if (position <= -1)
	{
		printf("모든 스택을 Pop 하였습니다\n");
		return;
	}

	stack->Top -= 1; // Top 노드 감소

	return stack->Nodes[position]; // Top 노드 반환
}

void Stack_Push(Stack* stack, int newData) // 스택에 새로운 Node 추가
{
	if (stack->Top >= stack->Capacity)
	{
		printf("배열의 범위를 넘어섰습니다.");
		return;
	}

	stack->Top += 1;

	stack->Nodes[stack->Top].Data = newData;
}

 

이외 추가적인 함수

BOOL IsStackEmpty(Stack* stack) // 비었는지 확인하는 함수
{
	if (stack->Top == -1)
		return true;

	else
		return false;
}

BOOL IsFull(Stack* stack) // 다 찼는지 확인하는 함수
{
	if (stack->Top == stack->Capacity - 1)
		return true;

	else
		return false;
}

int GetSizeofStack(Stack* stack) // 현재 스택의 사이즈를 확인하는 함수
{
	return stack->Top + 1;
}

 

스택 사용

Stack* stack;
	int capacity = 10;

	Stack_Init(&stack, capacity);

	Stack_Push(stack, 3);
	Stack_Push(stack, 37);
	Stack_Push(stack, 11);
	Stack_Push(stack, 12);

	printf("Capacity : %d, Size : %d, Top : %d\n\n",
		stack->Capacity, GetSizeofStack(stack), stack->Top);

	for (int i = 0; i < 4; i++)
	{
		if (IsStackEmpty(stack))
		{
			break;
		}

		printf("Popped : %d, ", Stack_Pop(stack).Data);

		if (!IsStackEmpty(stack))
		{
			printf("Current Top : %d\n", stack->Nodes[stack->Top].Data);
		}

		else
		{
			printf("Stack Is Empty.\n");
		}
	}

 

출력 결과

 

 

스택 사용

for (int i = 0; i < stack->Capacity; i++)
	{
		Stack_Push(stack, i);
	}

	if (IsFull(stack))
	{
		printf("The Stack is Full\n");
	}

	else
	{
		printf("The Stack is not Full\n");
	}

	for (int i = 0; i < stack->Capacity; i++)
	{
		if (IsStackEmpty(stack))
		{
			break;
		}

		printf("Popped : %d, ", Stack_Pop(stack).Data);

		if (!IsStackEmpty(stack))
		{
			printf("Current Top : %d\n", stack->Nodes[stack->Top].Data);
		}

		else
		{
			printf("Stack Is Empty.\n");
		}
	}

	Stack_Destroy(stack);

출력 결과

 

참고 서적 : 박상현, 이것이 자료구조 + 알고리즘이다 with C, 한빛 미디어, 2022년

수정할 점이 있다면 꼭 알려주세요. 배울 것이 많은 초보자이기에 어떤 조언이든 도움이 됩니다.