一.栈的概念及结构1.概念栈⼀种特殊的线性表其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶另⼀端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。压栈栈的插⼊操作叫做进栈/压栈/⼊栈⼊数据在栈顶。出栈栈的删除操作叫做出栈。出数据也在栈顶。2.结构栈底层结构选型栈的实现⼀般可以使⽤数组或者链表实现相对⽽⾔数组的结构实现更优⼀些。因为数组在尾上插⼊数据的代价⽐较⼩Stack的Push和Pop都说明他们遵循先进先出的原则二.栈的实现结构a.数组实现顺序栈数组实现栈时通常将数组的尾部作为栈顶因为尾部插入和删除数据的时间复杂度都是 O(1)效率很高。优点入栈和出栈操作简单高效时间复杂度均为 O(1);内存空间连续CPU 缓存命中率高访问速度快;不需要额外的指针域存储节点关系内存开销小;代码实现简单不容易出错。缺点需要预先分配固定大小的内存空间空间不够时需要扩容;扩容时涉及数据拷贝有一定的时间开销;扩容后可能造成内存浪费例如扩容到原来的 2 倍但实际只用了一小部分。b.链表实现链式栈1. 单链表实现如果要用单链表实现栈用头作栈顶头插和头删这样入栈和出栈的效率都是 O(1)。不适合用尾作栈顶因为尾插和尾删都需要遍历链表找到尾节点时间复杂度为 O(n)效率太低。2. 双向链表实现如果用尾作栈顶尾插和尾删使用双向链表更合适因为可以通过尾指针直接定位到尾部入栈和出栈的效率都是 O(1)。不过双向链表每个节点需要维护两个指针prev 和 next内存开销较大空间浪费较多实际应用价值并不高。a.栈的顺序存储结构以数组的起始位置作为栈底另一端作为栈顶并设置一个变量 top 来指示当前栈顶元素在数组中的下标位置。b.栈的链表存储结构左边进栈右边出栈链表的尾部作为栈底固定不变头部作为栈顶进栈和出栈都通过头插和头删完成时间复杂度均为 O(1)。这种情况下链表的头指针天然就是栈顶指针不需要额外定义 top 变量头指针和栈顶指针合为一体。三.栈的实现1.创建三个文件在实现栈之前首先需要创建以下三个文件test.c—— 主函数文件用于测试栈的各个接口功能是否正常Stack.c—— 栈接口函数的具体实现文件包含入栈、出栈、获取栈顶元素等操作Stack.h—— 栈的头文件包含栈的类型定义、接口函数声明以及所需引用的头文件说明采用这种模块化的文件组织方式可以将栈的实现细节与测试代码分离提高代码的可读性和可维护性也便于后续复用和扩展。其中 Stack.h 负责声明Stack.c 负责实现test.c 负责验证。2.Stack.h头文件代码下面是动态增长的栈的结构定义这种实现在实际工程中更为常用。#pragma once #include stdio.h #include assert.h // assert #include stdlib.h // malloc, realloc, free #include stdbool.h // bool 类型 // 支持动态增长的栈 typedef int STDataType; // 类型重命名栈中元素类型先假设为 int typedef struct Stack { STDataType* a; // 指向动态开辟的数组 int top; // 记录栈顶位置 int capacity; // 栈的容量大小 } Stack; // 初始化栈 void StackInit(Stack* ps); // 销毁栈 void StackDestroy(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);四.Stack.c 中各个接口函数的实现1.栈的初始化// 初始化栈 void StackInit(Stack* ps) { assert(ps); // 确保传入的指针非空 ps-a NULL; // 初始时动态数组为空 // 思路一本教程采用 ps-top 0; // top 指向栈顶数据的下一个位置即栈顶元素下标 1 // 思路二备选 // ps-top -1; // top 指向栈顶数据即当前栈顶元素的下标 ps-capacity 0; // 初始容量为 0 }思路一top 初始化为 0这种方式下top 指向栈顶元素的下一个位置也就是栈顶元素的下标加一。当栈为空时top 的值为 0。入栈操作时先在 top 位置放入数据然后 top 自增 1。这样设计的好处是top 的值始终等于栈中有效元素的个数判断栈空和获取元素个数都非常方便只需要检查 top 是否为 0 即可。思路二top 初始化为 -1这种方式下top 指向栈顶元素本身也就是当前栈顶元素在数组中的下标。当栈为空时top 的值为 -1。入栈操作时需要先将 top 自增 1然后在 top 位置放入数据。这种设计在逻辑上也说得通但判断栈空时需要检查 top 是否等于 -1稍微多了一步判断。两种思路都是可行的区别仅在于 top 的初始值不同以及入栈和出栈时操作的顺序稍有差异。我采用思路一因为 top 的值直接等于元素个数代码写起来更加直观出栈时只需要先让 top 自减 1再取出数据即可逻辑上更清晰。思路二有图解如下2.栈的销毁// 销毁栈 void StackDestroy(Stack* ps) { assert(ps); // 断言防止传入空指针 if (ps-a) // 如果栈中的数组不为空就释放掉 { free(ps-a); } ps-a NULL; // 释放完置空防止变成野指针 ps-top 0; // 栈顶归零 ps-capacity 0; // 容量归零 }解析这个函数是用来销毁栈的把之前动态开辟的空间还给操作系统。首先用 assert 断言一下传入的指针不能为空保证程序安全。然后用 if 判断一下 ps-a 是否为空如果不为空就用 free 释放掉这块动态开辟的数组空间。释放完之后记得把 ps-a 置成 NULL不然它就变成野指针了很危险。同时把 top 和 capacity 也归零这样栈就恢复到了初始状态。简单来说就是谁分配谁释放释放完记得清理干净防止内存泄漏和野指针问题。3.入栈// 入栈 void StackPush(Stack* ps, STDataType x) { assert(ps); // 断言防止传入空指针 // 检查栈空间是否满了如果满了就需要扩容 if (ps-top ps-capacity) { // 计算新容量如果原容量为0则分配4个空间否则扩容为原来的2倍 int newCapacity (ps-capacity 0) ? 4 : (ps-capacity) * 2; // 用realloc重新开辟空间 STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newCapacity); // 检查realloc是否成功 if (tmp NULL) { printf(realloc fail\n); exit(-1); // 扩容失败程序退出 } ps-a tmp; // 让a指向新开辟的空间 ps-capacity newCapacity; // 更新容量 } // 放入元素 ps-a[ps-top] x; // 在栈顶位置放入新元素 ps-top; // 栈顶指针后移一位 }解析这个函数是实现入栈操作的就是在栈顶放入一个新元素。首先要断言一下 ps 不为空。然后检查一下栈空间够不够用判断条件是 ps-top ps-capacity。如果 top 等于 capacity说明栈已经满了需要扩容。扩容的时候先算一下新容量如果原容量是 0就先给 4 个空间不然就扩大到原来的 2 倍。然后用 realloc 去申请新空间申请完要检查一下是否成功失败了就打印错误信息然后退出程序。如果成功了就让 ps-a 指向这块新空间同时更新 capacity。空间搞定之后就可以放数据了在 ps-a[ps-top] 这个位置放入 x然后把 top 加一这样就完成了一次入栈操作。整个过程其实就是三步检查空间够不够 -- 不够就扩容 -- 放数据并移动 top。4.出栈// 出栈 void StackPop(Stack* ps) { assert(ps); // 断言防止传入空指针 assert(!StackEmpty(ps)); // 断言确保栈不为空不能对空栈进行出栈操作 ps-top--; // 栈顶指针减一逻辑上删除了栈顶元素 }解析出栈操作就是把栈顶元素删除。实现起来很简单只需要让 top 减一就行了。这里用了两个断言一个是保证传入的指针不为空另一个是调用 StackEmpty 函数检查栈是否为空。如果栈是空的就不能执行出栈操作否则 top 就会变成负数程序就出问题了。其实出栈并不是真的把数据清掉只是把 top 往前面移了一位。下次入栈的时候新数据会直接覆盖掉原来的位置所以不用特意去清空数据。5.获取栈顶元素// 获取栈顶元素 STDataType StackTop(Stack* ps) { assert(ps); // 断言防止传入空指针 assert(!StackEmpty(ps)); // 断言确保栈不为空 return ps-a[ps-top - 1]; // 返回栈顶元素 }解析这个函数是获取栈顶元素的值但不是删除它。因为 top 指向的是栈顶元素的下一个位置所以栈顶元素的下标是 top - 1。直接返回 ps-a[ps-top - 1] 就行了。也要用断言保证栈不为空否则访问越界就危险了。6.获取栈中有效元素个数// 获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps); // 断言防止传入空指针 return ps-top; // 直接返回 top 就是元素个数 }解析这个就很简单了直接返回 top 就行了。因为采用的是 top 初始化为 0 的思路top 的值正好等于栈中有效元素的个数。所以获取元素个数直接 return ps-top 就搞定了。7.检测栈是否为空// 检测栈是否为空如果为空返回 true非零值如果不为空返回 false0 bool StackEmpty(Stack* ps) { assert(ps); // 断言防止传入空指针 // 写法一推荐 return ps-top 0; // top 为 0 表示栈空直接返回比较结果 // 写法二不推荐过于冗余 /*if (ps-top 0) { return true; } else { return false; }*/ }解析这个函数用来判断栈是不是空的。因为用的是 top 初始化为 0 的思路所以判断栈空很简单就看 top 是不是等于 0。如果 top 等于 0说明栈里没有元素是空的如果 top 大于 0说明栈里有元素。写法一直接用return ps-top 0;返回比较结果简洁明了推荐用这种写法。写法二用 if-else 判断再返回 true 或 false虽然逻辑上没问题但代码太冗余了完全没必要这么写。这个函数一般配合 assert 使用在出栈或者获取栈顶元素之前先用它来断言一下栈不为空防止程序出错。这里大家注意一下 如果编译器支持 C99 标准可以用bool类型需要包含stdbool.h头文件如果不支持可以用int类型返回 0 表示假非 0 表示真。五.代码整合Stack.h#pragma once #include stdio.h #include assert.h // assert #include stdlib.h // malloc、realloc、free #include stdbool.h // bool 类型 // 支持动态增长的栈 typedef int STDataType; // 类型重命名栈中元素类型先假设为 int typedef struct Stack { STDataType* a; // 指向动态开辟的数组 int top; // 记录栈顶位置指向栈顶元素的下一个位置 int capacity; // 栈的容量大小 } Stack; // 初始化栈 void StackInit(Stack* ps); // 销毁栈 void StackDestroy(Stack* ps); // 入栈 void StackPush(Stack* ps, STDataType x); // 出栈 void StackPop(Stack* ps); // 获取栈顶元素 STDataType StackTop(Stack* ps); // 获取栈中有效元素个数 int StackSize(Stack* ps); // 检测栈是否为空如果为空返回 true如果不为空返回 false bool StackEmpty(Stack* ps);Stack.c#include Stack.h // 1、初始化栈 void StackInit(Stack* ps) { assert(ps); // 防止传入空指针 ps-a NULL; // 初始时动态数组为空 ps-top 0; // top 指向栈顶元素的下一个位置 ps-capacity 0; // 初始容量为 0 } // 2、销毁栈 void StackDestroy(Stack* ps) { assert(ps); // 防止传入空指针 if (ps-a) // 如果动态数组不为空就释放掉 { free(ps-a); } ps-a NULL; // 释放完置空防止野指针 ps-top 0; // 栈顶归零 ps-capacity 0; // 容量归零 } // 3、入栈 void StackPush(Stack* ps, STDataType x) { assert(ps); // 防止传入空指针 // 检查栈空间是否满了如果满了就需要扩容 if (ps-top ps-capacity) { // 计算新容量如果原容量为 0则分配 4 个空间否则扩容为原来的 2 倍 int newCapacity (ps-capacity 0) ? 4 : (ps-capacity) * 2; // 用 realloc 重新开辟空间 STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newCapacity); // 检查 realloc 是否成功 if (tmp NULL) { printf(realloc fail\n); exit(-1); // 扩容失败程序退出 } ps-a tmp; // 让 a 指向新开辟的空间 ps-capacity newCapacity; // 更新容量 } // 放入元素 ps-a[ps-top] x; // 在栈顶位置放入新元素 ps-top; // 栈顶指针后移一位 } // 4、出栈 void StackPop(Stack* ps) { assert(ps); // 防止传入空指针 assert(!StackEmpty(ps)); // 确保栈不为空不能对空栈进行出栈操作 ps-top--; // 栈顶指针减一逻辑上删除了栈顶元素 } // 5、获取栈顶元素 STDataType StackTop(Stack* ps) { assert(ps); // 防止传入空指针 assert(!StackEmpty(ps)); // 确保栈不为空 return ps-a[ps-top - 1]; // 返回栈顶元素 } // 6、获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps); // 防止传入空指针 return ps-top; // 直接返回 top 就是元素个数 } // 7、检测栈是否为空 bool StackEmpty(Stack* ps) { assert(ps); // 防止传入空指针 return ps-top 0; // top 为 0 表示栈空 }test.c#include Stack.h // 测试1基本入栈出栈功能 void TestStack1() { Stack st; StackInit(st); // 入栈5个元素 printf(入栈1 2 3 4 5\n); StackPush(st, 1); StackPush(st, 2); StackPush(st, 3); StackPush(st, 4); StackPush(st, 5); printf(当前栈中元素个数%d\n, StackSize(st)); // 依次出栈并打印 printf(出栈顺序); while (!StackEmpty(st)) { printf(%d , StackTop(st)); StackPop(st); } printf(\n); printf(出栈后元素个数%d\n, StackSize(st)); printf(\n); StackDestroy(st); } // 测试2扩容功能测试 void TestStack2() { Stack st; StackInit(st); printf(初始容量%d\n, st.capacity); // 连续入栈6个元素观察扩容过程 for (int i 1; i 6; i) { StackPush(st, i * 10); printf(入栈 %d 后top %dcapacity %d\n, i * 10, st.top, st.capacity); } printf(\n); StackDestroy(st); } // 测试3多栈独立运行测试 void TestStack3() { Stack st1, st2; StackInit(st1); StackInit(st2); // st1 入栈 1 2 3 StackPush(st1, 1); StackPush(st1, 2); StackPush(st1, 3); // st2 入栈 10 20 30 40 StackPush(st2, 10); StackPush(st2, 20); StackPush(st2, 30); StackPush(st2, 40); printf(st1 元素个数%d\n, StackSize(st1)); printf(st2 元素个数%d\n, StackSize(st2)); printf(st1 出栈); while (!StackEmpty(st1)) { printf(%d , StackTop(st1)); StackPop(st1); } printf(\n); printf(st2 出栈); while (!StackEmpty(st2)) { printf(%d , StackTop(st2)); StackPop(st2); } printf(\n); printf(\n); StackDestroy(st1); StackDestroy(st2); } // 测试4边界安全检查测试 void TestStack4() { Stack st; StackInit(st); // 对空栈执行出栈操作会触发断言报错 // 下面这行代码如果取消注释程序会报错退出 // StackPop(st); // Assertion !StackEmpty(ps) failed. // 对空栈获取栈顶元素也会触发断言报错 // StackTop(st); // Assertion !StackEmpty(ps) failed. StackDestroy(st); } int main() { TestStack1(); // 测试入栈出栈 TestStack2(); // 测试扩容 TestStack3(); // 测试多栈 TestStack4(); // 测试边界检查 return 0; }六.代码测试1.测试入栈出栈2.测试扩容3.测试多栈4.测试边界问题现在是我没有触发操作代码成功执行接下来我触发错误共有两种