스택 (Stack)

같은 자료형의 데이터를 쌓아 놓는 자료구조

후입 선출 : LIFO Last-In Frist-Out 

 

함수 호출 역시 메모리 스택에 쌓이는 구조이다.

시스템 상에서 함수 호출

 

func1() // 호출되어 쌓임

main() // func1() 호출

 

스택 추상 데이터 타입

create(size) // 최대 크기가 size인 공백 스택을 생성

is_full(s) // if (스택의 원소수 == size) return TRUE; 아니라면 return False;

is_empty(s) // if(스택의 원소수 == 0) return TRUE; 아니라면 return False;

push(s, item) // 스택이 풀 상태이면 에러를 반환, 아니라면 스택 맨 위에 item 추가

pop(s) // 스택이 비어있다면 에러 반환, 아니라면 맨 위 원소를 꺼낸후(제거) 반환

peek(s) // 스택이 비어있다면 에러 반환, 아니라면 맨 위 원소를 반환(제거X)

 

 

스택은 기본적으로 1차원배열에서 구현된다. 맨 윗 원소를 반환하기 위해 top 위치를 가지며, 위의 메소드들을 가진다. 

 

✔️ 정적 할당 스택 구현

#include <stdio.h>
#define MAX_STACK_SIZE 100

typedef struct {
    int data[MAX_STACK_SIZE];
    int top;
}Stack;

// 스택 top 초기화
void init_stack(Stack* s) {
    s->top = -1;
}

// 스택이 비어있는지 확인
int is_empty(Stack* s) {
    return s->top == -1;
}

// 스택이 가득찼는지 확인
int is_full(Stack* s) {
    return s->top == (MAX_STACK_SIZE - 1);
}

// 스택에 요소 넣기
void push(Stack* s, int item) {
    if (is_full(&s)) {
        fprintf(stderr, "StackOverFlowError\n");
        return;
    }
    s->data[++(s->top)] = item;
}

// 스택에서 요소 빼기
int pop(Stack* s) {
    if (is_empty(&s)) {
        fprintf(stderr, "StackIsEmpty\n");
        return;
    }

    return s->data[(s->top)--];
}

// 스택 맨 위 요소 찾기
int peek(Stack* s) {
    if (is_empty(&s)) {
        fprintf(stderr, "StackIsEmpty\n");
        return;
    }

    return s->data[s->top];
}

 

 

 

✔️ 동적할당 스택 구현

typedef struct {
    int *data;
    int capacity;
    int top;
} Stack;

void init_stack(Stack* s) {
    s->top = -1;
    s->capacity = 5; // 용량
    s->data = (int*)malloc(s->capacity * sizeof(int)); // 동적 할당
}

void push(Stack *s, int item) {
	// 가득차면 용량 늘리기
	if (is_full(s&) {
    	s->capacity *= 2;
        s->data = (int*)realloc(s->data, s->capacity * sizeof(int));
    }
    
    s->data[++(s->top)] = item;
}

 

init :  top과 용량 값을 정해주고 , data에는 동적할당을 해준다.

push  : 가득 차면 용량을 2배로 넓히고 realloc으로 기존 배열을 용량만큼 더 늘리고 값을 추가한다.

 

 

 

🔖 참고자료

---

• C로 쉽게 풀어쓴 자료구조 - 생능출판사