[C] linked list로 stack 만들기

www.notion.so/2-bd4c4037074c42da83e73d016632c3f6

✔︎ 미션 2

1. 미션 제목

연결리스트로 Stack 만들기

2. 지시문

EDWITH CS50 강좌에서 배운 Stack을 보조미션 1에서 배열을 이용해서 구현해 보셨는데요, 이번에는 연결리스트를 이용해서 Stack을 구현하는 과제입니다. 지난 문제와 마찬가지로 아래 표에 함수의 주석 처리된 부분들에 여러분의 코드를 채워 넣어주세요.

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

typedef struct stackNode {
    int data;
    struct stackNode* next;
} StackNode;

StackNode* createStackNode(int data) {
    StackNode* node = (StackNode*)malloc(sizeof(StackNode));
    node->data = data;
    node->next = NULL;
    return node;
}

int isEmpty(StackNode* root) {
    return !root;
}

void push(StackNode** root, int data) {
    // 이 부분을 구현해 주세요!
    printf("%d pushed to stack\n", data);
}

int pop(StackNode** root) {
    if (isEmpty(*root))
        return -9999;
    int popped;
// 이 부분을 구현해 주세요!
		return popped;
}

int peek(StackNode** root) {
    if (isEmpty(*root))
        return -9999;
    return (*root)->data;
}

int main() {
    StackNode* root = NULL;

    push(&root, 10);
    push(&root, 20);
    push(&root, 30);
    push(&root, 40);

    printf("%d pop from stack\n", pop(&root));
    printf("%d pop from stack\n", pop(&root));

    push(&root, 50);
    printf("%d peeked from stack\n", peek(&root));
    printf("%d pop from stack\n", pop(&root));
    printf("%d pop from stack\n", pop(&root));
    printf("%d pop from stack\n", pop(&root));
    return 0;
}

Main 함수를 실행시키면 Stack 출력 결과가 정상적으로 나와야 합니다. 배열과 연결리스트를 이용해서 구현을 해 보셨는데요, 어떤 것이 더 마음에 드셨나요? Main 함수의 내용을 수정해 보면서 실험도 해보시고, Stack 을 구현할 때 리스트를 사용한 방식과 배열을 사용한 방식 중 어떤 방식이 더 좋았는지 느낀 점도 공유해 주세요!

 

3. 핵심 개념

#Stack #연결리스트 #Stack 구현

나의 풀이

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

typedef struct stackNode {
    int data;
    struct stackNode* next;
} StackNode;

StackNode* createStackNode(int data) {
    StackNode* node = (StackNode*)malloc(sizeof(StackNode));
    node->data = data;
    node->next = NULL;
    return node;
}

int isEmpty(StackNode* root) {
    // root가 NULL이면 빈 상태. !root를 return 하여 NULL이면 1을 반환
    return !root;
}

**void push(StackNode** root, int data) {
    // 이 부분을 구현해 주세요!
    StackNode* item = createStackNode(data);
    if (item == NULL) {
        printf("메모리가 부족합니다\n");
        return; // 메모리 할당 실패 시 return
    }
    item->next = *root;
    *root = item;
    printf("%d pushed to stack\n", data);
}**

**int pop(StackNode** root) {
    if (isEmpty(*root))
        return -9999;
    int popped;
    // 이 부분을 구현해 주세요!
    StackNode* temp = *root; // pop 된 노드를 해제하기 위해 temp에 담아준다.
    popped = (*root)->data;
    *root = (*root)->next;
    
    free(temp);
    return popped;
}**

int peek(StackNode** root) {
    if (isEmpty(*root))
        return -9999;
    return (*root)->data;
}

int main() {
    StackNode* root = NULL;

    push(&root, 10);
    push(&root, 20);
    push(&root, 30);
    push(&root, 40);

    printf("%d pop from stack\n", pop(&root));
    printf("%d pop from stack\n", pop(&root));

    push(&root, 50);
    printf("%d peeked from stack\n", peek(&root));
    printf("%d pop from stack\n", pop(&root));
    printf("%d pop from stack\n", pop(&root));
    printf("%d pop from stack\n", pop(&root));
    return 0;
}

미션 2는 연결리스트를 이용한 스택 구현 문제이다. stackNode 구조체는 data와 next를 가진다.

createStackNode()

StackNode* createStackNode(int data) {
    StackNode* node = (StackNode*)malloc(sizeof(StackNode));
    node->data = data;
    node->next = NULL;
    return node;
}

createStackNode 함수는 main 함수에서 사용되지 않았다. 내가 작성해야 할 함수에서 createStackNode 함수를 사용하라는 의미로 해석했다.

기능은 data를 파라미터로 입력 받으면 node를 생성하여 입력 받은 data를 node→data에 삽입하고, node→next 는 NULL을 가리키는 함수이다. 그리고 이렇게 생성된 node를 반환한다.

isEmpty()

int isEmpty(StackNode* root) {
    return !root;
}

isEmpty()함수는 스택이 비어있는지 확인한다. root를 파라미터로 입력 받아서 !root를 반환하는데 처음에 이게 무슨 의미인지 고민이 되었는데 전체적으로 살펴보면서 생각을 해보니 이 프로그램에서 root는 스택에서 가장 마지막에 삽입된 노드를 가리킨다는 것을 추측할 수 있었다.

즉, 스택에 아무 데이터도 없다면 root는 NULL(false)을 가리킬 것이고, !root를 반환한다면 1(true)을 반환하게 될 것이다.

push()

void push(StackNode** root, int data) {
    StackNode* item = createStackNode(data);
    if (item == NULL) {
        printf("메모리가 부족합니다\n");
        return;
    }
    item->next = *root;
    *root = item;
    printf("%d pushed to stack\n", data);
}push()

push 함수는 스택에 아이템을 추가하는 함수이다. 그 과정은 다음과 같이 손으로 작성해보았다.

push 구조

소스 코드에서

push 함수는 위에서 언급한 createStackNode 함수를 활용하여 item 노드를 생성하였다.

 

추가로 item 노드가 NULL을 가리키면 메모리를 정상적으로 할당 받지 못한 것이므로 사용자에게 알리고 함수를 끝내도록 작성하였다.

 

배열 방식과 비교해 연결 리스트의 장점은 메모리 공간에 여유가 있는 한 스택의 크기 제한에서 좀 더 유연하다는 점이다. 하지만 메모리에 여유 공간이 없는 경우가 있을 수 있기 때문에 그 부분을 체크한다.

 

 

그림에서

push 함수의 동작 방식을 보면 data1을 가지는 item 노드를 생성하고 item→next를 root가 가리키고 있던 곳을 가리키도록 설정한다.

 

그리고 root가 item을 가리키도록 설정하면 item 노드는 기존의 스택에 연결이 되고, root는 스택에서 가장 최근에 추가된 노드를 가리키게 된다.

 

이를 반복하면 (메모리가 허용되는 한) 새로운 노드를 계속해서 추가할 수 있다.

pop()

int pop(StackNode** root) {
    if (isEmpty(*root))
        return -9999;
    int popped;
    StackNode* temp = *root;
    popped = (*root)->data;
    *root = (*root)->next;
    
    free(temp);
    return popped;
}

pop함수는 스택에서 가장 최근에 삽입된 노드의 데이터를 출력하고 해당 노드를 스택에서 제거하는 함수이다. 미리 작성된 코드에서 스택이 비어있다면 -9999를 반환하도록 설계되어 있다.

pop 함수의 과정도 다음과 같이 손으로 작성해 보았다.

소스 코드에서

temp 노드를 만들어 root가 가리키는 노드를 담았다.

이후 그림 2번과 같이 popped 변수에 root가 가리키고 있던 노드의 data를 삽입하고, root가 가리키고 있던 노드의 next 포인터를 다음 노드로 변경하였다.

즉, 스택의 가장 마지막에 저장된 데이터를 담고, 스택의 끝(root)을 한 단계 낮춤으로써 마지막에 저장된 노드를 제거하였다.

 

하지만 여기서 끝내면 안된다. 제거된 노드가 여전히 메모리 상에서는 공간을 차지한 채로 메모리 낭비를 하고 있기 때문이다.

위에서 temp 노드에 root가 가리키는 노드를 담은 이유가 바로 이 제거된 노드를 메모리에서 해제해주기 위한 것이다. free(temp)를 통해 메모리 해제를 해준다.

마지막으로 데이터를 담아둔 popped를 return 한다.

peek()

int peek(StackNode** root) {
    if (isEmpty(*root))
        return -9999;
    return (*root)->data;
}

peek함수는 스택이 비어있다면 -9999를 반환하고, 그렇지 않다면 스택의 가장 마지막에 저장되어 있는 데이터를 반환한다.

이 함수가 pop 함수와 다른 점은 둘 다 스택의 가장 마지막에 저장된 데이터를 반환하는 점은 같지만 peek 함수는 마지막 노드를 제거하지 않고, 단순히 검색의 역할을 한다.

main함수와 결과창

주어진 main

 

추가로 2회 pop을 수행한 main