写在前面上一篇我们从内存布局、操作效率、CPU缓存三个维度完整对比了顺序表与链表的底层差异并在最后引出了一种操作受限的线性表——栈。栈的逻辑规则非常简单所有插入、删除操作只能在栈顶完成遵循后进先出LIFO的原则。但真正动手用C语言实现时很多初学者都会卡在一个经典问题上top到底应该指向哪里常见的实现约定有两种top指向栈顶元素的下一个位置初始化为 0top直接指向当前栈顶元素初始化为 -1两种写法都能正确实现栈没有绝对的对错核心原则只有一个一旦确定了 top 的语义初始化、入栈、出栈、判空、取栈顶等所有操作必须严格遵循同一套规则绝对不能混用。本文先完整实现我们日常使用的top0版本对齐后续C学习的思维习惯再补充常见的top-1经典写法最后聊一个很值得思考的问题明明可以直接访问结构体成员为什么还要专门封装StackPush、StackSize这些函数本篇代码仓库位置数据结构/8.15 栈的练习Stack · Luminous/Code_2026 - 码云 - 开源中国一、顺序栈的底层结构设计顺序栈的本质就是动态数组 栈顶标记底层复用了动态顺序表的扩容逻辑只是限制了所有操作只能在尾部进行。1.1 头文件结构体与接口定义我们先定义栈的结构体和对外接口命名和功能都对齐后续C的学习习惯同时明确判空规则栈为空返回非零值不为空返回0。// Stack.h #pragma once #includeassert.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 | | ↑ toptop4既代表下一个待插入的位置也等于当前有效元素的总数。2.2 完整实现代码以下是完整的Stack.c实现严格遵循上面的约定// Stack.c #includeStack.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-1top指向的是栈顶元素的下一个位置不是有效元素本身。真正的栈顶元素是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 | ↑ toptop3就是栈顶元素的下标有效元素总数是 314。3.2 完整实现代码头文件完全不需要修改只需要替换Stack.c的内部实现对外接口保持完全一致// Stack_top_minus_one.c #includeStack.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 0top -1空栈条件top 0top -1有效元素个数等于top等于top 1入栈顺序先赋值a[top]data再top先top再赋值a[top]data取栈顶a[top - 1]a[top]出栈操作top--top--满栈条件top capacitytop capacity - 1再次强调两套写法没有优劣之分但绝对不能混用。比如初始化用top0取栈顶却写a[top]。五、为什么更推荐 top 指向下一位置的写法两种实现都能正确运行但更推荐top0的版本主要有三个原因契合「左闭右开」的通用思维有效区间[0, top)是编程里非常经典的区间约定和数组遍历、字符串、后续C迭代器的设计思路完全统一学习成本更低。计算更直观减少出错概率有效元素个数直接等于top不需要额外做 1 计算待插入位置天然就是a[top]逻辑更顺。对齐后续C学习虽然C的std::stack是容器适配器没有强制规定底层下标实现但这种「尾后位置」的设计思路和STL容器的底层逻辑高度一致。现在习惯这套写法后面学C容器时会非常顺畅。六、思考为什么要封装成函数直接访问 st.top 不行吗很多初学者刚写的时候都会有疑问元素个数不就是top吗直接写st.top不行吗干嘛还要多写一层StackSize(st)这其实是一个非常重要的工程化思维转变从「写出能跑的代码」到「设计可维护的结构」。封装的价值主要体现在三点1. 隐藏实现细节接口保持稳定如果外部都通过StackSize()获取元素个数那么无论我们底层换成top0还是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)出栈 PopO(1)仅修改top的值无额外开销获取栈顶 TopO(1)直接按下标访问判空 EmptyO(1)仅一次比较获取大小 SizeO(1)直接返回top的值这里的「均摊O(1)」和动态顺序表的扩容逻辑完全一致虽然单次扩容开销很大但扩容的次数非常少把开销平摊到所有入栈操作上平均每次操作的成本依然是常数级。九、本篇总结手写顺序栈的代码本身并不复杂但里面藏着两个非常重要的认知点变量语义是边界问题的根源很多人写栈容易出边界错误本质不是代码写错了而是没有先定义清楚top到底代表什么。先定语义再写代码所有边界问题都会迎刃而解。封装不是冗余是工程化的基础多写一层函数调用不是多此一举而是在隔离实现细节、保护数据安全、提升代码可维护性。这也是我们从写玩具代码到写工程代码的第一步。理解了顺序栈的实现思路再学队列就会非常轻松——队列同样是操作受限的线性表只是换成了两端操作、先进先出的规则。