스택(2)-동적 배열 스택

- 이전까지는 컴파일 시 크기가 결정되는 정적 할당 사용

- 필요한 스택의 크기를 미리 알아야 함 → 곤란

- C언어에서는 malloc()을 호출하여 실행 시간에 메모리를 할당받을 수 있음

- 필요할 때마다 스택 크기를 늘릴 수 있음

typedef int element;
typedef struct{
	element* data;
    int capacity;	//현재 크기
    int top;
}StackType;

- 동적 메모리 할당을 이용하는 스택 코드

//스택 생성 함수
void init_stack(StackType* s) {
	s->top = -1;
	s->capacity = 1;
	s->data = (element*)malloc(s->capacity * sizeof(element));
}

//스택 삭제 함수
void delete(StackType* s) {
	free(s);
}

- 스택 생성 시 1개의 요소를 저장할 수 있는 공간을 일단 확보

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;
}

 - push() 함수에 가장 큰 변화가 있음

- 공간 부족 시 메모리를 2배로 더 확보(s->capacity*=2;)

- pop() 코드는 변경 x

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100

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

int is_empty(StackType* s) {
	return (s->top == -1);
}
int is_full(StackType* s) {
	return (s->top == (s->capacity - 1));
}
void init_stack(StackType* s) {
	s->top = -1;
	s->capacity = 1;
	s->data = (element*)malloc(s->capacity * sizeof(element));
}
void delete(StackType* s) {
	free(s);
}
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;
}
element pop(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[(s->top)--];
}

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));
	free(s.data);
	
	return 0;
}