동적 배열 스택 구현하기

앞에서는 스택의 크기를 고정시켜놓고 컴파일을 하는 1차원 배열 스택을 구현했다.

이번에는 필요에따라 메모리 공간을 할당하는 동적메모리를 활용한 스택을 구현해보자.

---

#include <stdio.h>
#include <stdlib.h>

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

일반적인 스택구현과 다른점은 element *data이다.

동적메모리를 할당할 malloc함수는 리턴값이 포인터이기 때문에,

그 포인터를 받을 포인터변수 data를 선언한다.

---

1.스택초기화, 동적메모리 free

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

스택초기화 함수이다.

capacity변수와 메모리할당 부분이 중요한데,

capacity는 메모리할당량을 어느정도 할 건지에 관여한다.

메모리할당하는 부분을 보자.

element형 메모리를 element크기 X capacity만큼 할당한다.

나중에 capacity가 2라면 element크기의 공간을 2배 할당한다는 뜻이다.

첫번째는 일단 capacity가 1인데, 공간을 1칸 할당한다.

 

 

 

void delete_stack(StackType *s)
{
    free(s->data);
}

할당했다면, 나중에 메모리를 해제해 줘야 할 것이다.

---

2.push함수의 변화

가장 큰 변화가 있는 부분은 push 함수일 것이다.

스택에 데이터를 넣어야 할 때, 메모리 공간이 있는지? 부족하다면 메모리를 늘려줘야 하기 때문이다.

void push(StackType *s, element item)
{
    if(is_full(s) == 1){
        printf("메모리 부족해서 늘립니다.\n");
        s->capacity *= 2;
        s->data = (element *) realloc(s->data, s->capacity * sizeof(element));
    }
    s->data[++(s->top)] = item;
}

만약, 데이터를 넣을때 스택이 꽉 찼다면 capacity를 2배 해주고,

realloc으로 기존메모리의 2배를 재할당 해준다.

그리고 데이터를 메모리에 넣으면 된다.

주의!) else문을 추가해서 s->data[++(s->top)] = item을 하면 안된다.

이렇게하면 메모리가 부족할 때, 재할당만 하고 데이터를 스택에 넣지 못하기 때문이다.(내가 실수했던 부분)

---

동적 배열 스택으로 구현했을 때, 다른 점만 써봤고

나머지는 앞에서 한 구현과 동일하다.

 

전체적인 코드를 보고, 실행해보자.

#include <stdio.h>
#include <stdlib.h>

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

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

void delete_stack(StackType *s)
{
    free(s->data);
}

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

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

void push(StackType *s, element item)
{
    if(is_full(s) == 1){
        printf("메모리 부족해서 늘립니다.\n");
        s->capacity *= 2;
        s->data = (element *) realloc(s->data, s->capacity * sizeof(element));
    }
    s->data[++(s->top)] = item;
}

int pop(StackType *s)
{
    if(is_empty(s) == 1){
        printf("empty\n");
    }
    else
        return s->data[(s->top)--];
}

int main(void)
{
    StackType s; //구조체 변수 선언
    init_stack(&s); //스택 초기화

    push(&s, 1);
    push(&s, 2); //메모리 부족
    push(&s, 3); //메모리 부족
	free(s.data);

    return 0;
}

 

실행결과)

---

과정 살펴보기