스택 자료구조와 구현

스택 자료구조의 선언부를 먼저 살펴보자.

스택의 구조체 정의는 다음과 같다.

#define MAX_STACK_SIZE 100	// 스택의 최대 크기

typedef int elem_t;
elem_t get_next();
char* str(elem_t e);
void free_elem(elem_t e);

typedef struct {
	elem_t data[MAX_STACK_SIZE];
	int top;
} stack_t;

여기서 중요한 점은 elem_t라는 타입 이름이다. 이것을 이용하므로써 요소 타입이 무엇이든 상관없이 스택 구조체와 함수들을 이용할 수 있게 된다. 예를 들어 maze를 이용하는 경우라면 벽인지, 길인지를 나타내는 문자를 스택에 넣을 요소로 사용할 수 있다. 그 경우는 typedef char elem_t로 바꾸면 아래 있는 코드들을 수정하지 않고 그대로 쓸 수 있다. 또한 트리에 대해 스택을 사용하는 경우는 typedef tree_node_t* elem_t라고 정의할 수 있다. 그러면 스택에 트리 노트의 포인터를 저장해서 트리 방문이나 검색 등에서 사용할 수 있다.

위와 같이 정의된 스택의 데이터에 대해 적용가능한 기능을 다음과 같이 함수 선언으로 미리 정의한다. (이것을 추상데이터타입(ADT)이라고 한다)

// 스택 초기화 함수
void init_stack(stack_t* s);
// 공백 상태 검출 함수
int is_empty(stack_t* s);
// 포화 상태 검출 함수
int is_full(stack_t* s);
// 삽입 함수
void push(stack_t* s, elem_t item);
// 삭제 함수
elem_t pop(stack_t* s);
// 피크 함수
elem_t peek(stack_t* s);

push나 pop에서 elem_t라는 타입이름을 쓴 것을 확인할 수 있다. 여기까지가 stack.h로 헤더파일이 됩니다. 스택을 사용하고자 하는 곳에서는 이것을 인클루드하여 쓸 수 있다.

#pragma once
#define MAX_STACK_SIZE 100	// 스택의 최대 크기

typedef struct {		// 교체!
	short r;
	short c;
} elem_t;

typedef struct {
	elem_t data[MAX_STACK_SIZE];
	int top;
} stack_t;

...  // 리스트 함수 선언들

그럼 이런 스택의 함수를 구현해야 될까? 함수의 구현을 가진 파일은 다음과 같다. 스택이라는 자료구조의 사용을 위해 필요한 함수들의 구현을 모아둔 .c 파일이다. 나중에 스택을이용하는 프로그램에서는 이 헤더 파일을 인클루드하고 프로젝트에 .c 파일을 포함시켜 해당 함수를 호출하면 된다.

여기서 push와 pop 함수를 잠깐 살펴보자.

// 삽입함수
void push(stack_t* s, elem_t item)
{
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else s->data[++(s->top)] = item;
}
// 삭제함수
elem_t pop(stack_t* s)
{
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[(s->top)--];
}

이들 함수에서는 elem_t가 어떤 타입인지에 대해 신경쓰지 않고 그 타입의 지정 기능만 이용해서 저장 및 반환하고 있다. 그러므로 elem_t 타입이 int라면 int를 푸시하고 팝에서도 int를 반환할 것이다. 또 elem_t 타입이 포인터라면 그 포인터 주소를 스택에 저장할 것이고 pop은 그 주소를 반환한다.