5. 데이터 구조 - 동적할당(malloc,realloc)과 스택(stack)

https://spatz.tistory.com/119

 

위의 글에서 구현한 스택은 배열의 크기를 이미 #define을 통해서 정해놓고 시작한다. 하지만 대부분의 코딩 문제나, 프로그래밍할 때는 내가 원하는 배열의 크기를 미리 정해놓을 수 없다. 그러므로 그 크기를 동적할당(malloc)이라는 것으로 메모리를 할당시킨 후에 이를 realloc()이라는 함수를 통해 내용을 그대로 두고 크기를 증가시키며 사용한다.

 

밑에 있는 코드는 이를 구현한 것이다.

#include <stdio.h>
#include <malloc.h>



typedef struct {
	int* data; //동적할당 받을 준비 하기
	int capacity; // 할당 받을 메모리의 현재 크기
	int top; 
} stacktype;

void init_stack(stacktype* s) {
	s->top = -1;
	s->capacity = 1; // 일단 할당 받은 메모리의 크기를 1로 지정
	s->data = (int*)malloc(s->capacity * sizeof(int)); // 메모리의 크기가 capacity인 동적할당 생성
}

void delete_stack(stacktype* s) {
	free(s->data); // 동적으로 할당된 메모리 해제
	s->data = NULL; // 해제된 메모리를 가리키지 않도록 NULL로 설정
}


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


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


void push(stacktype* s, int a) {
	if (is_full(s)) {
		s->capacity *= 2; //만약 동적할당을 할때 capacity가 가득 차면, 전의 크기의 두배를 capacity에 저장
		s->data = (int*)realloc(s->data, s->capacity * sizeof(int)); // 바뀐 capacity의 크기로 동적할당을 다시 함->realloc 함수 사용
		// realloc 함수는 동적메모리의 크기를 변경하는 함수로써, 현재 내용은 유지하면서 주어진 크기로 동적 메모리를 다시 할당
	}

	s->data[++s->top] = a;
}

int pop(stacktype* s) {
	if (is_empty(s)) {
		return 0;
	}
	int result = s->data[s->top--];
	return result;
}

int main(void) {
	stacktype s;
	init_stack(&s);

	push(&s, 1);
	push(&s, 2);
	push(&s, 3);

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