C.Interface.And.Implementations—stack的实现

时间:2022-07-15 19:50:06

由于之前一直写C++代码,感觉对指针都很多底层理解不是很深入,于是开始阅读《C.Interface.And.Implementations》这本书籍,这本书经别人推荐说不错,于是从头到尾好好研究一下。


第一章主要阐述了堆栈的接口以及实现。底层使用单链表进行支撑。


=======================stack.h=====================================

#ifndef STACK_INCLUDED
#define STACK_INCLUDED

#define T Stack_T
typedef struct T *T;

extern T Stack_new(void);
extern int Stack_empty(T stk);
extern void Stack_push(T stk, void* x);
extern void *Stack_pop(T stk);
extern void Stack_free(T *stk);

#undef T
#endif

=======================stack.c======================================

#include <stddef.h>
#include <assert.h>
#include "mem.h"
#include "stack.h"

#define T Stack_T
struct T {
    int count;
    struct elem{
        void* x;
        struct elem* link;
    }* head;
};

T Stack_new(){
    T stk;

    NEW(stk);
    stk->count = 0;
    stk->link = NULL;
    return stk;
}

int Stack_empty(T stk){
    assert(stk);
    return stk->count == 0;
}

void Stack_push(T stk, void *x){
    struct elem *t;

    assert(stk);
    NEW(t);
    t->x = x;
    t->link = stk->head;
    stk->head = t;
    stk->count++;
}

void *Stack_pop(T stk){
    void *x;
    struct elem *t;

    assert(stk);
    assert(stk->count > 0);
    t = stk->head;
    x = t->x;
    stk->head = t->link;
    stk->count--;
    FREE(t);
    return x;
}

void Stack_free(T *stk){
    struct elem *t , *u;

    assert(stk && *stk);
    for(t = (*stk)->head; t; t = u){
        u = t->link;
        FREE(t);
    }

    FREE(*stk);
}