【数据结构实战】C 语言实现静态顺序栈：从原理到完整可运行代码

栈(stack)是限定仅在表尾进行插入或删除操作的线性表。因此对栈来说表尾端有其特殊含义称为栈顶(top)相应地表头端称为栈底(bottom)。不含元素的空表称为空栈。假设 S(a1,a2,…,an)则称 a1为栈底元素an 为栈顶元素。栈中元素按 a1,a2,…an 的次序进栈退栈的第一个元素应为栈顶元素。换句话说栈的修改是按照后进先出的原则进行的。因此栈又称为后进先出(Last In First Out,LIFO)的线性表。栈是限制插入和删除操作只能在一个位置进行的表该位置是表的末端叫作栈顶(top)。对栈的基本操作有进栈(push)和出栈(Pop)前者相当于插入后者则是删除最后插入的元素。一、静态顺序栈核心概念静态顺序栈是用固定大小的数组存储栈元素通过「栈顶指针top」管理栈的状态核心规则top -1表示空栈初始化状态top 0栈中有元素top指向当前栈顶元素的下标top MAXSIZE - 1栈满无法继续入栈仅能在栈顶数组尾部执行入栈、出栈操作符合「后进先出」特性。二、 静态顺序栈的顺序结构实现 - 基础定义#define MAXSIZE 100 // 栈的最大容量 typedef int ElemType; // 元素类型可根据需求修改如char、float // 静态顺序栈结构体 typedef struct{ ElemType data[MAXSIZE]; // 存储栈元素的数组 int top; // 栈顶指针-1表示空栈 }Stack;三、 静态顺序栈 - 初始化固定数组版// 初始化栈将栈顶指针设为-1表示空栈 void initStack(Stack *s) { s-top -1; // 空栈约定top -1 }四、 静态顺序栈 - 判断栈是否为空// 判断栈是否为空空则返回1否则返回0 int isEmpty(Stack *s) { if (s-top -1) // 栈顶指针为-1说明栈空 { printf(空的\n); return 1; } else { return 0; } }五、静态顺序栈 - 进栈 / 压栈// 入栈操作将元素e压入栈s int push(Stack *s, ElemType e) { // 判断栈是否已满 if (s-top MAXSIZE - 1) { printf(满了\n); return 0; } s-top; // 栈顶上移 s-data[s-top] e; // 将元素存入栈顶 return 1; }顺序栈Sequential Stack的push进栈核心代码。 s-top; s-data[s-top] e;这两行代码顺序不能互换的根本原因在于为了保证栈顶指针top始终准确指向当前栈顶元素的存储位置。1.核心逻辑解析在顺序栈的实现中data数组是存储数据的容器而top是 “索引指针”。约定通常规定s-top指向的是当前栈顶元素的下标。初始状态栈空时s-top -1。2.为什么必须是s-top在前让我们拆解一下执行步骤第一步s-top假设当前栈内有元素1, 2, 3此时s-top 2指向元素 3。执行s-top后s-top变成了3。目的这一步是为了腾出下一个空位。第二步s-data[s-top] e此时s-top已经是3。执行赋值操作将新元素e存入了data[3]。结果赋值完成后top依然停留在新元素的位置符合 “top指向栈顶元素” 的约定。3.如果互换顺序会发生什么错误演示如果你先赋值、再自增第一步s-data[s-top] e当前s-top 2。程序把新元素e覆盖写入了data[2]这就把原本栈顶的元素3给覆盖掉了。第二步s-toptop变成了3。后果旧数据被覆盖丢失。此时top指向3但data[3]里根本没有存入正确的数据栈结构被破坏。所以s-top必须在前这是实现 “后进先出”LIFO逻辑的基础边界条件。六、静态顺序栈 - 出栈// 出栈操作将栈顶元素弹出存入*e中 ElemType pop(Stack *s, ElemType *e) { // 判断栈是否为空 if (s-top -1) { printf(空的\n); return 0; } *e s-data[s-top]; //把栈顶元素记录一下赋值到*e通过解引用的形式放到变量里面去 s-top--; // 栈顶下移逻辑删除 return 1; }1.代码含义解析// 第一步读取拷贝栈顶元素到 *e 中仅读取不删除 *e s-data[s-top]; // 第二步逻辑删除栈顶元素核心删除操作 s-top--;*e s-data[s-top];这行代码的作用是把栈顶元素的值拷贝到指针e所指向的内存地址中。我们可以拆成几部分理解s-top栈顶指针指向当前栈顶元素在数组data中的下标位置。s-data[s-top]访问顺序栈数组中栈顶位置的元素值。*e解引用指针e表示指针e所指向的变量。整个赋值语句将栈顶元素的值存入e指向的变量里方便函数调用者获取出栈的元素。*e s-data[s-top];这句话只做了 “读取 / 拷贝” 栈顶元素的操作完全没有删除任何东西—— 这是理解栈操作的关键细节。2.*e s-data[s-top];没有删除元素如果下次再有元素进栈会不会有影响结论完全不会有影响反而这正是顺序栈设计的精髓——“空间复用 指针控制”①先明确栈的 “删除” 不是物理删除是逻辑删除顺序栈是用数组实现的数组的内存一旦分配就不会凭空消失所以 “出栈删除元素” 并不是真的把数组里的数值删掉而是通过修改栈顶指针top来实现 “逻辑删除”—— 让程序认为 “这个位置的元素不再属于栈”。*e s-data[s-top]只拷贝值不删旧值对后续入栈无任何负面影响出栈后留在数组里的 “旧值 ”会被新入栈的元素直接覆盖新入栈的元素会直接覆盖旧值的位置数组空间被高效复用顺序栈的 “有效性” 由top指针控制而非数组里的数值旧值只要不在0~top范围内就等于 “不存在”。程序只认top指针指向的范围旧值就算存在也不会被访问到数组的空间被重复利用不用额外清理旧值这让入栈 / 出栈的效率极高仅需修改指针 赋值。2.为什么要先 “读” 再 “删”如果先执行s-top--再去读s-data[s-top]会发生什么// 错误顺序先删后读 s-top--; // top从2变成1 *e s-data[s-top]; // 读到的是20而不是原本的栈顶30这会导致你永远拿不到真正要出栈的那个元素 —— 所以必须先把栈顶元素 “复制出来保存好”再通过移动指针完成逻辑删除。3.补充物理删除几乎不用如果你非要 “物理删除” 数组里的栈顶元素把数值清空可以加一行但完全没必要*e s-data[s-top]; // 读取 s-data[s-top] 0; // 物理清空可选毫无意义 s-top--; // 逻辑删除核心因为只要top指针变了程序就不会再访问这个位置就算数值还在也不会影响栈的功能 —— 这也是顺序栈高效的原因出栈 / 入栈只需要操作指针不用动数组本身。4.出栈总结*e s-data[s-top]的唯一作用是读取并保存栈顶元素值和 “删除” 无关栈的 “删除” 核心是s-top--属于逻辑删除修改指针让元素 “不可见”而非物理删除出栈必须遵循 “先读再删” 的顺序否则会丢失要出栈的元素。七、静态顺序栈 - 获取栈顶元素// 获取栈顶元素不弹出 int getTop(Stack *s, ElemType *e) { if (s-top -1) // 栈空判断 { printf(空的\n); return 0; } *e s-data[s-top]; // 仅读取栈顶元素不修改top return 1; }八、静态顺序栈完整可运行代码固定数组版// 引入标准输入输出库用于printf、scanf等输入输出函数 #include stdio.h // 引入标准库用于malloc、free等内存操作函数本版未用到但链式栈会用到保留 #include stdlib.h // 定义栈的最大容量可根据需求修改新手建议先设小值如10方便测试栈满场景 #define MAXSIZE 100 // 定义栈存储的元素类型int可替换为char/float等体现代码的可复用性 typedef int ElemType; /** * 静态顺序栈结构体定义 * 静态栈基于数组实现大小固定内存连续 * data数组存储栈的元素 * top栈顶指针核心变量规则 * - top -1 表示空栈初始化状态 * - top 0 表示栈中有元素top指向当前栈顶元素的下标 * - top MAXSIZE-1 表示栈满 */ typedef struct { // 数组存储栈元素大小为MAXSIZE ElemType data[MAXSIZE]; // 栈顶指针整型变量记录栈顶元素的下标 int top; } Stack; /** * 初始化栈函数 * 功能将栈初始化为空栈状态 * 参数s - 指向栈结构体的指针必须传指针否则无法修改原栈的top值 */ void initStack(Stack *s) { // 空栈的核心标志栈顶指针设为-1 s-top -1; } /** * 判断栈是否为空函数 * 功能检查栈中是否有元素返回布尔值1空0非空 * 参数s - 指向栈结构体的指针 * 返回值1空栈 / 0非空栈 */ int isEmpty(Stack *s) { // 判断栈顶指针是否为-1空栈标志 if (s-top -1) { // 新手提示打印提示信息方便调试实际项目可移除 printf(空的\n); // 返回1表示栈为空 return 1; } else { // 返回0表示栈非空 return 0; } } /** * 入栈压栈函数 * 功能将元素e添加到栈顶 * 参数 * s - 指向栈结构体的指针 * e - 要入栈的元素ElemType类型与栈的元素类型一致 * 返回值1入栈成功 / 0入栈失败栈满 */ int push(Stack *s, ElemType e) { // 先判断栈是否已满top 最大下标MAXSIZE-1表示栈满 if (s-top MAXSIZE - 1) { // 栈满无法入栈打印提示 printf(满了\n); // 返回0表示入栈失败 return 0; } // 栈未满执行入栈操作核心两步顺序不能反 // 第一步栈顶指针上移1位腾出栈顶位置 s-top; // 第二步将元素e存入新的栈顶位置s-data[s-top] s-data[s-top] e; // 返回1表示入栈成功 return 1; } /** * 出栈弹栈函数 * 功能将栈顶元素移除并通过指针返回该元素的值 * 参数 * s - 指向栈结构体的指针 * e - 指向ElemType的指针用于带回出栈的元素值关键避免返回值歧义 * 返回值1出栈成功 / 0出栈失败栈空 * 新手重点为什么用指针e * - 如果直接返回元素值当元素是0时无法区分“栈空失败”和“出栈元素是0” * - 用返回值表示操作状态指针e存元素值逻辑更清晰 */ int pop(Stack *s, ElemType *e) { // 先判断栈是否为空空栈无法出栈 if (s-top -1) { printf(空的\n); // 返回0表示出栈失败 return 0; } // 栈非空执行出栈操作核心两步顺序不能反 // 第一步将栈顶元素的值赋值给*e通过指针带回 *e s-data[s-top]; // 第二步栈顶指针下移1位逻辑删除栈顶元素数组值仍在但top范围外无效 s-top--; // 返回1表示出栈成功 return 1; } /** * 获取栈顶元素函数仅读取不删除 * 功能查看栈顶元素的值不修改栈的状态 * 参数 * s - 指向栈结构体的指针 * e - 指向ElemType的指针用于带回栈顶元素值 * 返回值1获取成功 / 0获取失败栈空 */ int getTop(Stack *s, ElemType *e) { // 先判断栈是否为空 if (s-top -1) { printf(空的\n); return 0; } // 仅读取栈顶元素值不修改top指针区别于出栈 *e s-data[s-top]; return 1; } /** * 遍历打印栈函数 * 功能从栈底到栈顶打印所有元素直观展示栈的内容 * 参数s - 指向栈结构体的指针 */ void printStack(Stack *s) { // 先判断栈是否为空空栈直接返回 if (isEmpty(s)) return; // 打印提示信息区分遍历顺序 printf(栈元素栈底→栈顶); // 遍历数组从下标0栈底到top栈顶 for (int i 0; i s-top; i) { // 打印每个元素空格分隔 printf(%d , s-data[i]); } // 换行优化输出格式 printf(\n); } /** * 主函数测试栈的所有核心功能 * 流程初始化 → 入栈 → 遍历 → 出栈 → 遍历 → 获取栈顶 → 结束 */ int main() { // 定义一个栈结构体变量s静态分配栈内存 Stack s; // 初始化栈传入s的地址修改s的top值为-1 initStack(s); // 入栈测试依次入栈10、20、30 push(s, 10); push(s, 20); push(s, 30); // 遍历打印栈预期输出10 20 30 printStack(s); // 出栈测试定义变量e接收出栈元素 ElemType e; pop(s, e); // 打印出栈元素预期输出30 printf(出栈元素%d\n, e); // 再次遍历预期输出10 20 printStack(s); // 获取栈顶测试获取当前栈顶元素 getTop(s, e); // 打印栈顶元素预期输出20 printf(当前栈顶元素%d\n, e); // 程序正常结束 return 0; }九、新手高频疑惑总结入栈为什么先top先腾空间再赋值避免覆盖当前栈顶有效数据。出栈为什么用*e传值函数返回值仅表示成功 / 失败*e单独存元素消除 0 值歧义。出栈后数组旧值为什么不删栈是逻辑删除top范围外的数据无效新入栈会直接覆盖无需清空。链式栈为什么头插栈仅操作栈顶头插效率最高符合后进先出规则。链式栈入栈为什么先p-nexts-next先连接旧栈顶防止链表断裂避免数据丢失。十、静态栈总结核心变量top是静态栈的关键top-1为空栈、topMAXSIZE-1为满栈入栈 / 出栈必须先判断栈状态操作顺序入栈先top再赋值出栈先取值再top--顺序反了会导致数据覆盖或丢失指针传参修改栈状态的函数如initStack、push必须传栈的指针否则无法修改原栈的top值出栈 / 取栈顶用指针e带回元素避免返回值歧义特性对比静态栈内存连续、操作高效但容量固定适合元素数量可预估的场景。