摘要栈是一种受限的线性表只允许在栈顶插入和删除元素遵循后进先出LIFO原则。本文从栈的概念与结构讲起对比数组与链表两种底层实现随后用 C 语言完整实现一个基于动态数组的栈含初始化、销毁、入栈、出栈、取栈顶、判空、求个数七个接口并给出可运行的测试用例。最后总结各接口的时间复杂度除扩容搬移外均为O ( 1 ) O(1)O(1)与易错点清单帮助读者一次写对。文章目录1. 栈的概念与结构1.1 概念与结构1.2 底层结构选型数组还是链表2. 栈的实现2.1 文件规划2.2 头文件 Stack.h2.3 初始化与销毁2.4 入栈2.5 出栈2.6 取栈顶元素2.7 有效元素个数与判空2.8 测试 test.c3. 各接口复杂度与易错点3.1 各接口时间复杂度3.2 易错点清单4. 小结1. 栈的概念与结构1.1 概念与结构前面几篇文章把线性表的三种「自由形态」都实现了一遍顺序表、单链表、带头双向循环链表——它们的共同点是插入删除可以发生在任意位置。这篇换一个思路给线性表加上限制把「只能在一端操作」这条规则写死就得到了一种接口极少、但用途极广的结构——栈。栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作进行数据插入和删除操作的一端称为栈顶另一端称为栈底栈中的数据元素遵守**后进先出 LIFOLast In First Out**的原则压栈栈的插入操作叫做进栈 / 压栈 / 入栈入数据在栈顶出栈栈的删除操作叫做出栈出数据也在栈顶。看图就能抓住关键进栈是「从栈顶放进去」出栈也是「从栈顶拿走」。所以最早进来的元素沉在最底下栈底要等压在它上面的元素全部出栈之后才能被访问——这就是后进先出。生活中的栈弹夹、食堂里一摞盘子都是栈最后放进去的最先被拿走。想拿最底下那个就必须先把上面的一个个取走——这正是「只能访问栈顶」的直观体现。把栈对外的操作抽成接口一共只有五个操作语义作用位置入栈压栈STPush在栈顶插入一个元素栈顶出栈STPop删除栈顶元素栈顶取栈顶STTop只读取栈顶元素不删除栈顶判空STEmpty栈里是否还有元素—元素个数STSize当前有效元素个数—注意栈只能访问栈顶栈不能遍历、也不支持下标的随机访问。想拿到中间的元素唯一的办法是不断出栈把上面的一层层取掉。正是这个限制让栈天然适合表达「就近匹配」「原路返回」这类问题——它接口最少却出现在大量算法里例如括号匹配、表达式求值中缀转后缀、深度优先搜索DFS以及函数调用与递归背后的函数栈帧。1.2 底层结构选型数组还是链表栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些——因为数组在尾上插入数据的代价比较小对比项数组实现链表实现栈顶在哪数组尾部下标top - 1链表头部入栈 / 出栈尾插 / 尾删均摊O ( 1 ) O(1)O(1)头插 / 头删O ( 1 ) O(1)O(1)扩容需要realloc 搬移不需要用多少申请多少每个元素的额外开销无一个next指针内存局部性连续存储缓存友好节点分散要跳来跳去实现难度简单一个动态数组 一个下标稍复杂要管理节点两种实现的入栈、出栈都是O ( 1 ) O(1)O(1)所以差别不在复杂度而在额外开销和实现难度上链表每个元素要多存一个指针、还要动态申请节点数组只需要一个动态数组加一个下标顺序存储对缓存也更友好。所以本篇用数组实现栈。2. 栈的实现2.1 文件规划和前面几篇一样继续使用三文件结构Stack.h放类型定义与函数声明Stack.c放具体实现test.c用来验证接口。2.2 头文件 Stack.h//Stack.h#pragmaonce#define_CRT_SECURE_NO_WARNINGS// 关掉 VS 对 printf 等函数的「不安全」警告#includestdio.h#includestdlib.h#includeassert.h#includestdbool.htypedefintSTDataType;typedefstructStack{STDataType*arr;// 动态数组栈底在下标 0栈顶在 top-1inttop;// 栈顶的下一个空位下标也就是有效元素个数intcapacity;// 当前容量}ST;// 初始化栈voidSTInit(ST*ps);// 销毁栈voidSTDestroy(ST*ps);// 入栈voidSTPush(ST*ps,STDataType x);// 出栈voidSTPop(ST*ps);// 取栈顶元素STDataTypeSTTop(ST*ps);// 获取栈中有效元素个数intSTSize(ST*ps);// 栈是否为空boolSTEmpty(ST*ps);三个成员各有分工成员含义arr指向动态数组栈底元素固定在下标 0top栈顶的下一个空位下标恰好也等于有效元素个数capacity当前容量用来判断是否需要扩容top的两种约定选一种并从一而终约定 A本篇采用top表示「下一个可插入位置」——空栈时top 0栈顶元素是arr[top - 1]top同时就是元素个数约定 Btop表示「栈顶元素的下标」——空栈时top -1栈顶元素是arr[top]元素个数要写成top 1。两种写法都对但绝不能混用用约定 A 的top去写约定 B 的判空条件空栈就永远判不出来。2.3 初始化与销毁// 初始化栈voidSTInit(ST*ps){assert(ps);ps-arrNULL;ps-topps-capacity0;}初始化只是把三个成员清零数组还没申请、top为 0空栈、容量为 0。真正的空间留到第一次入栈时再申请——与顺序表「按需申请」的思路一致。// 销毁栈voidSTDestroy(ST*ps){assert(ps);free(ps-arr);ps-arrNULL;ps-topps-capacity0;}free之后把三个成员清零不只是好习惯这样即使不小心调用了第二次销毁free(NULL)也不会有事否则就是重复释放。2.4 入栈// 入栈voidSTPush(ST*ps,STDataType x){assert(ps);// 满了就扩容首次开 4 个之后每次翻倍if(ps-topps-capacity){intnewCapacityps-capacity0?4:2*ps-capacity;STDataType*newArr(STDataType*)realloc(ps-arr,newCapacity*sizeof(STDataType));if(newArrNULL){perror(realloc failed);exit(1);}ps-arrnewArr;ps-capacitynewCapacity;}ps-arr[ps-top]x;}入栈只有两个动作空间不够就扩容然后把数据写到top位置、并让top后移一位arr[top] x。扩容这一段有三个细节值得说清楚初始容量不能是 0capacity 0时用2 * capacity永远是 0realloc(ptr, 0)申请不到任何空间所以首次要单独给一个值这里是 4必须用临时指针接realloc的返回值如果直接写ps-arr realloc(ps-arr, ...)一旦失败realloc返回NULL原来的空间地址就被覆盖丢了——既泄漏又崩溃。用newArr先接住、判断成功后再回填才是最稳的写法扩容是「偶尔才发生」的容量按 0 → 4 → 8 → 16 翻倍扩容前后的对比见 2.2 节的图。连续入栈时绝大部分入栈都只做一次赋值偶发的O ( N ) O(N)O(N)搬移被摊到每次入栈上平均下来仍是常数级——这就是下面要说的均摊amortizedO ( 1 ) O(1)O(1)。2.5 出栈// 出栈voidSTPop(ST*ps){assert(!STEmpty(ps));ps-top--;}出栈只有一行top--。出栈并没有「删掉」数据top--只是把「栈顶」往回退了一格那个元素其实还躺在数组里只不过不再属于这个栈了下一次入栈会直接把它覆盖掉。这也是出栈能是O ( 1 ) O(1)O(1)的原因——不需要搬移任何数据。空栈出栈属于逻辑错误所以用assert(!STEmpty(ps))拦一道而不是让top变成负数。2.6 取栈顶元素// 取栈顶元素STDataTypeSTTop(ST*ps){assert(!STEmpty(ps));returnps-arr[ps-top-1];}因为top是「下一个空位」约定 A栈顶元素在下标top - 1。取栈顶只是读取不改变栈的状态——它最典型的用法是和出栈配合先用STTop看看栈顶是谁再决定要不要STPop。空栈调用STTop会去读arr[-1]下标-1已经跑到数组外面了属于未定义行为可能读到随机值也可能直接崩溃。所以这里和STPop一样先断言判空如果某个场景下空栈是「合法状态」那就不要用断言改成返回一个明确的错误值或者用一个bool输出参数把「有没有取到」告诉调用方。2.7 有效元素个数与判空// 获取栈中有效元素个数intSTSize(ST*ps){assert(ps);returnps-top;}// 栈是否为空boolSTEmpty(ST*ps){assert(ps);returnps-top0;}两个函数都只有一行但它们是「约定 A」的直接结果top既是下一个空位的下标也恰好等于元素个数所以STSize直接返回top判空就是top 0都不需要额外再维护一个size成员。2.8 测试 test.c//test.c#includeStack.hintmain(){ST st;STInit(st);// 1. 空栈printf( 新建一个栈 \n);printf(栈是否为空%s\n,STEmpty(st)?true:false);printf(有效元素个数%d\n,STSize(st));// 2. 依次入栈 1 2 3printf(\n 依次入栈 1 2 3 \n);STPush(st,1);STPush(st,2);STPush(st,3);printf(栈顶元素%d有效元素个数%d当前容量%d\n,STTop(st),STSize(st),st.capacity);// 3. 再入栈 4 5第 5 次入栈时容量不够触发扩容printf(\n 再入栈 4 5触发扩容\n);STPush(st,4);STPush(st,5);printf(栈顶元素%d有效元素个数%d当前容量%d\n,STTop(st),STSize(st),st.capacity);// 4. 连续出栈两次printf(\n 连续出栈两次 \n);STPop(st);STPop(st);printf(栈顶元素%d有效元素个数%d\n,STTop(st),STSize(st));// 5. 一直出栈直到空printf(\n 出栈直到空 \n);while(!STEmpty(st)){printf(%d ,STTop(st));STPop(st);}printf(\n栈是否为空%s\n,STEmpty(st)?true:false);// 6. 销毁STDestroy(st);return0;}预期输出 新建一个栈 栈是否为空true 有效元素个数0 依次入栈 1 2 3 栈顶元素3有效元素个数3当前容量4 再入栈 4 5触发扩容 栈顶元素5有效元素个数5当前容量8 连续出栈两次 栈顶元素3有效元素个数3 出栈直到空 3 2 1 栈是否为空true输出里有三处值得对照第一次入栈之后「当前容量」从 0 变成了4——这是首次扩容第 5 次入栈数据 5时容量从 4 变成8——这是第二次扩容「出栈直到空」打印出来的顺序是3 2 1和入栈顺序完全相反——这是后进先出最直观的体现。测试里为什么能直接读st.capacity为了直观看到扩容测试代码直接访问了结构体成员。这是「为了讲清原理」的临时做法正经的封装下外部只应该通过STPush/STTop这些接口来操作栈不直接碰成员。3. 各接口复杂度与易错点3.1 各接口时间复杂度接口关键动作时间复杂度STInit三个成员清零O ( 1 ) O(1)O(1)STDestroy释放动态数组O ( 1 ) O(1)O(1)STPush写一个元素只有满了才扩容并搬移均摊O ( 1 ) O(1)O(1)单次最坏O ( N ) O(N)O(N)STPoptop--O ( 1 ) O(1)O(1)STTop读arr[top - 1]O ( 1 ) O(1)O(1)STSize返回topO ( 1 ) O(1)O(1)STEmpty判断top 0O ( 1 ) O(1)O(1)一句话记住栈除了偶尔的扩容搬移栈的所有接口都是O ( 1 ) O(1)O(1)。它唯一的「慢」是功能上付出的代价只能访问栈顶想碰中间的元素就得把上面的元素全部出栈。3.2 易错点清单top的约定要前后一致本篇top 下一个空位的下标空栈top 0栈顶是arr[top - 1]若改成「top指向栈顶元素」判空要写top -1、元素个数要写top 1混用必出错。出栈 / 取栈顶前必须判空空栈STTop会读arr[-1]越界、未定义行为空栈STPop会让top变成负数本篇用assert(!STEmpty(ps))拦住。扩容必须用临时指针接realloc的返回值直接覆盖ps-arr会在申请失败时丢掉原空间内存泄漏随后崩溃。初始容量不能是 0capacity 0时要给一个非零初值本篇是 4否则2 * capacity永远是 0。出栈不等于删数据只是top--旧值仍在数组里下次入栈会被覆盖不要依赖「出栈后那个位置就是空的」。free之后把成员清零否则第二次调用STDestroy就是重复释放double free。断言是接口契约不是取巧STInit、STDestroy、STPush、STSize、STEmpty断言psSTPop、STTop断言非空——把「调用者不该这么做」的情况拦在调试期。换数据类型只需改typedef把STDataType改成char/double即可但printf的格式串%d→%c/%f也要跟着改。4. 小结栈是一种受限的线性表只允许在栈顶插入和删除元素后进先出LIFO。栈的接口极少——入栈、出栈、取栈顶、判空、求个数——只能访问栈顶不支持遍历和随机访问也正因如此它天然适配括号匹配、表达式求值、DFS、函数栈帧这些场景。数组实现更优栈顶就是数组尾部入栈 / 出栈都是均摊O ( 1 ) O(1)O(1)没有额外的指针开销实现也最简单。实现的核心只有三件事一个动态数组arrcapacity、一个下标top既是下一个空位也是元素个数、一套扩容策略首次 4之后翻倍。整个栈里唯一「不是O ( 1 ) O(1)O(1)」的动作就是扩容搬移而它被均摊到了每一次入栈上。 
长河君 · 2026/10/18 7:35:26 · 阅读 1.2k 【数据结构初阶】栈的概念及其实现
摘要栈是一种受限的线性表只允许在栈顶插入和删除元素遵循后进先出LIFO原则。本文从栈的概念与结构讲起对比数组与链表两种底层实现随后用 C 语言完整实现一个基于动态数组的栈含初始化、销毁、入栈、出栈、取栈顶、判空、求个数七个接口并给出可运行的测试用例。最后总结各接口的时间复杂度除扩容搬移外均为O ( 1 ) O(1)O(1)与易错点清单帮助读者一次写对。文章目录1. 栈的概念与结构1.1 概念与结构1.2 底层结构选型数组还是链表2. 栈的实现2.1 文件规划2.2 头文件 Stack.h2.3 初始化与销毁2.4 入栈2.5 出栈2.6 取栈顶元素2.7 有效元素个数与判空2.8 测试 test.c3. 各接口复杂度与易错点3.1 各接口时间复杂度3.2 易错点清单4. 小结1. 栈的概念与结构1.1 概念与结构前面几篇文章把线性表的三种「自由形态」都实现了一遍顺序表、单链表、带头双向循环链表——它们的共同点是插入删除可以发生在任意位置。这篇换一个思路给线性表加上限制把「只能在一端操作」这条规则写死就得到了一种接口极少、但用途极广的结构——栈。栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作进行数据插入和删除操作的一端称为栈顶另一端称为栈底栈中的数据元素遵守**后进先出 LIFOLast In First Out**的原则压栈栈的插入操作叫做进栈 / 压栈 / 入栈入数据在栈顶出栈栈的删除操作叫做出栈出数据也在栈顶。看图就能抓住关键进栈是「从栈顶放进去」出栈也是「从栈顶拿走」。所以最早进来的元素沉在最底下栈底要等压在它上面的元素全部出栈之后才能被访问——这就是后进先出。生活中的栈弹夹、食堂里一摞盘子都是栈最后放进去的最先被拿走。想拿最底下那个就必须先把上面的一个个取走——这正是「只能访问栈顶」的直观体现。把栈对外的操作抽成接口一共只有五个操作语义作用位置入栈压栈STPush在栈顶插入一个元素栈顶出栈STPop删除栈顶元素栈顶取栈顶STTop只读取栈顶元素不删除栈顶判空STEmpty栈里是否还有元素—元素个数STSize当前有效元素个数—注意栈只能访问栈顶栈不能遍历、也不支持下标的随机访问。想拿到中间的元素唯一的办法是不断出栈把上面的一层层取掉。正是这个限制让栈天然适合表达「就近匹配」「原路返回」这类问题——它接口最少却出现在大量算法里例如括号匹配、表达式求值中缀转后缀、深度优先搜索DFS以及函数调用与递归背后的函数栈帧。1.2 底层结构选型数组还是链表栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些——因为数组在尾上插入数据的代价比较小对比项数组实现链表实现栈顶在哪数组尾部下标top - 1链表头部入栈 / 出栈尾插 / 尾删均摊O ( 1 ) O(1)O(1)头插 / 头删O ( 1 ) O(1)O(1)扩容需要realloc 搬移不需要用多少申请多少每个元素的额外开销无一个next指针内存局部性连续存储缓存友好节点分散要跳来跳去实现难度简单一个动态数组 一个下标稍复杂要管理节点两种实现的入栈、出栈都是O ( 1 ) O(1)O(1)所以差别不在复杂度而在额外开销和实现难度上链表每个元素要多存一个指针、还要动态申请节点数组只需要一个动态数组加一个下标顺序存储对缓存也更友好。所以本篇用数组实现栈。2. 栈的实现2.1 文件规划和前面几篇一样继续使用三文件结构Stack.h放类型定义与函数声明Stack.c放具体实现test.c用来验证接口。2.2 头文件 Stack.h//Stack.h#pragmaonce#define_CRT_SECURE_NO_WARNINGS// 关掉 VS 对 printf 等函数的「不安全」警告#includestdio.h#includestdlib.h#includeassert.h#includestdbool.htypedefintSTDataType;typedefstructStack{STDataType*arr;// 动态数组栈底在下标 0栈顶在 top-1inttop;// 栈顶的下一个空位下标也就是有效元素个数intcapacity;// 当前容量}ST;// 初始化栈voidSTInit(ST*ps);// 销毁栈voidSTDestroy(ST*ps);// 入栈voidSTPush(ST*ps,STDataType x);// 出栈voidSTPop(ST*ps);// 取栈顶元素STDataTypeSTTop(ST*ps);// 获取栈中有效元素个数intSTSize(ST*ps);// 栈是否为空boolSTEmpty(ST*ps);三个成员各有分工成员含义arr指向动态数组栈底元素固定在下标 0top栈顶的下一个空位下标恰好也等于有效元素个数capacity当前容量用来判断是否需要扩容top的两种约定选一种并从一而终约定 A本篇采用top表示「下一个可插入位置」——空栈时top 0栈顶元素是arr[top - 1]top同时就是元素个数约定 Btop表示「栈顶元素的下标」——空栈时top -1栈顶元素是arr[top]元素个数要写成top 1。两种写法都对但绝不能混用用约定 A 的top去写约定 B 的判空条件空栈就永远判不出来。2.3 初始化与销毁// 初始化栈voidSTInit(ST*ps){assert(ps);ps-arrNULL;ps-topps-capacity0;}初始化只是把三个成员清零数组还没申请、top为 0空栈、容量为 0。真正的空间留到第一次入栈时再申请——与顺序表「按需申请」的思路一致。// 销毁栈voidSTDestroy(ST*ps){assert(ps);free(ps-arr);ps-arrNULL;ps-topps-capacity0;}free之后把三个成员清零不只是好习惯这样即使不小心调用了第二次销毁free(NULL)也不会有事否则就是重复释放。2.4 入栈// 入栈voidSTPush(ST*ps,STDataType x){assert(ps);// 满了就扩容首次开 4 个之后每次翻倍if(ps-topps-capacity){intnewCapacityps-capacity0?4:2*ps-capacity;STDataType*newArr(STDataType*)realloc(ps-arr,newCapacity*sizeof(STDataType));if(newArrNULL){perror(realloc failed);exit(1);}ps-arrnewArr;ps-capacitynewCapacity;}ps-arr[ps-top]x;}入栈只有两个动作空间不够就扩容然后把数据写到top位置、并让top后移一位arr[top] x。扩容这一段有三个细节值得说清楚初始容量不能是 0capacity 0时用2 * capacity永远是 0realloc(ptr, 0)申请不到任何空间所以首次要单独给一个值这里是 4必须用临时指针接realloc的返回值如果直接写ps-arr realloc(ps-arr, ...)一旦失败realloc返回NULL原来的空间地址就被覆盖丢了——既泄漏又崩溃。用newArr先接住、判断成功后再回填才是最稳的写法扩容是「偶尔才发生」的容量按 0 → 4 → 8 → 16 翻倍扩容前后的对比见 2.2 节的图。连续入栈时绝大部分入栈都只做一次赋值偶发的O ( N ) O(N)O(N)搬移被摊到每次入栈上平均下来仍是常数级——这就是下面要说的均摊amortizedO ( 1 ) O(1)O(1)。2.5 出栈// 出栈voidSTPop(ST*ps){assert(!STEmpty(ps));ps-top--;}出栈只有一行top--。出栈并没有「删掉」数据top--只是把「栈顶」往回退了一格那个元素其实还躺在数组里只不过不再属于这个栈了下一次入栈会直接把它覆盖掉。这也是出栈能是O ( 1 ) O(1)O(1)的原因——不需要搬移任何数据。空栈出栈属于逻辑错误所以用assert(!STEmpty(ps))拦一道而不是让top变成负数。2.6 取栈顶元素// 取栈顶元素STDataTypeSTTop(ST*ps){assert(!STEmpty(ps));returnps-arr[ps-top-1];}因为top是「下一个空位」约定 A栈顶元素在下标top - 1。取栈顶只是读取不改变栈的状态——它最典型的用法是和出栈配合先用STTop看看栈顶是谁再决定要不要STPop。空栈调用STTop会去读arr[-1]下标-1已经跑到数组外面了属于未定义行为可能读到随机值也可能直接崩溃。所以这里和STPop一样先断言判空如果某个场景下空栈是「合法状态」那就不要用断言改成返回一个明确的错误值或者用一个bool输出参数把「有没有取到」告诉调用方。2.7 有效元素个数与判空// 获取栈中有效元素个数intSTSize(ST*ps){assert(ps);returnps-top;}// 栈是否为空boolSTEmpty(ST*ps){assert(ps);returnps-top0;}两个函数都只有一行但它们是「约定 A」的直接结果top既是下一个空位的下标也恰好等于元素个数所以STSize直接返回top判空就是top 0都不需要额外再维护一个size成员。2.8 测试 test.c//test.c#includeStack.hintmain(){ST st;STInit(st);// 1. 空栈printf( 新建一个栈 \n);printf(栈是否为空%s\n,STEmpty(st)?true:false);printf(有效元素个数%d\n,STSize(st));// 2. 依次入栈 1 2 3printf(\n 依次入栈 1 2 3 \n);STPush(st,1);STPush(st,2);STPush(st,3);printf(栈顶元素%d有效元素个数%d当前容量%d\n,STTop(st),STSize(st),st.capacity);// 3. 再入栈 4 5第 5 次入栈时容量不够触发扩容printf(\n 再入栈 4 5触发扩容\n);STPush(st,4);STPush(st,5);printf(栈顶元素%d有效元素个数%d当前容量%d\n,STTop(st),STSize(st),st.capacity);// 4. 连续出栈两次printf(\n 连续出栈两次 \n);STPop(st);STPop(st);printf(栈顶元素%d有效元素个数%d\n,STTop(st),STSize(st));// 5. 一直出栈直到空printf(\n 出栈直到空 \n);while(!STEmpty(st)){printf(%d ,STTop(st));STPop(st);}printf(\n栈是否为空%s\n,STEmpty(st)?true:false);// 6. 销毁STDestroy(st);return0;}预期输出 新建一个栈 栈是否为空true 有效元素个数0 依次入栈 1 2 3 栈顶元素3有效元素个数3当前容量4 再入栈 4 5触发扩容 栈顶元素5有效元素个数5当前容量8 连续出栈两次 栈顶元素3有效元素个数3 出栈直到空 3 2 1 栈是否为空true输出里有三处值得对照第一次入栈之后「当前容量」从 0 变成了4——这是首次扩容第 5 次入栈数据 5时容量从 4 变成8——这是第二次扩容「出栈直到空」打印出来的顺序是3 2 1和入栈顺序完全相反——这是后进先出最直观的体现。测试里为什么能直接读st.capacity为了直观看到扩容测试代码直接访问了结构体成员。这是「为了讲清原理」的临时做法正经的封装下外部只应该通过STPush/STTop这些接口来操作栈不直接碰成员。3. 各接口复杂度与易错点3.1 各接口时间复杂度接口关键动作时间复杂度STInit三个成员清零O ( 1 ) O(1)O(1)STDestroy释放动态数组O ( 1 ) O(1)O(1)STPush写一个元素只有满了才扩容并搬移均摊O ( 1 ) O(1)O(1)单次最坏O ( N ) O(N)O(N)STPoptop--O ( 1 ) O(1)O(1)STTop读arr[top - 1]O ( 1 ) O(1)O(1)STSize返回topO ( 1 ) O(1)O(1)STEmpty判断top 0O ( 1 ) O(1)O(1)一句话记住栈除了偶尔的扩容搬移栈的所有接口都是O ( 1 ) O(1)O(1)。它唯一的「慢」是功能上付出的代价只能访问栈顶想碰中间的元素就得把上面的元素全部出栈。3.2 易错点清单top的约定要前后一致本篇top 下一个空位的下标空栈top 0栈顶是arr[top - 1]若改成「top指向栈顶元素」判空要写top -1、元素个数要写top 1混用必出错。出栈 / 取栈顶前必须判空空栈STTop会读arr[-1]越界、未定义行为空栈STPop会让top变成负数本篇用assert(!STEmpty(ps))拦住。扩容必须用临时指针接realloc的返回值直接覆盖ps-arr会在申请失败时丢掉原空间内存泄漏随后崩溃。初始容量不能是 0capacity 0时要给一个非零初值本篇是 4否则2 * capacity永远是 0。出栈不等于删数据只是top--旧值仍在数组里下次入栈会被覆盖不要依赖「出栈后那个位置就是空的」。free之后把成员清零否则第二次调用STDestroy就是重复释放double free。断言是接口契约不是取巧STInit、STDestroy、STPush、STSize、STEmpty断言psSTPop、STTop断言非空——把「调用者不该这么做」的情况拦在调试期。换数据类型只需改typedef把STDataType改成char/double即可但printf的格式串%d→%c/%f也要跟着改。4. 小结栈是一种受限的线性表只允许在栈顶插入和删除元素后进先出LIFO。栈的接口极少——入栈、出栈、取栈顶、判空、求个数——只能访问栈顶不支持遍历和随机访问也正因如此它天然适配括号匹配、表达式求值、DFS、函数栈帧这些场景。数组实现更优栈顶就是数组尾部入栈 / 出栈都是均摊O ( 1 ) O(1)O(1)没有额外的指针开销实现也最简单。实现的核心只有三件事一个动态数组arrcapacity、一个下标top既是下一个空位也是元素个数、一套扩容策略首次 4之后翻倍。整个栈里唯一「不是O ( 1 ) O(1)O(1)」的动作就是扩容搬移而它被均摊到了每一次入栈上。