[C언어 포인터 기반 스택 알고리즘] 스택 삽입 및 삭제하기

💡 이번에는 포인터 기반 스택 삽입 및 삭제하는 방법을 기록해보겠다.

문제

💡 배열 [1, 2, 3, 7, 9]을 삽입하고 배열 [1, 2, 3, 7]로 변경하시오.

당연히 없는 문제기에 대충 내가 만들었다.

해답

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

#define INF 99999999

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct Stack {
    Node *top;
} Stack;

void push(Stack *stack, int data) {
    Node* node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->next = stack->top;
    stack->top = node;
}

int pop(Stack *stack) {
    if (stack->top == NULL) {
        printf("스택 언더플로우가 발생했습니다.\\n");
        return -INF;
    }
    Node *node = stack->top;
    int data = node->data;
    stack->top = node->next;
    free(node);
    return data;
}

void show(Stack *stack) {
    Node *cur = stack->top;
    printf("--- 스택의 최상단 --- \\n");
    while (cur != NULL) {
        printf("%d\\n", cur->data);
        cur = cur->next;
    }
    printf("--- 스택의 최하단 --- \\n");
}

int main(void) {
    Stack stack;
    stack.top = NULL;   // 반드시 NULL값을 넣어주어야 한다.
    show(&stack);
    push(&stack, 1);
    push(&stack, 2);
    push(&stack, 3);
    push(&stack, 7);
    push(&stack, 9);
    pop(&stack);
    show(&stack);
    return 0;
}

설명

배열을 사용한 방법은 코딩하기에는 쉬우나(내 관점) SIZE 를 미리 할당해야하기 때문에 메모리점 관점에서는 좋지 않다고 할 수 있다.

그러나 포인터 기반으로 스택을 쌓으면 따로 사이즈를 미리 정해두지 않아도 되어서 메모리 관점에서 좋다고 할 수 있다.

슨생님이 포인터 잘 안쓴다고 했는데 매 강의마다 포인터가 들어가고 있다.

눈물을 머금고 코드를 하나씩 살펴보자. ༎ຶ‿༎ຶ

next 및 top 설정

typedef struct Node {
    int data;
    struct Node *next;  // 다음 노드와 연결될 수 있게 next를 만들어줘야 한다.
} Node;

typedef struct Stack {
    Node *top;  // 모든 스택은 top이라는 node를 가지고 있으면 된다.
} Stack;

push 함수

void push(Stack *stack, int data) {
    Node* node = (Node*) malloc(sizeof(Node));
    node->data = data;  // node의 데이터를 data로 설정해준다.
    node->next = stack->top;  // 현재 stack의 top이 될 수 있게 한다.
    stack->top = node;  // 항상 처음 들어온 노드가 탑이기 때문에 탑으로 해줌
}

pop 함수

int pop(Stack *stack) {
    if (stack->top == NULL) {
        printf("스택 언더플로우가 발생했습니다.\\n");
        return -INF;
    }
    Node *node = stack->top;    // 최상단 노드에 잠시 넣어둔다.
    int data = node->data;  // 최상단 노드의 데이터를 추출해준다.
    stack->top = node->next;    // 스택의 탑은 최상단 노드의 그 다음 next로 할당해준다.
    free(node); // node 메모리 할당 해제해준다.
    return data;
}

main 함수

int main(void) {
    Stack stack;
    stack.top = NULL;   // 반드시 NULL값을 넣어주어야 한다.
    show(&stack);  // 모든 함수에서 스택변수의 메모리 주소를 넣어주어야 한다.
    push(&stack, 1);
    push(&stack, 2);
    push(&stack, 3);
    push(&stack, 7);
    push(&stack, 9);
    pop(&stack);
    show(&stack);
    return 0;
}

---

마치며..

저번 리스트 알고리즘보다 이해하기 쉬웠으나 C언어는 정말 어렵구나 계속 느끼는 중이다..ㅎㅎ