[C/C++]스택 자료구조 - 정적구현/동적구현

자료구조하면 생각나는 대표격인 구조인 스택입니다.

스택은 쌓는 것을 의미하며 실제로도 쌓는 개념입니다. 후입선출(Last-In-First-Out)의 구조이며 오늘은 정적으로 구현하는 것과 동적메모리할당을 통한 구현. 이렇게 두 가지를 해볼 겁니다.

후입선출이라는 말은 마지막에 들어온게 제일 먼저 빠진다라는 말이죠. 스택에 1-5-3-4 순으로 들어왔다면, 반환순서는 4-3-5-1이 되는 것이죠.

▶정적으로 구현한 스택

#include <stdio.h>

#define MAX_STACK_SIZE 100

typedef int element;
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
} StackType;

스택의 요소인 element를 여기서는 그냥 정수형으로 잡았습니다. 필요에 따라 구조체로 element를 설정할 수 있습니다.

스택의 구조체는 인덱스 역할을 하는 top과 데이터를 담아두는 data배열로 구성되어있습니다.

top은 항상 최근에 데이터가 들어온 위치를 가리키며 비어있을 경우 -1로 설정됩니다. 스택을 비우겠다라고 함은 top을 -1로 설정하는 게 되는 거죠.

void init_stack(StackType *s) {
	s->top = -1;
}

초기화 함수가 그렇게 작동합니다. 인수를 포인터로 받는 이유는 값의 복사가 아니고 직접적으로 이루어져야하기 때문입니다.

int is_empty(StackType* s) {
	return (s->top == -1);
}

int is_full(StackType* s) {
	return (s->top == (MAX_STACK_SIZE - 1));
}

오류검사를 해줄 두 함수입니다. 들어있는 게 없는데 뺄 수 없고, 꽉 차있는데 넣을 순 없으니 이 두 함수를 이용해 스택을 사용하기 전 검사를 해주는 것이죠.

반환값으로 조건식을 넣어주면 실제로 반환되는 값은 is_empty, is_full이 1인지, 0인지가 됩니다.

void push(StackType* s, element item) {
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		exit(1);
	}
	else s->data[++(s->top)] = item;
}

element pop(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택이 비었습니다.\n");
		exit(1);
	}
	else return s->data[(s->top)--];
}

값을 넣는 push함수, 값을 뽑는 pop함수입니다. push함수는 값을 넣는 것이기 때문에 full검사를 먼저한 뒤, top의 위치를 하나 올려서 값을 넣습니다. 아무것도 안넣었을 때가 -1인 이유도 이것이죠. pop함수는 empty검사를 먼저하고, 값을 뽑은 다음 top을 내립니다. 이걸 생각해보면 top은 절대적으로 다음 값에 영향을 받는다는 것을 알 수 있습니다.

다음 값을 넣을 위치가 top이고, 값을 뽑은 후 다음 값의 위치를 top으로 표시하니까 말이죠.

element peek(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택이 비었습니다.\n");
		exit(1);
	}
	else return s->data[(s->top)];
}

peek함수는 pop과 완전히 동일하지만 top의 이동, 즉 값을 뽑지 않는다는 점이 다릅니다.

int main() {
	StackType s;
	
	init_stack(&s);
	push(&s, 1);
	printf("%d\n", pop(&s));

	return 0;
}

스택의 생성이 정적으로 진행됩니다. 앞으로 스택을 사용하는 자료구조가 나오게 되면 지금 사용한 방법을 이용하게 됩니다.

스택의 생성을 동적으로 해주려면

int main() {
	StackType *s;
	s = (StackType*)malloc(sizeof(StackType));
    
	init_stack(s);
	push(s, 1);
	printf("%d\n", pop(s));

	free(s);
    
	return 0;
}

이렇게 됩니다. 동적메모리를 사용할 때는 항상 free로 메모리 해제를 해주어야 합니다.

이건 스택의 생성을 동적으로 한 것이지 스택의 크기를 동적으로 잡은게 아닙니다.

▶동적으로 구현한 스택

동적으로 스택을 구현한다는 의미는 스택의 크기를 고정하지 않는다는 이야기입니다.

#include <stdio.h>

typedef int element;
typedef struct {
	element* data;
	int capacity;
	int top;
}StackType;

아까와 달리 data가 포인터로 만들어져있죠. capacity라는 것도 생겼고요. capacity는 용량이죠. 지금 스택의 용량을 의미하며 이 변수로 스택의 크기를 조절하게 됩니다.

void init_stack(StackType* s) {
	s->top = -1;
	s->capacity = 1;
	s->data = (element*)malloc(s->capacity * sizeof(element));
}

초기화 할 때 capacity에는 1이 들어갑니다.

data는 동적메모리로 설정을 해두고요. 이러면 지금 초기화된 내용을 보고 알 수 있는 건 element 1개의 크기만큼 저장할 수 있는 스택이 만들어진 것입니다.

int is_empty(StackType* s) {
	return (s->top == -1);
}

int is_full(StackType* s) {
	return (s->top == (s->capacity - 1));
}

is_full만 검사방법이 살짝 달라졌습니다. capaticy가 최대용량이다 보니까 배열표현방법으로 -1한 것이 마지막 값을 가리키게 되죠.

element pop(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택이 비어있음\n");
		exit(1);
	}
	else return (s->data[(s->top)--]);

}

pop도 달라진게 없습니다.

이 동적으로 구현된 스택에서 제일 주목해야될 점은 push입니다.

void push(StackType* s, element item) {
	if (is_full(s)) {
		s->capacity *= 2;
		s->data = (element*)realloc(s->data, s->capacity * sizeof(element));
	}
	s->data[++(s->top)] = item;
}

full검사를 하고 생기는 일에 주목해야되는 데요, 스택이 가득 찬 경우 일단 최대용량을 두배로 늘려주고, 그 크기만큼 메모리를 재할당 해줍니다.

realloc함수는 메모리 재할당을 해주는 함수로써 지금 내용을 유지하면서 주어지는 메모리 크기로 바꿔줍니다. 지금 코드에서는 가득 찰때마다 용량이 2배로 늘어나는 것을 알 수 있습니다.

main함수에서 사용하는 방법은 같으니 생략하도록 하겠습니다. 동적메모리로 스택을 구현하는 것의 장점은 컴파일 시간에 스택의 크기를 알 필요가 없고, 실행시간에 메모리를 할당 받음으로써 그 때 그 때 용량을 조절하면 된다는 것이죠. 지금은 늘리는 것만 했는데 pop의 경우에도 반감기처럼 만들어서 용량이 절반빌 때마다 realloc을 통해 메모리 관리를 할 수도 있습니다.

"댓글, 공감 버튼 한 번씩 누르고 가주시면 큰 힘이 됩니다"

저작자표시 비영리 동일조건

G Y U L O G