【C/C++】泛型栈

用 C 语言实现泛型栈

mystack.h

 #ifndef __MYSTACK_H__

 #define __MYSTACK_H__

 #include <assert.h>

 // C style，不使用C++的class

 typedef struct {

     void *elems;

     int elemSize;    // 元素大小

     int logicLen;    // 逻辑长度，栈中当前元素个数，也是下个进栈元素的下标

     int allocLen;    // 分配的最大内存长度

     void (*freefn)(void *);    // Free函数指针，用于释放栈元素的内存

 }stack;

 // 构造函数

 void StackNew(stack *s, int elemSize, void (*freefn)(void *) = NULL) {

     s->elemSize = elemSize;

     s->logicLen = ;

     s->allocLen = ;    // 初始为栈开辟4个元素的内存

     s->elems = malloc(s->allocLen * elemSize);

     assert(s->elems);    // 表达式为0则报错

     s->freefn = freefn;

 }

 // 析构函数

 void StackDispose(stack *s) {

     if (s->freefn) {

         for (int i = ; i < s->logicLen; i++) {

             s->freefn((char *)s->elems + i * s->elemSize);

         }

     }

     free(s->elems);

 }

 void StackPush(stack *s, void *elemAddr) {

     if (s->logicLen == s->allocLen) {

         s->allocLen <<= ;

         s->elems = realloc(s->elems, s->allocLen * s->elemSize);

         assert(s->elems);    // 如果realloc失败，s->elem还会是原来那片内存，并不是NULL，但realloc函数会返回NULL

     }

     void *target = (char *)s->elems + s->logicLen * s->elemSize;    // 目的地址

     memcpy(target, elemAddr, s->elemSize);

     s->logicLen++;

 }

 void StackPop(stack *s, void *elemAddr) {

     assert(s->logicLen > );

     s->logicLen--;

     void *source = (char *)s->elems + s->logicLen * s->elemSize;    // 栈顶元素地址

     memcpy(elemAddr, source, s->elemSize);

 }

 #endif

分析：

1、为了实现存放 int 型、double 型、char * 型、自定义类型元素的栈（泛型栈），需要定义一个指明元素大小的变量 elemSize，在栈初始化时传入以开辟足够大小的空间。注意 malloc() 后 assert() 的运用，在内存申请失败时直接退出。

2、如果存储的是基本数据类型，如 char、int 等或者是成员不包含指针的结构体类型，析构函数只需要 free(elems)，而对栈中每个元素则不需要手动 free；如果存储的元素是 char * ，或是指向结构体的指针，或是指向动态申请内存的指针等等，就需要在调用 StackDispose() 之前，将清理栈中元素的方式的信息传给构造函数，即函数指针（指向一段代码）。作为栈结构体的第 5 个成员，它默认是空指针（对于基本数据类型），要么是某个合法的 freefn() 指针（对于用户指定数据结构）。

3、入栈函数 StackPush() 使用 realloc 不断地增长栈的内存空间。对于基础数据类型，elems[logicLen] 即为栈顶元素；而泛型栈中，则需要从具体的内存地址中找到相应的栈顶位置 target，这里同样使用了 void * → char * 的小技巧，并使用 memcpy() 将要入栈的元素拷贝到栈顶地址中去。

4、出栈函数 StackPop() 将出栈元素放在函数的参数列表中，由用户提供一个地址，栈获取栈顶地址指向的元素并将其拷贝到该地址指向的内存中。

main() 函数

 void StrFree(void *vp) {

     free(*(char **)vp);

 }

 int main() {

     /* int栈 */

     stack intStack;

     StackNew(&intStack, sizeof(int));

     for (int i = ; i <= ; i++) {

         StackPush(&intStack, &i);

     }

     int top;

     for (int i = ; i < ; i++) {

         StackPop(&intStack, &top);

         cout << top << endl;

     }

     StackDispose(&intStack);

     /* string栈 */

     const char *players[] = {"Niko", "Miracle-" ,"Sky" ,"pigff" ,"Yaphets"};

     stack strStack;

     StackNew(&strStack, sizeof(char *), StrFree);

     for (int i = ; i < ; i++) {

         char *copy = strdup(players[i]);

         StackPush(&strStack, &copy);

     }

     char *player;

     for (int i = ; i < ; i++) {

         StackPop(&strStack, &player);

         cout << player << endl;

         free(player);

     }

     StackDispose(&strStack);

     return ;

 }

分析：

1、strFree() 函数，虽然接受的参数 vp 是 void *（为了类型通用），但我们编写该函数时逻辑上知道 vp 是 char ** 类型

2、WHY 不在 StackPop()（弹出栈顶元素）之前，释放栈顶字符串的内存空间？？？

因为 StackPop() 函数实际上并没有将一份栈顶字符串的拷贝返回给用户，而是获取栈顶字符串所在内存的地址，并用 memcpy() 复制到用户提供的空间（player），即用户获取的是一个指向该字符串的指针，该字符串的所有权由栈交给用户，因此弹出来的 player 应当由用户需要自行 free()。并且字符串拷贝函数 strdup() 在内部调用了 malloc() 动态分配内存，应该与 free() 成对出现。

输出结果：

以上。