C语言深处

        接下来我们来学习通用指针的实际应用，来实现一个可以存放任意类型数据通用栈。栈在内存中为一段连续的内存空间，有一个针指void *p指向栈顶元素。当有新元素入栈时，p向上（向低地址）移动4byte，然后将新元素入栈，此时p指向新元素地址，即p永远指向栈顶元素。当对栈执行出栈操作时，将栈顶元素出栈，再将p向下（向高地址）移动4byte，于是p仍指向栈顶元素。有两个特殊情况需要处理：

1. 当栈为空时p指向栈底，此时执行出栈则失败；
2. 当栈满并执行入栈操作时需要向系统申请更大的内存空间，如申请失败则入栈失败。

        我们在实现通用栈时要注意，实际上栈中元素并不是真正意义上的“数据内容”，而是指向这些“数据内容”的指针，这也就是为什么在入栈和出栈时p总是移动4byte的原因。下面就来看一下通用栈的实现过程，首先定义一个栈的数据结构：

typedef struct
{
        //栈大小，以元素个数为单位
        int stack_size;
        //元素个数
        int ele_count;
        //栈地址
        void *stack_addr;
        //栈顶地址
        void *p;
        //回调函数，在销毁栈时释放未出栈元素的内存
        void (*destructor)(void *);
} stack;

        定义两个函数，一个是栈的“构造函数”，另一个是栈的“析构函数”。当然，在C语言中并没有这两个名词，这里只是借用一下，换句话说就是定义两个函数，一个用于栈的创建，一个用于栈的销毁：

stack* stack_init(void (*destructor)(void *))
{
        //申请栈结构所在的内存空间
        stack *s = malloc(sizeof(stack));
        //初始大小为2
        s->stack_size = 2;
        //当前元素个数为0
        s->ele_count = 0;
        //申请栈空间
        s->stack_addr = malloc(4 * s->stack_size);
        //将指针p设置为栈顶元素
        s->p = s->stack_addr + s->stack_size * 4;
        //设置回调函数，在栈销毁时用于释放未出栈元素的内存
        s->destructor = destructor;
        //返回栈指针
        return s;
}

void stack_des(stack *s)
{
        //循环释放未出栈元素所占用的内存
        for (int i = 0; i < s->ele_count; i++)
        {
                //回调函数，释放内存
                s->destructor((void*) (*(unsigned int *) s->p));
                //p向下移动
                s->p += 4;
        }
        //释放栈内存
        free(s->stack_addr);
        //释放线结构内存
        free(s);
}

       然后再定义两个函数，一个是入栈函数push，另一个是出栈函数pop：

void stack_push(stack *s, void *p_ele)
{
        //p向上移动4byte
        s->p -= 4;
        //将元素入栈，入栈的是一个地址
        *(unsigned int *) s->p = (unsigned int) p_ele;
        //元素个数加1
        s->ele_count++;
        //如果栈满
        if (s->stack_size == s->ele_count)
        {
                //申请2倍大小的内存空间
                s->stack_addr = realloc(s->stack_addr, s->stack_size * 2 * 4);
                //设定指针p的新值
                s->p = s->stack_addr + s->stack_size * 2 * 4 - s->ele_count * 4;
                //复制原数据到新的栈底
                memcpy(s->stack_addr + s->stack_size * 4, s->stack_addr, s->stack_size * 4);
                //栈大小变为2倍
                s->stack_size *= 2;
        }
}

void stack_pop(stack *s, void *p_ele)
{
        //如果栈空，出栈失败
        if (s->ele_count == 0)
        {
                return;
        }
        //出栈
        *(unsigned int *) p_ele = *(unsigned int *) s->p;
        //p向下移动4byte
        s->p += 4;
        //元素个数减1
        s->ele_count--;
}

        再定义一个用于释放内存的函数：

void destructor_int(void *p)
{
        free(p);
}

        这个内存释放函数中直接调用了free函数来释放内存，之所以这样定义而不是在stack_des函数中直接调用free是因为我们所实现的是一个通用栈，这个栈可以存放任意类型的元素，包括用户自定义的数据结构，所以当释放用户自定义的数据结构时就不能直接调用free了，必须要自己编写一个释放内存的函数。最后来看一下main函数中使用栈的实现：

typedef struct
{
        //用于存放名字，这个变量在使用前需要申请内存
        char *name;
        char sex;
        int age;
} human;

//这是专门用于释放human类型元素的回调函数
void destructor_human(void *p)
{
        human *h = (human *) p;
        //释放名字属性
        free(h->name);
        //释放human
        free(h);
}

#define NAME_LEN         (20)

int main(int argc, char **args)
{
        //用于int类型的栈，回调函数为destructor_int
        stack *s = stack_init(&destructor_int);
        //压栈5个元素
        for (int i = 0; i < 5; i++)
        {
                int *val = malloc(sizeof(int));
                *val = i;
                stack_push(s, val);
        }
        //出栈3个元素
        for (int i = 0; i < 3; i++)
        {
                int *val;
                stack_pop(s, &val);
                printf("%d\n", *val);
                free(val);
        }
        //销毁栈
        stack_des(s);

        //用于存放human类型的栈，回调函数为destructor_human
        stack *s2 = stack_init(&destructor_human);
        //创建一个human并入栈
        human *h1 = malloc(sizeof(human));
        h1->name = malloc(NAME_LEN);
        memcpy(h1->name, "Tom", NAME_LEN);
        h1->sex = 'F';
        h1->age = 12;
        stack_push(s2, h1);
        //创建一个human并入栈
        human *h2 = malloc(sizeof(human));
        h2->name = malloc(NAME_LEN);
        memcpy(h2->name, "Jerry", NAME_LEN);
        h2->sex = 'M';
        h2->age = 11;
        stack_push(s2, h2);
        //创建一个human并入栈
        human *h3 = malloc(sizeof(human));
        h3->name = malloc(NAME_LEN);
        memcpy(h3->name, "Lily", NAME_LEN);
        h3->sex = 'F';
        h3->age = 16;
        stack_push(s2, h3);
        //循环出栈，出栈2个元素
        for (int i = 0; i < 2; i++)
        {
                human *h;
                stack_pop(s2, &h);
                printf("Name: %s, Sex: %c, Age: %d\n", h->name, h->sex, h->age);
                free(h);
        }
        //销毁栈
        stack_des(s2);

        return 0;
}

        运行结果：

4
3
2
Name: Lily, Sex: F, Age: 16
Name: Jerry, Sex: M, Age: 11

        可以看到，栈是一个先进后出、后进先出的数据结构。运行结果正确。