管理咨询公司的服务机构,北京网站seo技术厂家,安装wordpress主题放哪里,网线的制作步骤前言: #x1f4a5;#x1f388;个人主页:Dream_Chaser#xff5e; #x1f388;#x1f4a5; ✨✨专栏:http://t.csdn.cn/oXkBa ⛳⛳本篇内容:c语言数据结构--C语言实现栈 目录
什么是栈 栈的概念及结构
实现栈的方式
链表的优缺点:
顺序表的优缺点:
栈…前言: 个人主页:Dream_Chaser ✨✨专栏:http://t.csdn.cn/oXkBa ⛳⛳本篇内容:c语言数据结构--C语言实现栈 目录
什么是栈 栈的概念及结构
实现栈的方式
链表的优缺点:
顺序表的优缺点:
栈的实现
a.头文件的包含 b.栈的定义
c.接口函数
接口函数的实现
1.栈的初始化
2.销毁栈
3.入栈
4.检测栈是否为空
5.出栈
6.获取栈顶元素
7.获取栈中有效元素个数
完整代码
Test.c
Stack.h
Stack.c 什么是栈 栈的概念及结构 栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端称为 栈顶 另一端称为 栈底 。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在 栈顶。 出栈栈的删除操作叫做出栈。 出数据也在 栈顶。 栈的结构: 实现栈的方式
实现栈的方式有两种: 顺序表和链表
链表的优缺点: 优点: 1、任意位置插入删除O(1) 2、按需申请释放空间 缺点: 1、不支持下标随机访问 2、CPU高速缓存命中率会更低 先说链表实现栈的缺点: 额外内存开销链表实现的栈需要为每个节点分配内存空间来存储数据和指针。相比于数组实现的栈链表实现需要额外的内存开销来维护节点之间的指针关系可能导致内存碎片化。 动态内存分配链表实现的栈需要通过动态内存分配来创建和释放节点。这涉及到频繁的内存分配和释放操作可能导致内存管理的复杂性和性能开销。在某些情况下可能会出现内存分配失败或内存泄漏的问题。 指针操作开销链表实现的栈需要通过指针进行节点之间的连接操作。这包括插入和删除节点时的指针修改可能涉及到多个指针的更新。相比于数组实现的栈链表实现的栈需要更多的指针操作可能会带来一定的性能开销。 随机访问的限制链表是一种顺序访问的数据结构无法像数组一样通过索引进行随机访问。如果需要在栈中进行随机访问元素链表实现的栈可能不太适合而数组实现的栈更具优势。 顺序表的优缺点: 优点:1、尾插尾删效率不错。 2、下标的随机访问。 3、CPU高速缓存命中率会更高 缺点: 1、前面部分插入删除数据效率是O(N)需要挪动数据。 2、空间不够需要扩容。a、扩容是需要付出代价的b、一般还会伴随空间浪费。 顺序表实现栈的优点 内存连续性顺序表在内存中是连续存储的相比于链表的动态内存分配顺序表的元素在物理上更加紧凑。这样可以减少内存碎片化提高内存的利用效率。 随机访问顺序表可以通过索引直接访问栈中的元素具有随机访问的能力。这意味着可以快速访问栈中任意位置的元素而不需要遍历整个链表。 操作简单高效顺序表的插入和删除操作只涉及元素的移动不需要额外的指针操作和动态内存分配。这使得操作相对简单高效并且在某些情况下比链表实现更快。 空间效率相比于链表实现顺序表不需要额外的指针来维护节点之间的连接关系因此可以节省一定的空间开销。只需要存储元素本身和栈顶指针即可。 综上所述,用顺序表实现栈更好。 栈的实现
a.头文件的包含
#includestdlib.h
#includeassert.h
#includestdbool.h
#includestdio.h b.栈的定义
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;//栈顶int capacity;//栈的容量
}ST;c.接口函数
// 初始化栈
void STInit(ST* pst); // 入栈
void STPush(ST* pst, STDataType data); // 出栈
void STPop(ST* pst); // 获取栈顶元素
STDataType STTop(ST* pst); // 获取栈中有效元素个数
int STSize(ST* pst); // 检测栈是否为空如果为空返回true,如果不为空返回false
bool STEmpty(ST* pst); // 销毁栈
void STDestroy(ST* pst);
接口函数的实现
1.栈的初始化 pst-top表示栈的顶部指针通常情况下它指向栈顶元素的下一个位置,而不是指向当前栈顶元素。通过 pst-top 可以确定栈中元素的个数,打印的时候记得将 top - 1。
void STInit(ST* pst)
{assert(pst);//防止敲代码的人传过来是NULL指针pst-a NULL;//栈底//top不是数组下标,不能理解成数组下标,因为栈只能拿到栈顶的元素而数组可以随机访问拿到中间元素//pst-top-1;//指向栈顶元素pst-top 0;//指向栈顶元素的下一个位置pst-capacity 0;}分别解释一下各自的含义: pst 是指向栈的指针指向栈的首节点或头节点。- 是一个成员访问运算符用于通过指针访问结构体或类的成员 pst -a 是指向存储栈元素的数组的指针。栈中的元素通常被存储在数组中通过 pst-a 可以访问和操作该数组。在 STInit 函数中 pst-a 被设置为 NULL表示栈底为空即栈中没有任何元素。 pst-capacity 表示栈的容量即栈可以容纳的最大元素数量。当栈中元素的数量达到 pst-capacity 时栈被认为已满无法再进行入栈操作。在初始化时pst-capacity 的值通常被设置为 0表示栈的初始容量为 0。 pst-top 表示栈顶指针它指向当前栈顶元素的下一个位置。在栈为空时pst-top 的值为 0表示栈底。随着元素的入栈和出栈操作pst-top 的值会相应地增加或减少指向栈中下一个元素的位置。
2.销毁栈
为了防止野指针的出现栈销毁后记得将指针置空。
void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;
} 3.入栈
三元运算符 condition ? value1: value2 它的含义是如果条件condition为真非0则整个表达式的值为value1如果条件为假0则整个表达式的值为value2 解析: int newCapacity pst-capacity 0 ? 4 : pst-capacity * 2; 这段代码的执行顺序如下 首先评估条件pst-capacity 0 这将检查 pst 指针所指向的结构体中的 capacity 成员是否等于 0如果条件为真pst-capacity 等于 0则表达式的值为 4将其赋给 newCapacity 如果条件为假pst-capacity不等于 0则表达式的值为pst-capacity * 2将其赋给 newCapacity realloc函数:【C进阶】-- 动态内存管理_Dream_Chaser的博客-CSDN博客 动图: 函数代码: void STPush(ST* pst,STDataType x)
{if (pst-top pst-capacity){int newCapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-a, newCapacity * sizeof(STDataType));if (tmp NULL){perror(realloc fail);return;}pst-a tmp;//返回的是realloc出来的内存块的地址pst-capacity newCapacity;//把扩容后的空间大小赋值给栈容量}pst-a[pst-top] x;//先放值pst-top;//再
}
【注意事项】 1️⃣检查栈的顶部指针 top 是否等于栈的容量 capacity 。如果这两个值相等那么说明栈已经满了无法再添加新的元素。 2️⃣接着判断此时栈的容量是否是0若是0则把4赋值给newcapacity作为新的栈容量。此后若栈满了则把此时栈满时的容量 * 2进行扩容赋值给newcapacity作为新的栈容量。 3️⃣先放入新的元素入栈接着pst-top指向栈顶元素的指针 4.检测栈是否为空 栈为空返回true,不为空返回false bool STEmpty(ST* pst)//栈为空返回true,不为空返回false
{//写法一//assert(pst);//if (pst-top 0)//{// return true;//}//else//{// return false;//}//写法二return pst-top 0;
} 当栈为空时表示栈中没有任何元素。此时栈顶指针 top 的值通常被设置为特定的初始值例如0或-1指向栈底或栈外。在这种情况下栈顶指针没有指向有效的元素因此栈被认为是空的。 当栈非空时表示栈中至少有一个元素。此时栈顶指针top的值指向栈顶元素的位置。栈顶元素是最后一个被入栈的元素也是最先被访问或移除的元素。只要栈中有元素存在栈顶指针都会指向有效的位置。 因此在STEmpty(ST* pst)函数中当栈为空时即栈顶指针top的值为0或其他特定初始值我们返回 true 表示栈为空。反之如果栈非空即栈顶指针 top 的值大于0我们返回 false 表示栈不为空。
5.出栈 先用assert判断传过来的pst指针是否指向NULL。接着判断栈是否为NULL为NULLSTEmpty(pst)返回true!STEmpty(pst)就是false,断言失败程序终止。反之断言成功程序正常执行。
图解: void STPop(ST* pst)
{assert(pst);assert(!STEmpty(pst));pst-top--;
}
【注意事项】 接着将指向栈顶的指针--通过将栈顶指针top减一可以将指针向栈底方向移动从而使栈顶指向下一个元素。 指针的移动并不会直接导致元素的销毁。指针的移动只是改变了栈顶指针的位置使其指向了栈中的下一个元素。元素本身并不会被销毁只是在后续的操作中可能无法直接访问被移除的元素。 6.获取栈顶元素
图解:因为前面定义的时候pst-top0,表示指向栈顶元素的下一个位置。
pst-top-1表示栈顶元素在数组中的索引。 STDataType STTop(ST* pst)
{assert(pst);assert(!STEmpty(pst));return pst-a[pst-top - 1];
} 需要注意的是在实际使用中应确保栈不为空即栈中有元素存在才能执行取栈顶元素的操作。因此在代码中使用了 assert(!STEmpty(pst)) 进行栈非空的断言校验。
代码执行: 7.获取栈中有效元素个数
图解:由图看出,pst-top此时是指向下标为4的位置的所以栈此时的有效个数就为4 int STSize(ST* pst)
{assert(pst);return pst-top;
}代码执行: 完整代码
Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeStack.h
void TestStack1()
{ST st;STInit(st);STPush(st, 1);STPush(st, 2);STPush(st, 3);STPush(st, 4);while (!STEmpty(st)){printf(%d , STTop(st));//栈顶元素STPop(st);}STDestroy(st);
}
void TestStack2()
{ST st;STInit(st);STPush(st, 1);STPush(st, 2);printf(%d , STTop(st));STPush(st, 3);STPush(st, 4);printf(\n);printf(%d , STTop(st));//printf(%d, STSize(st));//while (!STEmpty(st))//{// printf(%d , STTop(st));//栈顶元素// STPop(st);//}STDestroy(st);
}
void TestStack3()
{ST st;STInit(st);STPush(st, 1);STPush(st, 2);STPush(st, 3);STPush(st, 4);//printf(%d, STSize(st));STDestroy(st);
}int main()
{TestStack1();//入栈出栈//TestStack2();//获取栈顶元素//TestStack3();//计算栈中有效元素个数 return 0;
}
Stack.h
#pragma once
#includestdlib.h
#includeassert.h
#includestdbool.h
#includestdio.h
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;//栈顶的位置int capacity;//栈的容量
}ST;void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst,STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST*pst);
Stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeStack.h
void STInit(ST* pst)
{assert(pst);pst-a NULL;//栈底//top不是下标//pst-top-1;//指向栈顶元素pst-top 0;//指向栈顶元素的下一个位置pst-capacity 0;}void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;
}void STPush(ST* pst,STDataType x)
{if (pst-top pst-capacity){int newCapacity pst-capacity 0 ? 4 : pst-capacity * 2;//true,4.false,括2倍STDataType* tmp (STDataType*)realloc(pst-a, newCapacity * sizeof(STDataType));//返回值地址相等就是原地扩容不同就是异地扩if (tmp NULL){perror(realloc fail);return;}pst-a tmp;//返回的是realloc出来的内存块的地址pst-capacity newCapacity;//把扩容后的空间大小赋值给栈容量}pst-a[pst-top] x;//先放值pst-top;//再
}void STPop(ST* pst)
{assert(pst);assert(!STEmpty(pst));pst-top--;
}STDataType STTop(ST* pst)
{assert(pst);assert(!STEmpty(pst));return pst-a[pst-top - 1];
}bool STEmpty(ST* pst)//栈为空返回true,不为空返回false
{//assert(pst);//if (pst-top 0)//{// return true;//}//else//{// return false;//}return pst-top 0;
}
int STSize(ST* pst)
{assert(pst);return pst-top;
} 栈面试题还在持续更新中感谢支持 文章转载自： http://www.morning.linzhigongmao.cn.gov.cn.linzhigongmao.cn http://www.morning.tgtwy.cn.gov.cn.tgtwy.cn http://www.morning.wgbmj.cn.gov.cn.wgbmj.cn http://www.morning.qhnmj.cn.gov.cn.qhnmj.cn http://www.morning.byxs.cn.gov.cn.byxs.cn http://www.morning.rcntx.cn.gov.cn.rcntx.cn http://www.morning.jcxqc.cn.gov.cn.jcxqc.cn http://www.morning.bfrsr.cn.gov.cn.bfrsr.cn http://www.morning.tkflb.cn.gov.cn.tkflb.cn http://www.morning.gdgylp.com.gov.cn.gdgylp.com http://www.morning.gjssk.cn.gov.cn.gjssk.cn http://www.morning.fwkjp.cn.gov.cn.fwkjp.cn http://www.morning.knpmj.cn.gov.cn.knpmj.cn http://www.morning.kgkph.cn.gov.cn.kgkph.cn http://www.morning.lbbrw.cn.gov.cn.lbbrw.cn http://www.morning.qfgwx.cn.gov.cn.qfgwx.cn http://www.morning.rfgc.cn.gov.cn.rfgc.cn http://www.morning.fxzw.cn.gov.cn.fxzw.cn http://www.morning.smqjl.cn.gov.cn.smqjl.cn http://www.morning.lbggk.cn.gov.cn.lbggk.cn http://www.morning.wgkz.cn.gov.cn.wgkz.cn http://www.morning.lssfd.cn.gov.cn.lssfd.cn http://www.morning.sfsjh.cn.gov.cn.sfsjh.cn http://www.morning.gthgf.cn.gov.cn.gthgf.cn http://www.morning.zzbwjy.cn.gov.cn.zzbwjy.cn http://www.morning.krbjb.cn.gov.cn.krbjb.cn http://www.morning.plqqp.cn.gov.cn.plqqp.cn http://www.morning.gqfks.cn.gov.cn.gqfks.cn http://www.morning.tmzlt.cn.gov.cn.tmzlt.cn http://www.morning.xdqrz.cn.gov.cn.xdqrz.cn http://www.morning.bpmfl.cn.gov.cn.bpmfl.cn http://www.morning.qjghx.cn.gov.cn.qjghx.cn http://www.morning.uycvv.cn.gov.cn.uycvv.cn http://www.morning.ygztf.cn.gov.cn.ygztf.cn http://www.morning.daidudu.com.gov.cn.daidudu.com http://www.morning.hphqy.cn.gov.cn.hphqy.cn http://www.morning.prznc.cn.gov.cn.prznc.cn http://www.morning.rwhlf.cn.gov.cn.rwhlf.cn http://www.morning.tbnn.cn.gov.cn.tbnn.cn http://www.morning.prgnp.cn.gov.cn.prgnp.cn http://www.morning.tmzlt.cn.gov.cn.tmzlt.cn http://www.morning.ndynz.cn.gov.cn.ndynz.cn http://www.morning.lgznc.cn.gov.cn.lgznc.cn http://www.morning.jzmqk.cn.gov.cn.jzmqk.cn http://www.morning.nrjr.cn.gov.cn.nrjr.cn http://www.morning.fqtzn.cn.gov.cn.fqtzn.cn http://www.morning.wzjhl.cn.gov.cn.wzjhl.cn http://www.morning.fdrwk.cn.gov.cn.fdrwk.cn http://www.morning.ybgcn.cn.gov.cn.ybgcn.cn http://www.morning.npgwb.cn.gov.cn.npgwb.cn http://www.morning.qkzdc.cn.gov.cn.qkzdc.cn http://www.morning.gwwky.cn.gov.cn.gwwky.cn http://www.morning.dkbsq.cn.gov.cn.dkbsq.cn http://www.morning.dqxnd.cn.gov.cn.dqxnd.cn http://www.morning.pmjhm.cn.gov.cn.pmjhm.cn http://www.morning.xqgfy.cn.gov.cn.xqgfy.cn http://www.morning.mdjtk.cn.gov.cn.mdjtk.cn http://www.morning.chmcq.cn.gov.cn.chmcq.cn http://www.morning.ymrq.cn.gov.cn.ymrq.cn http://www.morning.xhxsr.cn.gov.cn.xhxsr.cn http://www.morning.yyngs.cn.gov.cn.yyngs.cn http://www.morning.lhldx.cn.gov.cn.lhldx.cn http://www.morning.nrddx.com.gov.cn.nrddx.com http://www.morning.qcfcz.cn.gov.cn.qcfcz.cn http://www.morning.ndmbz.cn.gov.cn.ndmbz.cn http://www.morning.smhtg.cn.gov.cn.smhtg.cn http://www.morning.fjmfq.cn.gov.cn.fjmfq.cn http://www.morning.rdmz.cn.gov.cn.rdmz.cn http://www.morning.langlaitech.cn.gov.cn.langlaitech.cn http://www.morning.zxhpx.cn.gov.cn.zxhpx.cn http://www.morning.jljiangyan.com.gov.cn.jljiangyan.com http://www.morning.dxrbp.cn.gov.cn.dxrbp.cn http://www.morning.bttph.cn.gov.cn.bttph.cn http://www.morning.fbmzm.cn.gov.cn.fbmzm.cn http://www.morning.cxtbh.cn.gov.cn.cxtbh.cn http://www.morning.c7491.cn.gov.cn.c7491.cn http://www.morning.lwyqd.cn.gov.cn.lwyqd.cn http://www.morning.hotlads.com.gov.cn.hotlads.com http://www.morning.bxbkq.cn.gov.cn.bxbkq.cn http://www.morning.lnyds.cn.gov.cn.lnyds.cn
