写在前面
上一篇我们从内存布局、操作效率、CPU缓存三个维度，完整对比了顺序表与链表的底层差异，并在最后引出了一种操作受限的线性表——栈。
栈的逻辑规则非常简单：所有插入、删除操作只能在栈顶完成，遵循后进先出（LIFO）的原则。但真正动手用C语言实现时，很多初学者都会卡在一个经典问题上：top到底应该指向哪里？
常见的实现约定有两种：
top指向栈顶元素的下一个位置，初始化为 0top直接指向当前栈顶元素，初始化为 -1
两种写法都能正确实现栈，没有绝对的对错，核心原则只有一个：一旦确定了 top 的语义，初始化、入栈、出栈、判空、取栈顶等所有操作必须严格遵循同一套规则，绝对不能混用。
本文先完整实现我们日常使用的top=0版本（对齐后续C++学习的思维习惯），再补充常见的top=-1经典写法；最后聊一个很值得思考的问题：明明可以直接访问结构体成员，为什么还要专门封装StackPush、StackSize这些函数？
本篇代码仓库位置
数据结构/8.15 栈的练习Stack · Luminous/Code_2026 - 码云 - 开源中国
一、顺序栈的底层结构设计
顺序栈的本质就是动态数组 + 栈顶标记，底层复用了动态顺序表的扩容逻辑，只是限制了所有操作只能在尾部进行。
1.1 头文件：结构体与接口定义
我们先定义栈的结构体和对外接口，命名和功能都对齐后续C++的学习习惯，同时明确判空规则：栈为空返回非零值，不为空返回0。
// Stack.h #pragma once #include<assert.h> #include <stdlib.h> typedef int STDataType; typedef struct Stack { STDataType* a; int top; // 栈顶标记 int capacity; // 栈的总容量 }Stack; // 初始化栈 void StackInit(Stack* ps); // 入栈 void StackPush(Stack* ps, STDataType data); // 出栈 void StackPop(Stack* ps); // 获取栈顶元素 STDataType StackTop(Stack* ps); // 获取栈中有效元素个数 int StackSize(Stack* ps); // 检测栈是否为空：为空返回非零结果，不为空返回0 int StackEmpty(Stack* ps); // 销毁栈 void StackDestroy(Stack* ps);1.2 三个核心成员的作用
结构体里的三个变量各司其职，共同维护一个动态栈：
a：指向动态数组的指针，真正存储栈中元素的内存空间top：栈顶位置标记，具体含义由我们约定，是整个栈最核心的变量capacity：记录当前已申请的内存总容量，空间不足时触发扩容
二、主流实现：top 指向栈顶元素的下一个位置
这是我们日常开发、后续学习C++ STL最常用的约定，也是本文的主力实现版本。
2.1 核心规则约定
我们可以把栈的有效元素理解为左闭右开区间[0, top)：
- 初始化：
top = 0，表示没有有效元素 - 空栈判定：
top == 0 - 有效元素个数：直接等于
top - 入栈：先在
top位置赋值，再top++ - 取栈顶：访问
a[top - 1] - 出栈：直接
top-- - 满栈判定：
top == capacity
举个例子，栈里有4个元素时，内存布局是这样的：
下标： 0 1 2 3 4 数据： | 10 | 20 | 30 | 40 | | ↑ toptop=4既代表下一个待插入的位置，也等于当前有效元素的总数。
2.2 完整实现代码
以下是完整的Stack.c实现，严格遵循上面的约定：
// Stack.c #include"Stack.h" // 初始化栈 void StackInit(Stack* ps) { assert(ps); ps->a = NULL; ps->top = 0; ps->capacity = 0; } // 入栈 void StackPush(Stack* ps, STDataType data) { assert(ps); // 空间不足时触发扩容 if (ps->capacity == ps->top) { int num = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * num); if(tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity = num; } ps->a[ps->top] = data; ps->top++; } // 出栈 void StackPop(Stack* ps) { assert(ps); assert(ps->top > 0); // 空栈禁止出栈 ps->top--; } // 获取栈顶元素 STDataType StackTop(Stack* ps) { assert(ps); assert(ps->top > 0); // 空栈无栈顶元素 return ps->a[ps->top - 1]; } // 获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps); return ps->top; } // 检测栈是否为空：为空返回非零，不为空返回0 int StackEmpty(Stack* ps) { assert(ps); return ps->top == 0; } // 销毁栈 void StackDestroy(Stack* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = 0; ps->capacity = 0; }2.3 关键细节拆解
（1）入栈为什么先赋值再top++？
因为top本身就指向第一个空闲的可插入位置，直接写入数据即可；写入后top向后移动一位，继续指向新的空闲位置。顺序不能颠倒，否则会跳过下标0的位置，造成空间浪费。
（2）取栈顶为什么是 top-1？
top指向的是栈顶元素的下一个位置，不是有效元素本身。真正的栈顶元素，是top前面的那一个，也就是下标为top-1的元素。
（3）出栈为什么只需要top--，不用清零数据？
出栈本质上是「缩小有效区间」。top--之后，原来的栈顶位置就不在[0, top)这个有效区间里了，逻辑上已经被删除。 内存里的旧数据虽然还在，但后续入栈时会直接被新数据覆盖，完全不需要手动清零。多一步清零反而会增加不必要的开销。
三、教材经典实现：top 直接指向栈顶元素
这是数据结构教材里非常常见的入门写法，top不再代表尾后位置，而是直接记录当前栈顶元素的数组下标。
3.1 核心规则约定
- 初始化：
top = -1，用负数标记空栈状态 - 空栈判定：
top == -1 - 有效元素个数：
top + 1 - 入栈：先
top++，再在top位置赋值 - 取栈顶：直接访问
a[top] - 出栈：直接
top-- - 满栈判定：
top == capacity - 1
同样是4个元素，此时的内存布局是这样的：
下标： 0 1 2 3 数据： | 10 | 20 | 30 | 40 | ↑ toptop=3就是栈顶元素的下标，有效元素总数是 3+1=4。
3.2 完整实现代码
头文件完全不需要修改，只需要替换Stack.c的内部实现，对外接口保持完全一致：
// Stack_top_minus_one.c #include"Stack.h" // 初始化栈 void StackInit(Stack* ps) { assert(ps); ps->a = NULL; ps->top = -1; ps->capacity = 0; } // 入栈 void StackPush(Stack* ps, STDataType data) { assert(ps); // 栈满时扩容：top到达最后一个有效下标 if (ps->top == ps->capacity - 1) { int num = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * num); if(tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity = num; } ps->top++; ps->a[ps->top] = data; } // 出栈 void StackPop(Stack* ps) { assert(ps); assert(ps->top >= 0); // 空栈禁止出栈 ps->top--; } // 获取栈顶元素 STDataType StackTop(Stack* ps) { assert(ps); assert(ps->top >= 0); return ps->a[ps->top]; } // 获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps); return ps->top + 1; } // 检测栈是否为空：为空返回非零，不为空返回0 int StackEmpty(Stack* ps) { assert(ps); return ps->top == -1; } // 销毁栈 void StackDestroy(Stack* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = -1; ps->capacity = 0; }注意：两个版本的函数名完全一致，不要同时加入同一个工程编译，否则会出现重复定义错误，可以分别测试。
3.3 高频易错点
- 初始值不能错：必须是
-1，如果写成0，第一个元素会存在下标1的位置，永久浪费下标0的空间。 - 入栈顺序不能反：必须先移动top再赋值，否则会覆盖原有的栈顶数据。
- 扩容条件要对应：满栈判断是
top == capacity - 1，不是top == capacity。
四、两种 top 约定核心对比
两套写法的所有差异，都来自「top的语义」这一个核心定义。我们整理成对照表，方便复习和做题：
| 操作项 | top 指向栈顶下一位（推荐版本） | top 指向栈顶元素（教材版本） |
|---|---|---|
| 初始化 | top = 0 | top = -1 |
| 空栈条件 | top == 0 | top == -1 |
| 有效元素个数 | 等于top | 等于top + 1 |
| 入栈顺序 | 先赋值a[top]=data，再top++ | 先top++，再赋值a[top]=data |
| 取栈顶 | a[top - 1] | a[top] |
| 出栈操作 | top-- | top-- |
| 满栈条件 | top == capacity | top == capacity - 1 |
再次强调：两套写法没有优劣之分，但绝对不能混用。比如初始化用top=0，取栈顶却写a[top]。
五、为什么更推荐 top 指向下一位置的写法？
两种实现都能正确运行，但更推荐top=0的版本，主要有三个原因：
- 契合「左闭右开」的通用思维有效区间
[0, top)是编程里非常经典的区间约定，和数组遍历、字符串、后续C++迭代器的设计思路完全统一，学习成本更低。 - 计算更直观，减少出错概率有效元素个数直接等于
top，不需要额外做 +1 计算；待插入位置天然就是a[top]，逻辑更顺。 - 对齐后续C++学习虽然C++的
std::stack是容器适配器，没有强制规定底层下标实现，但这种「尾后位置」的设计思路，和STL容器的底层逻辑高度一致。现在习惯这套写法，后面学C++容器时会非常顺畅。
六、思考：为什么要封装成函数？直接访问 st.top 不行吗？
很多初学者刚写的时候都会有疑问：
元素个数不就是top吗？直接写
st.top不行吗，干嘛还要多写一层StackSize(&st)？
这其实是一个非常重要的工程化思维转变：从「写出能跑的代码」到「设计可维护的结构」。封装的价值，主要体现在三点：
1. 隐藏实现细节，接口保持稳定
如果外部都通过StackSize()获取元素个数，那么无论我们底层换成top=0还是top=-1的实现，外部调用代码一行都不用改。 我们只需要修改函数内部的实现，就能完成底层逻辑的切换，这就是「接口不变，实现可替换」。
2. 保护数据结构，避免非法修改
如果结构体成员直接暴露，外部代码可以随意修改top的值，比如误写st.top = 100，会直接导致整个栈的结构错乱，排查起来非常麻烦。 通过函数封装，外部只能执行入栈、出栈这些合法操作，从根源上避免了非法修改，保证了数据结构的安全性。
3. 语义更清晰，代码可读性更高
看到StackSize(&st)，任何人都能立刻明白是「获取栈的元素个数」；但看到st.top，还要先回忆这个项目里的top是哪一种约定。 函数封装把「怎么算」的细节藏在了内部，调用者只需要关心「做什么」，代码的可读性和可维护性都会大幅提升。
C语言没有C++类的private访问权限，但通过「头文件声明接口 + 源文件实现细节」的方式，已经可以模拟出封装的效果。这种思维习惯，也是从C语言过渡到C++面向对象的重要铺垫。
七、测试验证
下面是完整的测试代码，可以验证所有接口的正确性。有意思的是，无论底层用哪一种top约定，这套测试代码都完全不用改——这正是接口封装的意义。
// test.c #include "Stack.h" #include <stdio.h> int main() { Stack st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); StackPush(&st, 5); // 第5个元素触发扩容 printf("size=%d\n", StackSize(&st)); printf("top=%d\n", StackTop(&st)); StackPop(&st); printf("pop之后top=%d\n", StackTop(&st)); if (StackEmpty(&st)) { printf("栈为空\n"); } else { printf("栈不为空\n"); } while (!StackEmpty(&st)) { StackPop(&st); } StackDestroy(&st); printf("销毁栈成功\n"); return 0; }本篇全部示例代码已上传代码仓库，包含两套 top 实现源码、测试用例以及使用提示文档。 读者可以直接下载本地编译运行，对照博文加深对顺序栈接口封装与 top 两种语义的理解。
代码仓库
数据结构/8.15 栈的练习Stack · Luminous/Code_2026 - 码云 - 开源中国
八、复杂度分析
顺序栈的所有核心操作，时间复杂度都非常优秀：
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 入栈 Push | 均摊 O(1) | 绝大多数情况直接写入，仅扩容时需要搬迁数据，倍增扩容下均摊为O(1) |
| 出栈 Pop | O(1) | 仅修改top的值，无额外开销 |
| 获取栈顶 Top | O(1) | 直接按下标访问 |
| 判空 Empty | O(1) | 仅一次比较 |
| 获取大小 Size | O(1) | 直接返回top的值 |
这里的「均摊O(1)」和动态顺序表的扩容逻辑完全一致：虽然单次扩容开销很大，但扩容的次数非常少，把开销平摊到所有入栈操作上，平均每次操作的成本依然是常数级。
九、本篇总结
手写顺序栈的代码本身并不复杂，但里面藏着两个非常重要的认知点：
- 变量语义是边界问题的根源：很多人写栈容易出边界错误，本质不是代码写错了，而是没有先定义清楚
top到底代表什么。先定语义，再写代码，所有边界问题都会迎刃而解。 - 封装不是冗余，是工程化的基础：多写一层函数调用，不是多此一举，而是在隔离实现细节、保护数据安全、提升代码可维护性。这也是我们从写玩具代码到写工程代码的第一步。
理解了顺序栈的实现思路，再学队列就会非常轻松——队列同样是操作受限的线性表，只是换成了两端操作、先进先出的规则。