연결 리스트로 구현한 스택

C

c 에서 연결 리스트 개념을 이용하면 크기에 제한이 없는 스택을 구현할 수 있다. 다만 배열로 구현한 스택에 비해 삽입과 삭제에 드는 시간은 좀 더 걸린다.

소스코드

#include <stdio.h>
#include <malloc.h>

typedef int element;

typedef struct StackNode {
    element item;
    struct StackNode* link;
}StackNode;

typedef struct {
    StackNode* top;
}LinkedStackType;

void init(LinkedStackType* s) {
    s->top = NULL;
}

int is_empty(LinkedStackType* s) {
    return (s->top == NULL);
}

void push(LinkedStackType* s, int e) {
    StackNode *temp = (StackNode*)malloc(sizeof(StackNode));
    if (temp == NULL) {
        printf("메모리 할당 에러\n");
    }
    else {
        temp->item = e;
        temp->link = s->top;
        s->top = temp;
    }
}

element pop(LinkedStackType* s) {
    if (is_empty(s)) {
        printf("스택 공백 에러\n");
        return -1;
    }
    else {
        StackNode* temp = s->top;
        element item = temp->item;
        s->top = s->top->link;
        free(temp);
        return item;
    }
}

element peek(LinkedStackType* s) {
    if (is_empty(s)) {
        printf("스택 공백 에러\n");
        return -1;
    }
    else {
        return s->top->item;
    }
}

int main() {
    LinkedStackType s;

    init(&s);

    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    push(&s, 4);
    push(&s, 5);
    push(&s, 6);

    printf("%d\n", pop(&s));

    printf("%d\n", peek(&s));

    return 0;
}

출력

6
5