[C언어] 알고리즘을 위한 스택(Stack) 구현

[C언어] 알고리즘을 위한 스택(Stack) 구현

 

스택 (Stack)이란?

스택은 제일 먼저 입력된 데이터가 제일 나중에 출력되는 자료구조입니다.

임베디드 SW에서 CPU가 코드를 수행하기 위해 메모리에 스택을 잡아 놓는데 그 스택과 같은 것입니다.

그래서 예를 들어 설명하면, 데이터가 4, 2, 1, 5로 입력이 되면 5, 1, 2, 4 형태로 출력이 되는 구조입니다.

좋습니다. 그럼 스택을 한번 구현해보도록 하겠습니다.

스택 구현 코드

#define MAXN 10

int sp = 0;
int stk[MAXN];

void push(int d)
{
	stk[++sp] = d; 
}

int top(void)
{
	return stk[sp];
}

void pop(void)
{
	sp--;
}

int empty(void)
{
	if(sp==0) return 1;
	else return 0;
}

int size(void)
{
	return sp;
}

 

스택 구현 코드 설명

sp 변수는 stk 포인터라고 하며 stk 배열에 현재 위치를 알려주기 위한 용도입니다.

그리고 초기값을 0으로 설정해 주어 stk[0] 번째는 비어있는 상태를 유지하도록 만들어 줍니다.

 

이 stk에 데이터를 입력 시키기 위해서는 push 함수를 사용합니다.

push 함수는 sp값을 하나 증가시킨 후 stk배열에 입력된 데이터를 저장합니다.

그럼 stk[1]에 데이터가 입력이 됩니다.

그리고 sp는 1 상태가 됩니다.

 

그리고 현재 sp가 가리키고 있는 값을 읽어올 때는 top 함수를 사용합니다.

top은 stk[sp]값을 리턴하여 줍니다. 대신 값을 읽기만 하는 것이지 데이터를 제거하지는 않습니다.

그래서 데이터를 스택에서 제거하고 싶을 때는  pop함수를 사용하여 sp의 값을 하나 감소시켜줍니다.

그럼 top함수와 pop함수는 친근하게 자주 붙어 다니게 될 것 같습니다.

 

그럼 이제 스택이 계속 감소할 수 없으니 스택이 빈 상태를 출력해주는 함수를 하나 만들어 줍니다.

바로 empty() 함수입니다. sp 값이 0이 되면 stk은 비어있는 상태입니다.

그래서 sp 조건이 0이되면 비어 있다고 판단 하여 1을 리턴하여 주고 그 외에는 비어 있지 않으니까 0을 리턴해 줍니다.

1이 아닌 다른 값을 리턴해주어도 무방합니다.

 

그리고 stk에 현재 담겨있는 데이터의 개수를 알기 위해서 size 함수를 선언하여 sp 값의 리턴해주면 size를 알 수 있게 됩니다.

 

그럼 이제 C언어를 사용하여 스택을 구현 해 보았으니 알고리즘 문제에서 스택을 이용하여 푸는 문제가 나오면 풀수 있겠죠?ㅎㅎ