스택(Stack) - C언어, 배열로 구현

스택

1. 요소의 삽입/삭제가 한쪽 끝에서만 이루어짐
2. 처음에 들어간 것이 마지막에 나오는 구조 - FILO(First In Last Out), LIFO(Last In First Out)
3. 자동 메모리, 대부분의 네트워크 프로토콜이 스택 기반

배열을 이용하여 구현한 스택

1. 스택 생성 초기에 사용자가 부여한 용량만큼의 노드를 한꺼번에 생성
2. 장점: 구현 간단
3. 단점: 스택의 용량을 동적으로 조절하기 어려움

---

0. 노드의 구조

노드가 존재하는 위치는 배열의 인덱스로 알 수 있기 때문에 포인터 없이 데이터만 담는 구조체로 표현

typedef struct tagNode {
    int birth;
    char* name;
} Node;

---

1. 스택의 구조

용량, 최상위 노드의 위치, 노드 배열을 가진 구조체로 표현

typedef struct tagArrayStack {
    int capacity;	// 용량
    int top;		// 최상위 노드 위치, 삽입/제거 시 사용
    Node* stack;	// 쌓이는 노드들 보관
} ArrayStack;

노드 배열이 포인터로 선언된 이유: 포인터를 배열로 사용할 수 있는 C언어의 특성 때문

---

2. 스택 생성

void CreateStack(ArrayStack** as, int capacity) {
    // 스택 구조체를 힙 영역에 생성
    (*as) = (ArrayStack*)malloc(sizeof(ArrayStack));
    (*as)->capacity = capacity;
    (*as)->top = 0;
    // 입력된 용량만큼의 노드를 힙 영역에 생성
    (*as)->stack = (Node*)malloc(sizeof(Node) * capacity);
}

---

3. 스택 확인

// 스택이 다 찼는지 확인
int IsFull(ArrayStack* as) {
    if(as->capacity == as->top) return 1;
    return 0;
}

// 비었는지 확인
int IsEmpty(ArrayStack* as) {
    if(as->top == 0) return 1;
    return 0;
}

---

4. Push

void Push(ArrayStack* as) {
    // 스택에 공간이 남았으면 Push 수행
    if(!IsFull(as)) {
        GetInfo(&as->stack[as->top++]);
    }
}

void GetInfo(Node* node) {
    node->name = (char*)malloc(sizeof(char) * 20);
    printf("이름: ");
    scanf("%s", node->name);
    printf("출생연도: ");
    scanf("%d", &node->birth);
}

---

5. Pop

Node Pop(ArrayStack* as) {
    // 비어있지 않으면 Pop 수행
    if(!IsEmpty(as)) {
        Node node;
        memcpy(&node, &as->stack[--as->top], sizeof(Node));
        return node;
    }
}

---

6. 노드 삭제

void DestroyNode(Node node) {
    // 노드 이름 필드에 할당된 메모리 해제
    free(node.name);
}

---

7. 스택 삭제

void DestroyStack(ArrayStack* as) {
    // 스택 비울 때까지 Pop 수행해서 이름 필드에 할당된 메모리 해제
    while(!IsEmpty(as)) {
        Node node = Pop(as);
        DestroyNode(node);
    }
    // 노드 배열 메모리 해제
    free(as->stack);
    // 스택 구조체 메모리 해제
    free(as);
}

---

8. 예시

int main(void)
{
    ArrayStack* as;
    Node node;
    
    CreateStack(&as, 10);
    Push(as);
    Push(as);
    Push(as);
    
    node = Pop(as);
    printf("Popped--- %s, %d\n", node.name, node.birth);
    DestroyNode(node);
    
    node = Pop(as);
    printf("Popped--- %s, %d\n", node.name, node.birth);
    DestroyNode(node);
    
    DestroyStack(as);
    return 0;
}