[자료구조] c언어로 스택 구현하기

안녕하세요 폴라민입니다. 

오늘은 자료구조로 스택을 구현하는 내용을 가지고 왔습니다.

 

저도 스택을 직접 구현해보는 것은 이번 자료구조 수업을 들으면서 처음 해봤습니다.

매번 리스트, 벡터 등등 자료구조를 가져다 쓰기만 해봤죠.

 

막상 구현하려고 하면 막막하지만 개념만 잘 이해하고 있으면 그리 어렵지 않아요! 

그럼 시작해 보겠습니다.

 

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

#define	MAX_STACK_SIZE 100
#define True 1
#define False 0

typedef char Element;
typedef int Bool;

typedef struct{
	Element stackArr[MAX_STACK_SIZE];
	int top;
} Stack;


Stack *Create(void) {
	Stack *new_stack = (Stack *)malloc(sizeof(Stack));
	if (new_stack == 0) // 널 가드
		return 0;
	new_stack -> top = -1;
	return new_stack;
}

Bool isEmpty(Stack *pstack)
{
	if (pstack -> top == -1)
		return True;
	return False;
}

Bool isFull(Stack *pstack)
{
	if (pstack -> top == MAX_STACK_SIZE - 1)
		return True;
	return False;
}

void Push(Stack *pstack, Element Data)
{
	if (isFull(pstack))
    	{
    		printf("stack is full\n");
        	return ;
    	}
	pstack->stackArr[++pstack->top] = Data;
}

Element Pop(Stack *pstack)
{
	if (isEmpty(pstack))
    	{
    		printf("stack is empty\n");
        	return NULL;
    	}
	return pstack->stackArr[pstack->top--];
}

Element Peek(Stack *pstack)
{
	if (isEmpty(pstack))
    	{
    		printf("stack is empty\n");
        	return NULL;
    	}
	return pstack -> stackArr[pstack->top];
}

 

 

이게 스택을 구현한 전체 코드입니다. 별로 복잡하지 않죠?

코드를 하나하나 뜯어봅시다.

 

#define MAX_STACK_SIZE 100
#define ARRAY_SIZE 100
#define True 1
#define False 0

typedef int Bool;
typedef char Element;
typedef struct{
    Element stackArr[MAX_STACK_SIZE];
    int top;
} Stack;

 

우선 define들은 그냥 매크로를 설정해 두었어요. 프로그램 전체적으로 사용할 것 같은 변수들을 저장해 놓았습니다.

Bool이라는 타입을 새로 만들어서 True, False를 사용할 수 있도록 했습니다.

 

https://polarmin.tistory.com/11

[파이썬 자료구조] 스택(stack) - 스택의 개념, 구현, 스택을 활용한 수식의 괄호 검사

 

스택의 상세한 개념은 이곳에서 설명을 해두었으니 파이썬이 익숙하신 분들은 이곳에서 한번 설명을 읽고 오시면 이해하는 데 더 도움이 될 것 같습니다.

 

간단히 설명을 하자면 스택은 길쭉한 바구니에 물건을 하나씩 집어넣어 저장해 둔 뒤,

필요할 때마다 위에서부터 하나씩 꺼내 쓰는 것입니다.

 

 

 

 

 

이제 이것을 c언어 코드를 구현할 것입니다.

 

무엇이 필요할까요?

 

우선 물건을 담을 바구니가 필요하겠죠. 배열로 구현합니다.

Element stackArr[MAX_STACK_SIZE];

 

여기서 Element는 그냥 제가 typedef 로 지정해둔 타입인데 그냥 다음과 같이 쓰셔도 됩니다.

char stackArr[MAX_STACK_SIZE];

 

앞에 타입은 배열에 무엇을 넣을 것인지에 따라 달라집니다.

 

정수를 넣을 것이라면

int stackArr[MAX_STACK_SIZE];

 

가 되겠죠.

 

 

자 여기서만 끝나면 그건 스택이 아닌 그저 배열이겠죠. 스택은 위로 넣고 위에서 꺼내기 때문에 가장 위의 요소를 가리키는 인덱스가 필요합니다.

 

int top;

 

가장 위 요소를 가리킬 인덱스 변수를 하나 선언합니다.

 

 

자 이제 스택 구현은 끝났으니 스택을 활용할 수 있는 함수들이 필요하겠죠.

 

스택을 생성할 create()

스택이 비어있는지, 꽉 차있는지 검사할 isEmpty(), isFull()

스택에 요소를 집어 넣을 Push()

스택에서 요소를 꺼낼 Pop()

스택에서 가장 위에 있는 요소가 무엇인지 알 수 있는 Peek()

 

이렇게만 있어도 스택을 충분히 활용할 수 있습니다. 그럼 구현한 코드를 볼까요?

 

 

Stack *Create(void) {
	Stack *new_stack = (Stack *)malloc(sizeof(Stack));
	if (new_stack == 0) // 널 가드
		return 0;
	new_stack -> top = -1;
	return new_stack;
}

Bool isEmpty(Stack *pstack)
{
	if (pstack -> top == -1)
		return True;
	return False;
}

Bool isFull(Stack *pstack)
{
	if (pstack -> top == MAX_STACK_SIZE - 1)
		return True;
	return False;
}

void Push(Stack *pstack, Element Data)
{
	if (isFull(pstack))
    	{
    		printf("stack is full\n");
        	return ;
    	}
	pstack->stackArr[++pstack->top] = Data;
}

Element Pop(Stack *pstack)
{
	if (isEmpty(pstack))
    	{
    		printf("stack is empty\n");
        	return NULL;
    	}
	return pstack->stackArr[pstack->top--];
}

Element Peek(Stack *pstack)
{
	if (isEmpty(pstack))
    	{
    		printf("stack is empty\n");
        	return NULL;
    	}
	return pstack -> stackArr[pstack->top];
}

 

 

우선 스택을 새로 생성할 때는 동적할당을 사용합니다. 그리고 새로 할당 받은 스택을 반환합니다.

처음에 생성할 때 top은 -1로 초기화합니다.

 

널가드는 동적할당이 실패 했을 경우, NULL을 반환하기 때문에 변수에 NULL이 들어갔을 경우 NULL 포인터를 반환합니다.

스택에 물건을 넣는 것은 top을 하나 늘린 이후에 그 인덱스 위치에 데이터를 넣습니다.

스택에서 물건을 꺼내는 것은 top위치에서 꺼낸뒤 top을 한개 줄입니다. 이때 후위연산자를 사용해줬습니다.

Peek은 top의 변화 없이 그냥 현재 top위치에 있는 요소를 반환합니다.

 

 

이때 주의할점은 push할때는 stack이 꽉차있는지, pop할때는 stack이 비어있는지 확인한 후 코드를 진행해야 한다는 것입니다.

 

 

스택은 굉장히 자주 쓰이는 자료구조 중 하나이니 알아두시면 많은 도움이 됩니다. 별로 어렵지 않으니 한번 구현해서 사용해보세요!

오늘은 여기까지 하도록 하겠습니다.

 

다음에 봬요!!