【附C语言源码】C语言 栈结构 实现及其扩展操作
【附C语言源码】基于链表实现的C语言栈结构及其扩展操作栈作为一种基础的数据结构在表达式求值、函数调用、深度优先搜索等场景中均有广泛应用。设计思路数据结构的选取栈的实现通常有两种方式顺序栈数组和链式栈链表。本实现选择链表方案主要基于以下考量动态扩容链表无需预先分配固定容量避免了数组扩容时的数据迁移开销内存利用节点按需分配不存在数组尾部的闲置空间操作一致性入栈出栈均为O(1)时间复杂度与顺序栈持平结构定义typedefintData;structNode{Data node_data;structNode*next;};structStack{Node*top;intsize;};此处将Data定义为int的别名若后续需要存储其他类型数据仅需修改此处 typedef 即可无需改动接口实现。Stack结构体中维护size字段使得获取栈元素数量的操作从O(n)降至O(1)。核心操作实现内存管理创建栈时使用calloc而非malloc确保指针字段初始化为NULLStack*creatStack(void){Stack*stack(Stack*)calloc(1,sizeof(Stack));if(!stack)returnNULL;stack-topNULL;stack-size0;returnstack;}销毁栈时需先释放所有节点再释放栈结构本身避免内存泄漏voiddestroyStack(Stack*stack){if(!stack)return;clear(stack);// 遍历释放节点free(stack);}入栈与出栈入栈操作采用头插法新节点直接插入栈顶voidpush(Stack*stack,Data val){if(!stack)return;Node*newNode(Node*)calloc(1,sizeof(Node));if(!newNode)return;newNode-node_dataval;newNode-nextstack-top;stack-topnewNode;stack-size;}出栈时保存栈顶指针更新栈顶后释放原节点voidpop(Stack*stack){if(!stack||!stack-top)return;Node*tempstack-top;stack-topstack-top-next;free(temp);stack-size--;}所有操作均包含空指针检查增强代码的健壮性。扩展操作的设计与实现除基础操作外本实现还提供了若干扩展功能以下对其设计思路进行说明。栈的复制复制操作需要保持原栈的顺序不变。直接遍历原栈并依次压入新栈会导致顺序反转因此引入临时栈作为中转voidcopyStack(Stack*src,Stack*dest){clear(dest);Stack*tempStackcreatStack();// 第一次反转原栈 - 临时栈Node*curNodesrc-top;while(curNode){push(tempStack,curNode-node_data);curNodecurNode-next;}// 第二次反转临时栈 - 目标栈while(!isEmpty(tempStack)){push(dest,getAndPop(tempStack));}destroyStack(tempStack);}该算法的时间复杂度为O(n)空间复杂度为O(n)由临时栈的额外开销所致。栈的反转反转操作同样借助临时栈完成。将原栈元素全部弹出并压入临时栈此时顺序已反转再移回原栈即可voidreverseStack(Stack*stack){if(!stack||!stack-top||!stack-top-next)return;Stack*tempStackcreatStack();while(!isEmpty(stack)){push(tempStack,getAndPop(stack));}while(!isEmpty(tempStack)){push(stack,getAndPop(tempStack));}destroyStack(tempStack);}栈顶元素交换该操作仅需两次出栈和两次入栈voidswapTopTwo(Stack*stack){if(!stack||stack-size2)return;Data firstgetAndPop(stack);Data secondgetAndPop(stack);push(stack,first);push(stack,second);}此处利用栈的后进先出特性天然地实现了两个元素的交换。测试用例main函数中设计了一系列测试场景覆盖以下验证点连续入栈后栈大小的正确性栈顶元素的读取与出栈getAndPop的组合操作swapTopTwo对栈状态的影响copyStack后两栈的独立性reverseStack的顺序反转效果clear与destroyStack的内存释放测试输出示例C:\Users\anjuxi\Desktop\C语言 栈库a.exe 入栈1,2,3,4,5当前栈从栈顶到栈底54321栈大小5 栈顶元素5 栈大小5 出栈一次 当前栈从栈顶到栈底4321栈大小4 获取并出栈4 当前栈从栈顶到栈底321栈大小3 交换栈顶两个元素 当前栈从栈顶到栈底231栈大小3 复制栈到stack2 stack2从栈顶到栈底231stack2大小3 反转stack2 stack2反转后从栈顶到栈底231stack2大小3 清空stack stack是否为空是 stack大小0 栈已销毁总结本文实现了一套完整的链式栈结构主要特点包括通过typedef实现数据类型的快速切换维护size字段以优化查询性能全面的空指针检查提升接口安全性基于临时栈的算法设计解决复制与反转问题完整代码已开源可根据实际需求进行裁剪或扩展。⚠️源码地址https://github.com/anjuxi/C-stack_library
)
