教科书上的栈长这样：int stack[MAX]——只能装 int。2022 年 10 月我刚学完数据结构，决定写一个”任意类型都能装”的栈；2024 年 7 月翻出来重写了一遍。两个版本放在一起看特别有意思：一个用 memcpy 把数据拷进容器，一个只存数据的地址——这正是 C 语言里实现泛型容器的两条路线。后来写的通用链表 glist 和计算器的栈，都能在这两条路线里找到自己的位置。

📌 更新（2026-08-31）：为写这篇重新编译复现了两个版本，抓到了 2022 版里的两个老 bug（见复盘一节），实测输出均已录入正文。

2022 版：void* 加 typesize，memcpy 说了算

这个版本的完整设计思路，被当年的我用一段英文注释写在了 stack.h 的开头——现在读来简直就是一篇给自己看的教案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// This stack is implemented by void pointer, so it is GENERIC.
//
// How the void pointer allows assignments of different data types:
//    first, a normal pointer is binded to a data type, so it knows the
//    number of bytes of the data it points to. second, it has an address,
//    which is the start-address of the data. so they can tell the compiler
//    where to start and where to stop accessing the data.
//
//    but void pointer is binded to no data type,it only knows the starting-address.
//    so it can be forcely assigned to any pointers, thus allowing assignments of
//    all data types. so what we do is: when we create the stack, we MALLOC a block
//    of free space, and we take an integer of 'size_t', the typesize, which
//    specifies the length of the data. We use the function MEMCPY, which directly
//    access the addresses,to push the data in the stack and pop data out.
//
// The difference from the definiton:
//    the stack pointer here is different from the definition.
//    when the stack is empty, top == base.
//    when an element is pushed in, top points to the address after the last byte
//    of the element. so the top always points to the next available space.

核心思路浓缩成一句话：普通指针绑定了类型，所以知道数据从哪开始到哪结束；void* 只知道起始地址，所以什么都能指。那就让容器按字节存取——建栈时额外记下每个元素的 typesize，出入栈全靠 memcpy 搬运字节：

1
2
3
4
5
6
7
8
9
10
11
12
13
struct Record
{
    void *top;
    void *base;
    int stacksize;
    int typesize;
};

typedef struct Record *Stack;

Stack CreateStack(int stacksize, size_t typesize);
void Push(Stack S, void *data);
void *Pop(Stack S);

CreateStack(10, sizeof(int)) 一口下去：容量 10 个元素、每个元素 4 字节，内部开 10 * 4 字节的连续空间。Push 把调用方数据的 typesize 个字节原样拷进栈顶：

1
2
3
4
5
6
7
8
9
10
11
void Push( Stack S, void *data)
{
    if( (int)(S->top - S->base) + S->typesize > S->stacksize )
    {
        printf("Out of space to Push.\n");
        exit(1);
    }

    memcpy(S->top, data, S->typesize);
    S->top = (void*)( S->top + S->typesize );
}

S->top + S->typesize 这行有个当年专门查过的知识点：ANSI C 其实不允许对 void* 做运算，因为不知道指向的类型有多大；但 GCC 把 void* 当 char* 处理，按字节算。代码上方还留着一段更早的注释，说”先把指针转成 int 再加减，用完转回来”——那就是 ANSI 保守写法的遗迹，后来发现 GCC 直接支持，代码换成了现在这种便利写法，注释没删，正好留下了思路演进的化石。

这版有个隐藏的设计选择值得注意：容器拥有数据。你 push 一个 int，栈里存的是这个 int 的拷贝——调用方之后改了自己的变量，栈里不受影响。memcpy 是一次彻底的”过户”。

复盘：两个潜伏的 bug

这次为写文章重新编译运行，2022 版当场表演了一下什么叫”能编译不代表对”。

第一个：容量守卫的单位错配。 缓冲区是 stacksize * typesize 字节，但守卫条件拿来比较的却是元素个数：

1
if( (int)(S->top - S->base) + S->typesize > S->stacksize )

CreateStack(10, sizeof(int)) 的意思是”10 个 int”，缓冲区实际有 40 字节；可这个条件在已用 8 字节时就判定”满了”——第三个元素推不进去。2026 年更新时原样编译运行，输出就是当年这个 bug 的现场：

1
Out of space to Push.

main 里推第三个元素直接退出了，三个 Pop 一个都没跑到。修复只需把比较对象换回字节数：

1
if( (int)(S->top - S->base) + S->typesize > S->stacksize * S->typesize )

修完再跑，久违的正常输出：

1
2
3
3
2
1

第二个更危险：Pop 里的未初始化指针。

1
2
3
4
5
6
7
8
void * Pop( Stack S )
{
    void * data;
    ...
    S->top = (void*)( S->top - S->typesize);
    memcpy(data, S->top, S->typesize);
    return data;
}

data 声明时没赋值，是个野指针，memcpy 却往它指向的地方写数据——往随机地址写内存，标准教科书级的未定义行为。2022 年它”能跑”，纯粹是那个栈槽里残留的垃圾值恰好指向一块可写内存；换台机器、换个编译选项，可能当场崩掉。修复要顺手回答一个所有权问题：弹出的数据放哪？让 Pop 内部 malloc 再返回，调用方就得负责 free；更稳妥的写法是改签名让调用方自己出缓冲区——void Pop(Stack S, void *out)，容器只管搬运，内存归调用方。

2024 版：不拷了，只存地址

两年后重写，思路整个掉了个头：既然拷贝要操心 typesize、容量单位、深浅拷贝……那就干脆不拷贝，栈里只存地址。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
typedef struct
{
    void **top;   // 栈顶
    void **end;   // 栈底
    size_t count; // 栈的大小
}STACK;

STACK * creatStack()
{
    STACK *stack=(STACK *)malloc(sizeof(STACK));
    if(stack==NULL)
    {
        return NULL;
    }
    memset(stack,0,sizeof(STACK));
    stack->top=(void **)malloc(STACK_SIZE);
    if(stack->top==NULL)
    {
        free(stack);
        return NULL;
    }
    stack->count=STACK_SIZE/4;
    stack->end=stack->top;
    return stack;
}

int pushbackStack(STACK * stack,void *data)
{
    if( ! isFullStack(stack) )
    {
        *(stack->top)=data;
        stack->top++;
        return 0;
    }
    else
    {
        return -1;
    }
}

void* popStack(STACK *stack)
{
    if( ! isEmptyStack(stack))
    {
        stack->top--;
        return (void*)(*(stack->top));
    }
    else
    {
        return NULL;
    }
}

注意这个结构：top 和 end 都是 void**——指向”指针”的指针。栈的内存区里排的不再是数据本体，而是一个个 void* 槽位；pushbackStack 只做一件事：*(stack->top) = data，把地址塞进槽位，栈顶前移一格。没有 memcpy，没有 typesize——因为根本不需要知道数据长什么样。

测试程序把三种类型轮番进栈出栈：int、字符串、还有 malloc 出来的结构体：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef struct
{
    char name[20] ;
    int age;
}student;

int number1 = 10;
int number2 = 20;
int number3 = 30;
pushbackStack(stack, &number1);
pushbackStack(stack, &number2);
pushbackStack(stack, &number3);

char* st1 = "aaa";
pushbackStack(stack, st1);

student* student1 = (student*)malloc(sizeof(student));
strcpy(student1->name,"xiaoMing");
student1->age = 10;
pushbackStack(stack, student1);

运行效果

当年写完时，我把预期输出记在了文件末尾的注释里。这次重新编译运行，控制台打出来的和那条两年前的注释一字不差：

1
2
3
4
5
6
7
8
9
30
20
10
ccc
bbb
aaa
[name:xiaoBai   age:30]
[name:xiaoHei   age:20]
[name:xiaoMing   age:10]

int 弹出要强转 *(int *)popStack(stack)，结构体弹出要 studentTemp=(student *)popStack(stack)——和 glist 一样，存地址路线的代价就是：取出来的时候，类型信息由调用方自己负责。

两条路线，各自的位置

拷值（memcpy + typesize） 存址（void* 槽位）
容器里有什么 数据本体的一份拷贝 指向数据的地址
需要知道什么 每个元素的 typesize 什么都不用知道
所有权 容器拥有数据，入栈即过户 调用方拥有数据，容器只做登记
生命周期 调用方变量改了不影响栈里 原数据一死，栈里的地址变悬空
典型代表 这篇的 2022 版、计算器的 My_Stack 这篇的 2024 版、glist

拷值路线对小对象友好：int、double 这些几字节的东西，拷贝开销忽略不计，还能摆脱对原变量的依赖。存址路线对大对象和对象池友好：不用搬运、不用关心大小，代价是必须保证原数据活着。写计算器的时候我给 My_Stack 选了存字符串指针的折中路——本质还是存址。而这两篇合在一起看，C 语言泛型容器的全部秘密其实就是一句话：你要么替它记住大小，要么替它只记地址。

完整代码（2022 版）

2024 版的源文件里一部分中文注释在多年的保存、转码中损坏了，所以只以前文片段的形式出现；下面是 2022 版的完整文件——包括那个容量守卫 bug 和未初始化的 data，原样封存：

stack.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// This stack is implemented by void pointer, so it is GENERIC.
//
// How the void pointer allows assignments of different data types:
//    first, a normal pointer is binded to a data type, so it knows the
//    number of bytes of the data it points to. second, it has an address,
//    which is the start-address of the data. so they can tell the compiler
//    where to start and where to stop accessing the data.
//
//    but void pointer is binded to no data type,it only knows the starting-address.
//    so it can be forcely assigned to any pointers, thus allowing assignments of
//    all data types. so what we do is: when we create the stack, we MALLOC a block
//    of free space, and we take an integer of 'size_t', the typesize, which
//    specifies the length of the data. We use the function MEMCPY, which directly
//    access the addresses,to push the data in the stack and pop data out.
//
// The difference from the definiton:
//    the stack pointer here is different from the definition.
//    when the stack is empty, top == base.
//    when an element is pushed in, top points to the address after the last byte
//    of the element. so the top always points to the next available space.

#include<stdio.h>
#include<stdlib.h>

struct Record
{
    void *top;
    void *base;
    int stacksize;
    int typesize;
};

typedef struct Record *Stack;

Stack CreateStack(int stacksize, size_t typesize);
void Push(Stack S, void *data);
void *Pop(Stack S);
int IsEmpty(Stack S);
void Clear(Stack S);
void Destroy(Stack S);
stack.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include"stack.h"
#include<string.h>

Stack CreateStack(int stacksize, size_t typesize)
{
    Stack S = (Stack)malloc(sizeof(struct Record));
    S->base = (void *)malloc(stacksize*typesize);
    if(!S->base)
    {
        printf("Out of space.\n");
        exit(1);
    }

    S->top = S->base;
    S->stacksize = stacksize;
    S->typesize = typesize;

    return S;
}

void Push( Stack S, void *data)
{
    if( (int)(S->top - S->base) + S->typesize > S->stacksize )
    {
        printf("Out of space to Push.\n");
        exit(1);
    }

    memcpy(S->top, data, S->typesize);
    S->top = (void*)( S->top + S->typesize );
}

    // GNU defines the arithmetic of void* equals to char(which is defined as byte).
    // ANSI says we cannot do arithmetic on void* because we don't know the type.
    // so when we update the top pointer, first regard it as an int, and convert it
    // back when we are finished.

void * Pop( Stack S )
{
    void * data;
    if( S->top == S->base )
    {
        printf("Error:Popping an empty stack.\n");
        exit(1);
    }

    S->top = (void*)( S->top - S->typesize);
    memcpy(data, S->top, S->typesize);
    return data;
}

void Clear(Stack S)
{
    S->top = S->base;
}

int IsEmpty(Stack S)
{
    return S->top == S->base;
}

void Destroy(Stack S)
{
    free(S->base);
}

int main()
{
    Stack my_stack;
    my_stack = CreateStack(10, sizeof(int));
    int test1 = 1;
    int test2 = 2;
    int test3 = 3;
    Push(my_stack,&test1);
    Push(my_stack,&test2);
    Push(my_stack,&test3);
    printf("%d\n",*(int *)Pop(my_stack));
    printf("%d\n",*(int *)Pop(my_stack));
    printf("%d\n",*(int *)Pop(my_stack));
    return 0;
}