[C] 스택과 연결리스트

단순 연결리스트(simply linked list)로 스택을 구현해보자.

리스트뿐만 아니라 스택과 큐도 연결리스트로 구현할 수 있다. 똑같이 구조체로 노드를 정의하고 시작하면 된다.

일단 스택은 top이 head가 된다. 위에서부터 삽입하고 삭제하는거 잊지말기~

이것도 두 가지 방법이 있는데 전역변수를 사용할 것인지 말것인지에 따라 나눠보았다. 왜 전역변수의 유무에 집착하냐고 물어보고 싶으면 저 말고 제 교수님께 여쭤보세요.

 

사용한 함수들은 다음과 같음:

• init(): top을 초기화한다.
• is_empty(): 스택이 비었는지 확인한다.
• push(value): 요소를 삽입한다.
• pop(): top을 삭제한다. (스택은 LIFO이기 때문에 무조건 맨 위의 요소를 삭제한다. User Input으로 못 받아옴!!!!)
• peek(): top을 반환한다. 삭제하지는 않음.
• print_all(): 스택 안의 모든 요소를 순차적으로 출력한다.

이번에도 is_full()은 굳이 쓸 필요가 없을 것 같아서 안씀.

 

(1) 전역변수 사용

Node* top으로 헤드포인터 정의하고 삽입과 삭제 연산을 각각 해주면 된다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define ERROR_VALUE -300000
 
typedef struct LinkedNode {
    int data;
    struct LinkedNode* link;
}Node;
 
Node* top;
 
void init() { top = NULL; }
int is_empty() { return (top == NULL); }
void push(int value) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->data = value;
    n->link = top; //노드 n의 링크필드가 top이 가리키던 노드를 가리키게 한다
    top = n; //top이 노드 n을 가리키게 한다
}
int pop() {
    Node* removed;
    int value;
    if (is_empty()) {
        printf("Stack Empty Error!\n");
        return ERROR_VALUE;
    }
    else {
        removed = top; //removed를 반환할 것이다
        top = removed->link;
        value = removed->data;
        free(removed);
        return value;
    }
}
int peek() {
    int value;
    if (is_empty()) {
        printf("Stack Empty Error!\n");
        return ERROR_VALUE;
    }
    else {
        value = top->data;
        return value;
        /*
        이 부분은 그냥 return top->data 해도 된다
        */
    }
}
int size() {
    Node* p; //전부 방문하기 위한 노드 p
    int count = 0;
    for (p = top; p != NULL; p = p->link)
        count++;
    return count;
}
void print_all() {
    Node* p;
    printf("STACK STATUS: size=%d\n", size());
    for (p = top; p != NULL; p = p->link)
        printf("[%2d]->", p->data);
    printf("NULL\n");
}
 
int main(void) {
    int sel, value;
 
    init();
    while (1) {
        do {
            printf("1.PUSH 2.POP 3.PEEK 4.STATUS 0.EXIT :");
            scanf("%d", &sel);
        } while (sel < 0 || sel > 4);
        if (sel == 1) {
            printf("Enter value to push from top : ");
            scanf("%d", &value);
            push(value);
        }
        else if (sel == 2) {
            value = pop(); //스택이므로 user input으로 임의대로 pop할 수 없다.
            if (value != ERROR_VALUE)
                printf("[%2d] has been popped out from STACK\n", value);
        }
        else if (sel == 3) {
            value = peek();
            if (value != ERROR_VALUE)
                printf("[%2d] is the top value of STACK\n", value);
        }
        else if (sel == 4) {
            if (is_empty()) printf("Stack is Empty!\n");
            else print_all();
        }
        else break;
    }
    printf("\nE N D  O F  P R O G R A M");
    return 0;
}
 

 

 

(2) 전역변수 미사용

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define ERROR_VALUE -300000
 
typedef struct LinkedNode {
    int data;
    struct LinkedNode* link;
}Node;
 
int is_empty(Node** top) { return (*top == NULL); }
void push(Node**top, int value) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->data = value;
    n->link = *top;
    *top = n; 
}
int pop(Node** top) {
    Node* removed;
    int value;
    if (is_empty(top)) {
        printf("Stack Empty Error!\n");
        return ERROR_VALUE;
    }
    else {
        removed = *top; 
        *top = removed->link;
        value = removed->data;
        free(removed);
        return value;
    }
}
int peek(Node** top) {
    int value;
    if (is_empty(top)) {
        printf("Stack Empty Error!\n");
        return ERROR_VALUE;
    }
    else {
        value = (*top)->data;
        return value;
    }
}
int size(Node** top) {
    Node* p; 
    int count = 0;
    for (p = *top; p != NULL; p = p->link)
        count++;
    return count;
}
void print_all(Node** top) {
    Node* p;
    printf("STACK STATUS: size=%d\n", size(top));
    for (p = *top; p != NULL; p = p->link)
        printf("[%2d]->", p->data);
    printf("NULL\n");
}
 
int main(void) {
    Node* top = NULL; //main에서 바로 초기화(아직도 함수로 할 줄 모름)
    int sel, value;
 
    while (1) {
        do {
            printf("1.PUSH 2.POP 3.PEEK 4.STATUS 0.EXIT :");
            scanf("%d", &sel);
        } while (sel < 0 || sel > 4);
        if (sel == 1) {
            printf("Enter value to push from top : ");
            scanf("%d", &value);
            push(&top, value);
        }
        else if (sel == 2) {
            value = pop(&top); //스택이므로 user input으로 임의대로 pop할 수 없다.
            if (value != ERROR_VALUE)
                printf("[%2d] has been popped out from STACK\n", value);
        }
        else if (sel == 3) {
            value = peek(&top);
            if (value != ERROR_VALUE)
                printf("[%2d] is the top value of STACK\n", value);
        }
        else if (sel == 4) {
            if (is_empty(&top)) printf("Stack is Empty!\n");
            else print_all(&top);
        }
        else break;
    }
    printf("\nE N D  O F  P R O G R A M");
    return 0;
}
 

 

 

<결과 창>

 

STATUS로 전체출력한 걸 보면 스택이 옆으로 누운(?)모양이다. 순서 헷갈릴까봐 끝에 NULL 넣음.

 

 ++ 참고로

typedef struct LinkedNode {
    int data;
    struct LinkedNode* link;
}Node;