[자료구조] 배열을 이용하여 Stack 구현하기(c 언어)

2학년 자료구조 수업을 들으면 가장 먼저 구현하게되는 자료구조가 바로 Stack이다.

Stack은 컴퓨터구조 시간에도 들을 수 있는 아주 친근한 녀석인데 컴퓨터의 메모리 관리하는 파트에서도 적지 않게 들을 수 있다.

Stack은 더미라는 뜻을 가지고 있는데 이는 자료구조에서도 똑같이 생각하면 된다.

value3(top)

value2

value1

 

위의 그림이 stack을 나타낸 것이다. 이를 어떻게 구현해야할까?

처음 이 자료구조를 접한다면 많은 혼란을 겪을 수도 있다. 그러나 생각보다 간단한다.

value1

value2

value3

위의 그림은 배열을 나타낸 것이다. 어떻게 위의 그림과 비슷해 보이지 않는가?

그렇다 Stack을 구현하는 방법에는 많은 방법이 있지만 그 중에서 가장 간단한 배열을 이용해서 스택을 구현할 수 있다. 

#include <stdio.h>
#define MAX_SIZE 10

typedef struct Stack{
  int myStack[MAX_SIZE];
  int top;
}Stack;

위 코드는 배열로 Stack을 구현한 것이다. top 변수는 현재 스택의 가장 최근에 들어온 값을 가르킬 용도로 선언한 것이다.

여기서 주의할 점은 당연한 것이지만 top변수는 절대 Stack의 최대 값을 넘어서는 안된다.

 

우리는 지금 Stack을 만들었으니 이 Stack을 사용하기 위해 push(값을 넣는함수)와 pop(값을 빼는 함수)를 만들어보겠다.

Stack* initStack(){
	Stack* newStack = (Stack*)malloc(sizeof(Stack));
	newStack->top = -1;
	return newStack;
}

void push(Stack* s, int value){
	s->top++;
	if(s->top > MAX_SIZE){
		printf("Stack is overflow!!\n");
		return ;
	}
	s->myStack[s->top] = value;
}

int pop(Stack* s){
	if(s->top < 0){
		printf("Stack is empty!!\n");
		return -1;
	}
	return s->myStack[s->top--];
}

위의 코드에서 initStack 함수의 경우에는 동적할당을 위해서 사용한 함수이므로 여기서는 설명하지 않겠다.

 

push함수의 경우 먼저 초기 값을 -1로 주었으므로 처음에 값을 넣을 때 1을 더해야 하기 때문에 s->top++을 하였고 1을 더한 값이 MAX_SIZE를 넘으면 안되기 때문에 if문으로 검사를 해준다. 이를 전부 다 통과한다면 값을 Stack에 넣고 함수를 종료한다.

 

pop함수의 경우에는 먼저 top변수의 값이 비어있는지 검사를 하기 위해 s->top < 0 이라는 조건문을 넣어주고 이를 만족한다면 리턴값으로 myStack의 최근 값을 돌려주면서 s->top의 변수를 1 감소시킨다.

 

이렇게 배열을 이용한 간단한 함수를 구현해보았다.

 

아래의 코드는 전체 코드이다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10

typedef struct Stack{
	int arr[MAX_SIZE];
	int top;
}Stack;

Stack* initStack(){
	Stack* newStack = (Stack*)malloc(sizeof(Stack));
	newStack->top = -1;
	return newStack;
}

void push(Stack* s, int value){
	s->top++;
	if(s->top > MAX_SIZE){
		printf("Stack is overflow!!\n");
		return ;
	}
	s->arr[s->top] = value;
}

int pop(Stack* s){
	if(s->top < 0){
		printf("Stack is empty!!\n");
		return -1;
	}
	int res = s->arr[s->top--];
	return res;
}

int main(void){
  	Stack *s = initStack();
	push(s, 10);
	push(s, 3);
	push(s, 7);
	push(s, 1);

	printf("%d\n", pop(s));
	printf("%d\n", pop(s));
	printf("%d\n", pop(s));
	printf("%d\n", pop(s));
	return 0;
}

// 코드 실행 시 값
// 1
// 7
// 3
// 10