【C/C++】泛型栈

用 C 语言实现泛型栈

mystack.h

1 #ifndef __MYSTACK_H__
 2 #define __MYSTACK_H__
 3 
 4 #include <assert.h>
 5 
 6 // C style，不使用C++的class
 7 typedef struct {
 8     void *elems;
 9     int elemSize;    // 元素大小
10     int logicLen;    // 逻辑长度，栈中当前元素个数，也是下个进栈元素的下标
11     int allocLen;    // 分配的最大内存长度
12     void (*freefn)(void *);    // Free函数指针，用于释放栈元素的内存
13 }stack;
14 
15 // 构造函数
16 void StackNew(stack *s, int elemSize, void (*freefn)(void *) = NULL) {
17     s->elemSize = elemSize;
18     s->logicLen = 0;
19     s->allocLen = 4;    // 初始为栈开辟4个元素的内存
20     s->elems = malloc(s->allocLen * elemSize);
21     assert(s->elems);    // 表达式为0则报错
22     s->freefn = freefn;
23 }
24 
25 // 析构函数
26 void StackDispose(stack *s) {
27     if (s->freefn) {
28         for (int i = 0; i < s->logicLen; i++) {
29             s->freefn((char *)s->elems + i * s->elemSize);
30         }
31     }
32     free(s->elems);
33 }
34 
35 void StackPush(stack *s, void *elemAddr) {
36     if (s->logicLen == s->allocLen) {
37         s->allocLen <<= 1;
38         s->elems = realloc(s->elems, s->allocLen * s->elemSize);
39         assert(s->elems);    // 如果realloc失败，s->elem还会是原来那片内存，并不是NULL，但realloc函数会返回NULL
40     }
41     void *target = (char *)s->elems + s->logicLen * s->elemSize;    // 目的地址
42     memcpy(target, elemAddr, s->elemSize);
43     s->logicLen++;
44 }
45 
46 void StackPop(stack *s, void *elemAddr) {
47     assert(s->logicLen > 0);
48     s->logicLen--;
49     void *source = (char *)s->elems + s->logicLen * s->elemSize;    // 栈顶元素地址
50     memcpy(elemAddr, source, s->elemSize);
51 }
52 
53 #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() 函数

1 void StrFree(void *vp) {
 2     free(*(char **)vp);
 3 }
 4 
 5 int main() {
 6     /* int栈 */
 7     stack intStack;
 8     StackNew(&intStack, sizeof(int));
 9     for (int i = 1; i <= 5; i++) {
10         StackPush(&intStack, &i);
11     }
12     int top;
13     for (int i = 0; i < 5; i++) {
14         StackPop(&intStack, &top);
15         cout << top << endl;
16     }
17     StackDispose(&intStack);
18     /* string栈 */
19     const char *players[] = {"Niko", "Miracle-" ,"Sky" ,"pigff" ,"Yaphets"};
20     stack strStack;
21     StackNew(&strStack, sizeof(char *), StrFree);
22     for (int i = 0; i < 5; i++) {
23         char *copy = strdup(players[i]);
24         StackPush(&strStack, &copy);
25     }
26     char *player;
27     for (int i = 0; i < 5; i++) {
28         StackPop(&strStack, &player);
29         cout << player << endl;
30         free(player);
31     }
32     StackDispose(&strStack);
33     return 0;
34 }

分析：

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

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

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

输出结果：

以上。
原文链接: https://www.cnblogs.com/wayne793377164/p/8854676.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍