企业官网建设流程全解析

C语言实现栈的详细解析

栈（Stack）一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端，称为栈顶，另一端称为栈底。具有后进先出（LIFO, Last In First Out）的特性。它在函数调用、表达式求值、括号匹配等场景有广泛应用。下面我将详细讲解C语言中实现栈的两种主要方式：顺序栈（基于数组-最常用）和链式栈（基于链表）。

一、栈的基本概念

栈的核心特性

• 后进先出：最后进入的元素最先被取出
• 操作限制：只能在栈顶进行插入（push）和删除（pop）操作
• 基本操作时间复杂度：均为O(1)

栈的两个经典操作

1. 压栈（Push）：栈的插入操作，将元素放入栈顶
2. 出栈（Pop）：栈的删除操作，将栈顶元素移除

二、栈的实现方式

1. 顺序栈（基于数组实现）

结构体定义

typedefstruct{int*data;// 存储元素的数组intsize;// 栈的总容量inttop;// 栈顶指针（初始为-1，表示空栈）}Stack;

关键点：

• top初始值为-1表示空栈
• size限制栈的最大容量
• 使用动态数组实现顺序存储

代码实现

初始化栈

Stack*initStack(intn){Stack*s=(Stack*)malloc(sizeof(Stack));s->data=(int*)malloc(sizeof(int)*n);s->size=n;s->top=-1;// 初始化栈顶指针returns;}

入栈操作

intpush(Stack*s,intval){if(s->top==s->size-1){// 栈已满，返回错误return-1;}s->top++;s->data[s->top]=val;return0;// 成功}

出栈操作

intpop(Stack*s,int*val){if(s->top==-1){// 栈为空，返回错误return-1;}*val=s->data[s->top];s->top--;return0;// 成功}

判空操作

intempty(Stack*s){returns->top==-1;}

获取栈顶元素

inttop(Stack*s){if(empty(s)){return-1;// 空栈返回错误值}returns->data[s->top];}

顺序栈的特点

• 优点：实现简单，内存连续，访问速度快
• 缺点：容量固定，可能有空间浪费；满栈时需要扩容（增加复杂性）

完整数组实现

#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>// 定义栈中存储的数据类型为整型typedefintSTDataType;// 定义栈结构体typedefstructStack{STDataType*a;// 动态数组，用于存储栈元素inttop;// 栈顶指针（指向栈顶元素的下一个位置）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);// 判断栈是否为空// 初始化栈voidSTInit(ST*ps){// 确保传入的指针有效assert(ps);// 初始化栈成员：// 1. 将动态数组指针置为NULL（表示尚未分配内存）// 2. 栈顶指针初始化为0（表示栈为空，栈顶元素在位置-1，但实际存储从0开始）// 3. 栈容量初始化为0ps->a=NULL;ps->top=0;ps->capacity=0;}// 销毁栈（释放内存并重置状态）voidSTDestroy(ST*ps){// 确保传入的指针有效assert(ps);// 释放动态数组内存free(ps->a);// 重置栈状态（避免野指针）ps->a=NULL;ps->top=0;ps->capacity=0;}// 入栈操作（压栈）voidSTPush(ST*ps,STDataType x){// 确保传入的指针有效assert(ps);// 检查栈是否已满（top等于容量表示已无可用空间）if(ps->top==ps->capacity){// 计算新容量：如果当前容量为0（空栈），则分配4个元素空间// 否则，容量翻倍（避免频繁扩容，提高效率）intnewcapacity=ps->capacity==0?4:ps->capacity*2;// 重新分配内存，扩展栈容量STDataType*tmp=(STDataType*)realloc(ps->a,newcapacity*sizeof(STDataType));// 检查内存分配是否成功if(tmp==NULL){perror("realloc fail");// 打印错误信息return;// 分配失败，退出函数}// 更新栈的数组指针和容量ps->a=tmp;ps->capacity=newcapacity;}// 将元素放入栈顶位置（top指向的位置）ps->a[ps->top]=x;// 栈顶指针后移（指向下一个空位置）ps->top++;}// 出栈操作（弹栈）voidSTPop(ST*ps){// 确保传入的指针有效assert(ps);// 检查栈是否为空（不能从空栈弹出元素）assert(!STEmpty(ps));// 栈顶指针前移（相当于移除栈顶元素）ps->top--;}// 获取栈顶元素STDataTypeSTTop(ST*ps){// 确保传入的指针有效assert(ps);// 检查栈是否为空assert(!STEmpty(ps));// 栈顶元素位于top-1位置（因为top指向下一个空位置）returnps->a[ps->top-1];}// 获取栈中元素个数intSTSize(ST*ps){// 确保传入的指针有效assert(ps);// 栈中元素个数 = top（因为top表示已使用的元素数量）returnps->top;}// 判断栈是否为空boolSTEmpty(ST*ps){// 确保传入的指针有效assert(ps);// 如果栈顶指针为0，则栈为空returnps->top==0;}intmain(){ST s;STInit(&s);STPush(&s,1);STPush(&s,2);STPush(&s,3);inttop=STTop(&s);printf("%d ",top);STPop(&s);STPush(&s,4);STPush(&s,5);while(!STEmpty(&s)){inttop=STTop(&s);printf("%d ",top);STPop(&s);}STDestroy(&s);return0;}

主要掌握上面数组实现即可

2. 链式栈（基于链表实现）

结构体定义

typedefstructNode{intdata;structNode*next;}Node;typedefstruct{Node*top;// 栈顶指针intsize;// 栈的大小}Stack;

关键点：

• 栈顶即为链表的头节点
• top指向栈顶元素
• size记录栈中元素个数

代码实现

初始化栈

Stack*initStack(){Stack*s=(Stack*)malloc(sizeof(Stack));s->top=NULL;s->size=0;returns;}

入栈操作

voidpush(Stack*s,intval){Node*newNode=(Node*)malloc(sizeof(Node));newNode->data=val;newNode->next=s->top;s->top=newNode;s->size++;}

出栈操作

intpop(Stack*s,int*val){if(s->top==NULL){return-1;// 栈为空}Node*temp=s->top;*val=temp->data;s->top=temp->next;free(temp);s->size--;return0;}

判空操作

intempty(Stack*s){returns->top==NULL;}

获取栈顶元素

inttop(Stack*s){if(empty(s)){return-1;// 空栈返回错误值}returns->top->data;}

链式栈的特点

• 优点：空间利用率高，无需扩容，动态增长
• 缺点：实现相对复杂，内存不连续，访问速度稍慢

三、两种实现方式的对比

四、栈的应用场景

栈在C语言中有以下广泛应用：

1. 表达式求值：

   • 栈可以用于存储运算符和操作数
   • 实现表达式的求值算法，如中缀表达式转后缀表达式并计算结果

2. 函数调用：

   • 函数调用时，需要保存函数的返回地址、参数和局部变量等信息
   • 这些信息使用栈来保存和管理

3. 括号匹配：

   • 栈可以用于检查括号是否匹配
   • 遇到左括号入栈，遇到右括号出栈，最终检查栈是否为空

4. 逆波兰表达式求值：

   • 逆波兰表达式是一种后缀表达式
   • 栈可以实现逆波兰表达式的求值

5. 递归算法：

   • 递归算法中，每次递归调用时需要保存当前函数的状态
   • 这些状态可以使用栈来保存和管理

6. 深度优先搜索：

   • 栈可以用于实现图的深度优先搜索算法

五、实际应用示例

括号匹配检查

#include<stdio.h>#include<stdlib.h>typedefstruct{char*data;intsize;inttop;}Stack;Stack*initStack(intn){Stack*s=(Stack*)malloc(sizeof(Stack));s->data=(char*)malloc(sizeof(char)*n);s->size=n;s->top=-1;returns;}intpush(Stack*s,charc){if(s->top==s->size-1)return-1;s->top++;s->data[s->top]=c;return0;}intpop(Stack*s,char*c){if(s->top==-1)return-1;*c=s->data[s->top];s->top--;return0;}intempty(Stack*s){returns->top==-1;}intisMatching(charc1,charc2){return(c1=='('&&c2==')')||(c1=='['&&c2==']')||(c1=='{'&&c2=='}');}intcheckBrackets(char*str){Stack*s=initStack(100);for(inti=0;str[i]!='\0';i++){if(str[i]=='('||str[i]=='['||str[i]=='{'){push(s,str[i]);}elseif(str[i]==')'||str[i]==']'||str[i]=='}'){charc;if(empty(s)||!isMatching(pop(s,&c),str[i])){return0;// 括号不匹配}}}returnempty(s);// 检查栈是否为空}intmain(){charstr1[]="({[()])}";charstr2[]="({[]})";printf("str1: %s\n",checkBrackets(str1)?"匹配":"不匹配");printf("str2: %s\n",checkBrackets(str2)?"匹配":"不匹配");return0;}

六、总结

1. 栈的实现：

   • 顺序栈：基于数组，实现简单，但容量固定
   • 链式栈：基于链表，空间利用率高，动态增长

2. 选择建议：

   • 如果已知栈的大小，且对性能要求高，选择顺序栈
   • 如果栈的大小不确定，需要动态增长，选择链式栈

3. 栈的核心价值：

   • 通过后进先出的特性，简化了复杂问题的解决
   • 为表达式求值、括号匹配、函数调用等提供了高效解决方案

4. 重要原则：

   • 所有栈操作必须检查栈是否为空（避免空栈出栈错误）
   • 顺序栈需注意容量限制，满栈时需要处理扩容
   • 链式栈需注意内存管理，出栈时需释放节点内存

栈作为基础数据结构，理解其原理和实现方式对学习更复杂的数据结构和算法至关重要。希望这篇详细解析能帮助你深入理解C语言中栈的实现和应用。