【附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，确保指针字段初始化为NULL：

Stack*creatStack(void){Stack*stack=(Stack*)calloc(1,sizeof(Stack));if(!stack)returnNULL;stack->top=NULL;stack->size=0;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_data=val;newNode->next=stack->top;stack->top=newNode;stack->size++;}

出栈时保存栈顶指针，更新栈顶后释放原节点：

voidpop(Stack*stack){if(!stack||!stack->top)return;Node*temp=stack->top;stack->top=stack->top->next;free(temp);stack->size--;}

所有操作均包含空指针检查，增强代码的健壮性。

扩展操作的设计与实现

除基础操作外，本实现还提供了若干扩展功能，以下对其设计思路进行说明。

栈的复制

复制操作需要保持原栈的顺序不变。直接遍历原栈并依次压入新栈会导致顺序反转，因此引入临时栈作为中转：

voidcopyStack(Stack*src,Stack*dest){clear(dest);Stack*tempStack=creatStack();// 第一次反转：原栈 -> 临时栈Node*curNode=src->top;while(curNode){push(tempStack,curNode->node_data);curNode=curNode->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*tempStack=creatStack();while(!isEmpty(stack)){push(tempStack,getAndPop(stack));}while(!isEmpty(tempStack)){push(stack,getAndPop(tempStack));}destroyStack(tempStack);}

栈顶元素交换

该操作仅需两次出栈和两次入栈：

voidswapTopTwo(Stack*stack){if(!stack||stack->size<2)return;Data first=getAndPop(stack);Data second=getAndPop(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 栈已销毁