동적 배열 스택

 

2024.07.22 - [Algorithm] - 스택 (stack)

스택 (stack)

 

  

    
    
    
    
  
int main(void)
{
    StackType t;

    init_stack(&t);
    push(&t, 1);
    push(&t, 2);
    push(&t, 3);
    printf("%d\n", pop(&t));
    printf("%d\n", pop(&t));
    printf("%d\n", pop(&t));
}

 

이전글 구조체를 사용한 스택 구현의 메인함수에서 구조체를 정적으로 생성하였다. 

이번에는 구조체를 동일하게 사용하나, 동적 메모리 할당으로 스택을 생성해보자.

  

    
    
    
    
  
int main(void)
{
    StackType *s;
    s = (StackType *)malloc(sizeof(StackType));
    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);
}

 

  

    
    
    
    
  
StackType *s;
s = (StackType *)malloc(sizeof(StackType));

스택을 동적으로 생성하고 마지막에 free(s)를 통해 사용이 완료된 동적 메모리를 반환한다.

여기서 정적 메모리로 생성된 스택일때와 동적 메모리로 생성된 스택일 때, 함수 호출 방식(& 사용)에서 차이가 나는데

StackType 변수 t를 사용하고, 함수들이 StackType * 타입의 매개변수를 기대하기 때문에 &t로 주소를 전달해야 한다.

하지만 동적 메모리로 생성할때는 StackType * 포인터 s를 사용하고,

이 포인터를 직접 함수에 전달할 수 있고, s 자체가 이미 포인터 타입이기 때문에 &를 사용할 필요가 없다.

  

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

typedef int element;
typedef struct {
	element *data;		// 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));
}

// 공백 상태 검출 함수
int is_empty(StackType *s)
{
	return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType *s)
{
	return (s->top == (MAX_STACK_SIZE - 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;
}
// 삭제함수
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;
}