Stack 예제를 통한 정리 1편 (자료구조, MCU 모두 정리)

안녕하세요.

오늘은 Stack에 대해서 정리해 보는 시간을 가지도록 하겠습니다.

MCU안에는 RAM과 Flash가 있습니다.

RAM에는 DataRAM 영역과 Stack이 존재하는데요.

 

Stack은 MCU안에 있는 RAM에서

일부 영역을 할당하여 사용하는 메모리 영역입니다.

보통 Stack은 function call이 불리거나, 인터럽트가 발생하면

지역변수를 저장하고, Core Register 및 핵심 레지스터를 저장하는 역할을 수행합니다.

​

그런데 자료구조에서도 우리는 동일하게 Stack에 대해서 배우게 됩니다.

그리고 알고리즘에서 Stack의 구조 형태를 사용하기도 합니다.

 

MCU에서는 이러한 Stack구조의 형태를 

​지역변수 저장의 관점에서 아주 잘 사용하고 있습니다.

 

그렇다면 지금부터 자료구조 Stack 예제를 한번 구현해보면서

Stack의 원리를 알아보는 시간을 가지고

다음 글에서 MCU안의 Stack이 실제로 어떻게 동작하는지 알아 보도록 하겠습니다.​

​

먼저 Stack 의 데이터 구조 예제를  구현 및 실행해 보도록 하겠습니다.

이 예제도 예전에 좋은 강의를 통해 얻게 된 예제 입니다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#define MAX_STACK_SIZE 5
#define TRUE 1
#define FALSE 0

typedef unsigned char uint8_t;
typedef unsigned int uint32_t;
typedef int int32_t;

typedef struct _element
{
	int key;
}element;

typedef struct _Stack
{
	element items[MAX_STACK_SIZE];
	int top;
}Stack;

int main(void)
{
	int i;
	Stack my_stack;

	return 0;
}

 

위의 코드에서 Stack이 아래와 같은

그림이 그려지는 것을 알 수 있습니다.

먼저 Items[0]이 들어가고

그 다음에 Items[1]이 들어가게 됩니다.

그럼, 이제부터

Stack을 구현하기 위해서 필요한 API를한번 구현해 보도록 하겠습니다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#define MAX_STACK_SIZE 5
#define TRUE 1
#define FALSE 0

typedef unsigned char uint8_t;
typedef unsigned int uint32_t;
typedef int int32_t;

typedef struct _element
{
	int key;
}element;

typedef struct _Stack
{
	element items[MAX_STACK_SIZE];
	int top;
}Stack;

uint8_t IsEmpty(const Stack* pStack)
{
	if (pStack->top == -1)
		return TRUE;
	else
		return FALSE;
}

uint8_t IsFull(const Stack* pStack)
{
	if (pStack->top >= MAX_STACK_SIZE - 1)
		return TRUE;
	else
		return FALSE;
}

void Push(Stack* pStack, element item)
{
	if (IsFull(pStack) == TRUE)
	{
		printf("Stack is Full. Cannot Add.\n");
	}
	else
	{
		pStack->items[++pStack->top] = item;
	}
}

element Pop(Stack* pStack)
{
	element temp;

	if (IsEmpty(pStack) == TRUE)
	{
		printf("Stack is empty. Cannot Remove. \n");
		temp.key = -1;
		return temp;
	}

	return pStack->items[pStack->top--];
}

void Initialize(Stack* pStack)
{
	pStack->top = -1;
}

void print_stack(const Stack* pStack)
{
	int i;
	printf("stack : ");
	if (IsEmpty(pStack) == TRUE)
	{
		printf("Empty\n");
	}
	else
	{
		for (i = 0; i <= pStack->top; i++)
		{
			printf("%d ", pStack->items[i].key);
		}
		printf("\n");
	}
}

element get_element(const int key)
{
	element new_element;
	new_element.key = key;
	return new_element;
}


int main(void)
{
	int i;
	Stack my_stack;
	Initialize(&my_stack);
	print_stack(&my_stack);
	Push(&my_stack, get_element(1));
	print_stack(&my_stack);
	return 0;
}

Push를 한번 생각해 보겠습니다.

 

우리는 Push를 통해서 Item을 넣을 것입니다.

이때 그림은 아래와 같이 표현 할 수 있습니다.

그러면 아래와 같이 6개를 넣으면 하나는 들어가지 못합니다.

최대 크기가 5개까지 넣을수 있으니까요.

int main(void)
{
	int i;
	Stack my_stack;
	Initialize(&my_stack);
	print_stack(&my_stack);
	Push(&my_stack, get_element(1));
	print_stack(&my_stack);
	Push(&my_stack, get_element(2));
	print_stack(&my_stack);
	Push(&my_stack, get_element(3));
	print_stack(&my_stack);
	Push(&my_stack, get_element(4));
	print_stack(&my_stack);
	Push(&my_stack, get_element(5));
	print_stack(&my_stack);
	Push(&my_stack, get_element(6));
	print_stack(&my_stack);
	return 0;
}

그림을 그리면 아래와 같습니다.

우리가 Max Size를 5로 정했기 때문에 아래와 같습니다.

실행시키면 아래와 같습니다.

한번 위의 코드를 실행시켜보도록 하겠습니다.

그러면 아래와 같은 결과가 나오게 됩니다.

그러면 이제 pop을 해서 꺼내 보도록 하겠습니다.

for (i = 0; i < MAX_STACK_SIZE + 1; i++)
	{
		printf("Pop = %d\n", Pop(&my_stack).key);
		print_stack(&my_stack);
	}

pop을 실행시키면 위에서 부터 꺼내고 있습니다.

데이터를 꺼내고 있는것을 알 수 있습니다.

function 안에 또 function을 타서 들어갔다고 생각해 볼게요.

나올때는 가장 나중에 들어가 function부터 나가게 됩니다.

MCU의 stack은 위의 자료구조의 동작데로 정확하게 동작합니다.

이 부분에 대해서는 제가 다음글에서

MCU를 실제로 동작시켜보며 Stack과 동일한 동작을 수행하는것을 보여드리도록 하겠습니다.

​

위의 예제코드는 아래 카페링크에서 다운로드 가능하오니

필요하신분은 다운받으셔서 직접 돌려보시고

Stack에 대해서 공부해 보시길 바랍니다.

 

https://cafe.naver.com/binaryembedded/158

감사합니다.

 

이상으로 금일 포스팅을 마치도록 하겠습니다.