文章目录C语言实现栈的详细解析一、栈的基本概念栈的核心特性栈的两个经典操作二、栈的实现方式1. 顺序栈基于数组实现结构体定义代码实现顺序栈的特点完整数组实现2. 链式栈基于链表实现结构体定义代码实现链式栈的特点三、两种实现方式的对比四、栈的应用场景五、实际应用示例括号匹配检查六、总结C语言实现栈的详细解析栈Stack一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。具有后进先出LIFO, Last In First Out的特性。它在函数调用、表达式求值、括号匹配等场景有广泛应用。下面我将详细讲解C语言中实现栈的两种主要方式顺序栈基于数组-最常用和链式栈基于链表。一、栈的基本概念栈的核心特性后进先出最后进入的元素最先被取出操作限制只能在栈顶进行插入push和删除pop操作基本操作时间复杂度均为O(1)栈的两个经典操作压栈Push栈的插入操作将元素放入栈顶出栈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-sizen;s-top-1;// 初始化栈顶指针returns;}入栈操作intpush(Stack*s,intval){if(s-tops-size-1){// 栈已满返回错误return-1;}s-top;s-data[s-top]val;return0;// 成功}出栈操作intpop(Stack*s,int*val){if(s-top-1){// 栈为空返回错误return-1;}*vals-data[s-top];s-top--;return0;// 成功}判空操作intempty(Stack*s){returns-top-1;}获取栈顶元素inttop(Stack*s){if(empty(s)){return-1;// 空栈返回错误值}returns-data[s-top];}顺序栈的特点优点实现简单内存连续访问速度快缺点容量固定可能有空间浪费满栈时需要扩容增加复杂性完整数组实现#includestdio.h#includestdlib.h#includestdbool.h#includeassert.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-aNULL;ps-top0;ps-capacity0;}// 销毁栈释放内存并重置状态voidSTDestroy(ST*ps){// 确保传入的指针有效assert(ps);// 释放动态数组内存free(ps-a);// 重置栈状态避免野指针ps-aNULL;ps-top0;ps-capacity0;}// 入栈操作压栈voidSTPush(ST*ps,STDataType x){// 确保传入的指针有效assert(ps);// 检查栈是否已满top等于容量表示已无可用空间if(ps-topps-capacity){// 计算新容量如果当前容量为0空栈则分配4个元素空间// 否则容量翻倍避免频繁扩容提高效率intnewcapacityps-capacity0?4:ps-capacity*2;// 重新分配内存扩展栈容量STDataType*tmp(STDataType*)realloc(ps-a,newcapacity*sizeof(STDataType));// 检查内存分配是否成功if(tmpNULL){perror(realloc fail);// 打印错误信息return;// 分配失败退出函数}// 更新栈的数组指针和容量ps-atmp;ps-capacitynewcapacity;}// 将元素放入栈顶位置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-top0;}intmain(){ST s;STInit(s);STPush(s,1);STPush(s,2);STPush(s,3);inttopSTTop(s);printf(%d ,top);STPop(s);STPush(s,4);STPush(s,5);while(!STEmpty(s)){inttopSTTop(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-topNULL;s-size0;returns;}入栈操作voidpush(Stack*s,intval){Node*newNode(Node*)malloc(sizeof(Node));newNode-dataval;newNode-nexts-top;s-topnewNode;s-size;}出栈操作intpop(Stack*s,int*val){if(s-topNULL){return-1;// 栈为空}Node*temps-top;*valtemp-data;s-toptemp-next;free(temp);s-size--;return0;}判空操作intempty(Stack*s){returns-topNULL;}获取栈顶元素inttop(Stack*s){if(empty(s)){return-1;// 空栈返回错误值}returns-top-data;}链式栈的特点优点空间利用率高无需扩容动态增长缺点实现相对复杂内存不连续访问速度稍慢三、两种实现方式的对比特性顺序栈链式栈实现基础数组链表空间利用率低可能有浪费高动态分配扩容需要扩容可能有性能开销无需扩容插入/删除效率O(1)O(1)代码复杂度较低较高适用场景已知栈大小需要频繁操作不知道栈大小需要动态增长四、栈的应用场景栈在C语言中有以下广泛应用表达式求值栈可以用于存储运算符和操作数实现表达式的求值算法如中缀表达式转后缀表达式并计算结果函数调用函数调用时需要保存函数的返回地址、参数和局部变量等信息这些信息使用栈来保存和管理括号匹配栈可以用于检查括号是否匹配遇到左括号入栈遇到右括号出栈最终检查栈是否为空逆波兰表达式求值逆波兰表达式是一种后缀表达式栈可以实现逆波兰表达式的求值递归算法递归算法中每次递归调用时需要保存当前函数的状态这些状态可以使用栈来保存和管理深度优先搜索栈可以用于实现图的深度优先搜索算法五、实际应用示例括号匹配检查#includestdio.h#includestdlib.htypedefstruct{char*data;intsize;inttop;}Stack;Stack*initStack(intn){Stack*s(Stack*)malloc(sizeof(Stack));s-data(char*)malloc(sizeof(char)*n);s-sizen;s-top-1;returns;}intpush(Stack*s,charc){if(s-tops-size-1)return-1;s-top;s-data[s-top]c;return0;}intpop(Stack*s,char*c){if(s-top-1)return-1;*cs-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*sinitStack(100);for(inti0;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;}六、总结栈的实现顺序栈基于数组实现简单但容量固定链式栈基于链表空间利用率高动态增长选择建议如果已知栈的大小且对性能要求高选择顺序栈如果栈的大小不确定需要动态增长选择链式栈栈的核心价值通过后进先出的特性简化了复杂问题的解决为表达式求值、括号匹配、函数调用等提供了高效解决方案重要原则所有栈操作必须检查栈是否为空避免空栈出栈错误顺序栈需注意容量限制满栈时需要处理扩容链式栈需注意内存管理出栈时需释放节点内存栈作为基础数据结构理解其原理和实现方式对学习更复杂的数据结构和算法至关重要。希望这篇详细解析能帮助你深入理解C语言中栈的实现和应用。
5.c语言实现栈【由浅入深-数据结构】
文章目录C语言实现栈的详细解析一、栈的基本概念栈的核心特性栈的两个经典操作二、栈的实现方式1. 顺序栈基于数组实现结构体定义代码实现顺序栈的特点完整数组实现2. 链式栈基于链表实现结构体定义代码实现链式栈的特点三、两种实现方式的对比四、栈的应用场景五、实际应用示例括号匹配检查六、总结C语言实现栈的详细解析栈Stack一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。具有后进先出LIFO, Last In First Out的特性。它在函数调用、表达式求值、括号匹配等场景有广泛应用。下面我将详细讲解C语言中实现栈的两种主要方式顺序栈基于数组-最常用和链式栈基于链表。一、栈的基本概念栈的核心特性后进先出最后进入的元素最先被取出操作限制只能在栈顶进行插入push和删除pop操作基本操作时间复杂度均为O(1)栈的两个经典操作压栈Push栈的插入操作将元素放入栈顶出栈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-sizen;s-top-1;// 初始化栈顶指针returns;}入栈操作intpush(Stack*s,intval){if(s-tops-size-1){// 栈已满返回错误return-1;}s-top;s-data[s-top]val;return0;// 成功}出栈操作intpop(Stack*s,int*val){if(s-top-1){// 栈为空返回错误return-1;}*vals-data[s-top];s-top--;return0;// 成功}判空操作intempty(Stack*s){returns-top-1;}获取栈顶元素inttop(Stack*s){if(empty(s)){return-1;// 空栈返回错误值}returns-data[s-top];}顺序栈的特点优点实现简单内存连续访问速度快缺点容量固定可能有空间浪费满栈时需要扩容增加复杂性完整数组实现#includestdio.h#includestdlib.h#includestdbool.h#includeassert.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-aNULL;ps-top0;ps-capacity0;}// 销毁栈释放内存并重置状态voidSTDestroy(ST*ps){// 确保传入的指针有效assert(ps);// 释放动态数组内存free(ps-a);// 重置栈状态避免野指针ps-aNULL;ps-top0;ps-capacity0;}// 入栈操作压栈voidSTPush(ST*ps,STDataType x){// 确保传入的指针有效assert(ps);// 检查栈是否已满top等于容量表示已无可用空间if(ps-topps-capacity){// 计算新容量如果当前容量为0空栈则分配4个元素空间// 否则容量翻倍避免频繁扩容提高效率intnewcapacityps-capacity0?4:ps-capacity*2;// 重新分配内存扩展栈容量STDataType*tmp(STDataType*)realloc(ps-a,newcapacity*sizeof(STDataType));// 检查内存分配是否成功if(tmpNULL){perror(realloc fail);// 打印错误信息return;// 分配失败退出函数}// 更新栈的数组指针和容量ps-atmp;ps-capacitynewcapacity;}// 将元素放入栈顶位置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-top0;}intmain(){ST s;STInit(s);STPush(s,1);STPush(s,2);STPush(s,3);inttopSTTop(s);printf(%d ,top);STPop(s);STPush(s,4);STPush(s,5);while(!STEmpty(s)){inttopSTTop(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-topNULL;s-size0;returns;}入栈操作voidpush(Stack*s,intval){Node*newNode(Node*)malloc(sizeof(Node));newNode-dataval;newNode-nexts-top;s-topnewNode;s-size;}出栈操作intpop(Stack*s,int*val){if(s-topNULL){return-1;// 栈为空}Node*temps-top;*valtemp-data;s-toptemp-next;free(temp);s-size--;return0;}判空操作intempty(Stack*s){returns-topNULL;}获取栈顶元素inttop(Stack*s){if(empty(s)){return-1;// 空栈返回错误值}returns-top-data;}链式栈的特点优点空间利用率高无需扩容动态增长缺点实现相对复杂内存不连续访问速度稍慢三、两种实现方式的对比特性顺序栈链式栈实现基础数组链表空间利用率低可能有浪费高动态分配扩容需要扩容可能有性能开销无需扩容插入/删除效率O(1)O(1)代码复杂度较低较高适用场景已知栈大小需要频繁操作不知道栈大小需要动态增长四、栈的应用场景栈在C语言中有以下广泛应用表达式求值栈可以用于存储运算符和操作数实现表达式的求值算法如中缀表达式转后缀表达式并计算结果函数调用函数调用时需要保存函数的返回地址、参数和局部变量等信息这些信息使用栈来保存和管理括号匹配栈可以用于检查括号是否匹配遇到左括号入栈遇到右括号出栈最终检查栈是否为空逆波兰表达式求值逆波兰表达式是一种后缀表达式栈可以实现逆波兰表达式的求值递归算法递归算法中每次递归调用时需要保存当前函数的状态这些状态可以使用栈来保存和管理深度优先搜索栈可以用于实现图的深度优先搜索算法五、实际应用示例括号匹配检查#includestdio.h#includestdlib.htypedefstruct{char*data;intsize;inttop;}Stack;Stack*initStack(intn){Stack*s(Stack*)malloc(sizeof(Stack));s-data(char*)malloc(sizeof(char)*n);s-sizen;s-top-1;returns;}intpush(Stack*s,charc){if(s-tops-size-1)return-1;s-top;s-data[s-top]c;return0;}intpop(Stack*s,char*c){if(s-top-1)return-1;*cs-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*sinitStack(100);for(inti0;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;}六、总结栈的实现顺序栈基于数组实现简单但容量固定链式栈基于链表空间利用率高动态增长选择建议如果已知栈的大小且对性能要求高选择顺序栈如果栈的大小不确定需要动态增长选择链式栈栈的核心价值通过后进先出的特性简化了复杂问题的解决为表达式求值、括号匹配、函数调用等提供了高效解决方案重要原则所有栈操作必须检查栈是否为空避免空栈出栈错误顺序栈需注意容量限制满栈时需要处理扩容链式栈需注意内存管理出栈时需释放节点内存栈作为基础数据结构理解其原理和实现方式对学习更复杂的数据结构和算法至关重要。希望这篇详细解析能帮助你深入理解C语言中栈的实现和应用。
