[부스트 코딩 뉴비 챌린지 2020] week6_미션02 : 연결 리스트로 Stack 만들기

✔︎ 미션 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 구현

 

---

미션 Q&A

Q.

미션2에서 main함수에서

    StackNode* root = NULL;

라고 작성하면 이제 root 변수가 존재하게 된다.

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

stack속에 값이 있는지 없는지 확인하는 isEmpty()의 정의를 위와 같이 내리셨는데 이렇게 되면 항상 root가 존재한다고 뜨지 않을까?

라는 의문을 가졌었다.

A.

하지만 아래 코드를 살펴보자.

#include <stdio.h>

int main(){
    void* a = NULL;
    if(!a){
        printf("ok");
    }else{
        printf("no");
    }
}

 ok

결과가 ok로 나오는 것을 보아, 포인터의 변수 값을 = NULL로 지정해주면 포인터 변수가 존재하지 않는 것과 마찬가지로 간주한다.

즉, 포인터 변수 속에 값으로 NULL이 아닌 값을 넣어야만 if(a)를 만족하게 된다.(존재)

---

Q. 

왜 StackNode*가 아닌 StackNode**를 사용했을까? 실제로 사용할 땐 (root)가 아닌 (*root)라고 별 첨자만 넣고 기능은 같은데.

A.

 

---

#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));
    if(!node){
        printf("failed to create node\n");
        exit(0);
    }

    node->data = data;
    node->next = NULL;
    return node;
}

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

void push(StackNode** root, int data) {
    StackNode* node = createStackNode(data);

    node->next = (*root);
    *root = node;

    printf("%d pushed to stack\n", data);
}

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

    StackNode *tmp = *root;
    *root = (*root)->next;
    free(tmp);

    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;

    while(root->next == NULL){
        StackNode* tmp = root;
        root = root->next;
        free(tmp);
    }
}

 

설명 주석을 달은 코드

// 연결리스트로 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));
    // malloc사용 후 node가 만들어졌는지 확인
    if(!node){
        printf("failed to create node\n");
        exit(0);
    }
    node->data = data;
    node->next = NULL;
    return node;
}

int isEmpty(StackNode* root) {
    return !root;   //true, false (0,1) 값을 반환. root=NULL일 경우 !root=true(1)
}

void push(StackNode** root, int data) {
    StackNode* node = createStackNode(data);

    node->next = (*root);   //젤 첫 부분에 node가 와야하므로 node다음에 root를 가리킴
    *root = node;   //추가한 node가 젤 첫 부분이므로 root로 추가한 node를 가리킴

    printf("%d pushed to stack\n", data);
}

int pop(StackNode** root) {
    if (isEmpty(*root)) //root가 빈 경우 뺄게 없으므로 종료
        return -9999;
    int popped = (*root)->data; //뺄 값 = 젤 위의 값(=root의 값)

    StackNode *tmp = *root; //tmp: root를 변경하기 전에 root를 저장하여 메모리를 할당함
    *root = (*root)->next;  //root를 root 다음 노드로 변경
    free(tmp);  //tmp(=old root) 메모리 할당

    return popped;
}

int peek(StackNode** root) {
    if (isEmpty(*root)) //root=NULL이라면 최상위 값이 없음
        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;

    //할당받은 메모리 해제
    while(root->next == NULL){
        StackNode* tmp = root;
        root = root->next;
        free(tmp);
    }
}