스택

삽입과 삭제 연산이 한쪽 끝에서 이루어지는 자료구조

후입선출 : 먼저 입력 된 것이 나중에 출력

스택은 보통 이런 모양으로 만들 수 있다.

MyArrayStack.h

#ifndef __MY_ARRAY_STACK_H__
#define __MY_ARRAY_STACK_H__
#include <stdio.h>
#include <stdlib.h>
#define STACK_LEN 100
typedef enum { F, T }Bool; //Bool 타입 정의
typedef int Data; //Data 타입 정의
typedef struct MyArrayStack {
	Data arr[STACK_LEN];
	int top;
}ArrStack; //Array Stack 구조체 선언
void Stack_Init(ArrStack* pStack) {
	pStack->top = -1;
}

void Stack_Push(ArrStack* pStack, Data item) {
	if (Stack_IsFull(pStack) == F) { //스택이 가득 안 찼다면 스택에 값 하나 추가
		pStack->top += 1;
		pStack->arr[pStack->top] = item;
	}
	else { //스택이 가득 찼을 때 리턴
		return;
	}
}

Data Stack_Pop(ArrStack* pStack) {
	if (Stack_IsEmpty(pStack) == T) {
		return -1; //스택이 모두 비었을 때 리턴
	}
	else
	{
		int item = pStack->arr[pStack->top];
		pStack->arr[pStack->top] = 0;
		pStack->top -= 1; //스택값을 빼고 top 값을 하나 줄이기
		return item;
	}
}

Data Stack_Peek(ArrStack* pStack) {
	if (Stack_IsEmpty(pStack) == T) {
		return -1; //스택이 비었으면 리턴
	}
	else {
		return pStack->arr[pStack->top]; //스택의 탑 값을 바로 리턴
	}
}

Bool Stack_IsEmpty(ArrStack* pStack) {
	if (pStack->top < 0) {
		return T; //스택에 탑이 0이하 즉 -1이라면 T를 반환
	}
	else {
		return F; //아니면 F 반환
	}
}
Bool Stack_IsFull(ArrStack* pStack) {
	if (pStack->top >= (STACK_LEN - 1)) {
		return T;
	}
	else
	{
		return F;
	}
}
#endif

소스.c

#include<stdio.h>
#include "MyArrayStack.h"

int main(void) {
	ArrStack stack;
	Stack_Init(&stack);
	Stack_Push(&stack, 5);
	Stack_Push(&stack, 7);
	Stack_Push(&stack, 8);
	Stack_Push(&stack, 9);
	Stack_Push(&stack, 2);
	printf("top : %d\\n", Stack_Peek(&stack));
	while (!Stack_IsEmpty(&stack))
	{
		printf("%d\\n", Stack_Pop(&stack));
	}
	return 0;
}

결과

과제에 대한 고찰

스택은 예전에 알고리즘을 풀 때 깊이 탐색 문제를 풀 때 많이 사용했는데 이렇게 직접 구현해보니까 스택의 구성을 더 잘 알 수 있어서 좋았다 특히 그냥 후입선출 인줄 알았는데 top을 이용해서 빼는 나름의 알고리즘이 들어 있는 자료구조였다는 것을 이번 과제를 통해 알 수 있었다. 요즘은 대부분 라이브러리에 스택과 큐를 다 사용할 수 있지만 이렇게 구현해보는 것도 코딩 실력을 올리는데 좋은 거 같다.