数据结构初开课：栈的实现

本次编译环境为VS2022

前言

在我们了解完链表：单链表和双链表后 我们将开始 栈和队列的学习
今天我们学习的是 栈 的代码实现 其中会有部分画图内容 和代码内容方便各位理解

栈的实现

1.什么是栈

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底
栈 是先进后出的

通过图例可以更快地理解

2.栈的实现

一.头文件和源文件的创建以及头文件中的内容

老样子 一个.h 文件和一个 .c文件
给到.h文件的实现代码`

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>typedefintSTDateType;typedefstructStack{STDateType*a;inttop;intcapacity;}ST;//功能函数//定义voidSTInit(ST*ps);//销毁voidSTDestory(ST*ps);//插入voidSTPush(ST*ps,STDateType x);//删除voidSTPop(ST*ps);//找栈顶STDateTypeSTTop(ST*ps);//判断空boolSTEmpty(ST*ps);//获取栈中的个数intSTSize(ST*ps);

二.功能代码的实现

1.定义和销毁

定义和销毁其实和我们以前学过的链表顺序表大差不差 这里放出实现代码直接给各位观看

voidSTInit(ST*ps){assert(ps);ps->a=NULL;ps->capacity=0;ps->top=0;}//销毁voidSTDestory(ST*ps){assert(ps);free(ps->a);ps->a=NULL;ps->capacity=ps->top=0;}

2.增加和删除

了解完图例后呈现代码给各位

//插入voidSTPush(ST*ps,STDateType x){assert(ps);//当我们的 top = capacity的时候 要进行扩容操作 否则无法容纳归纳topif(ps->top=ps->capacity){intnewcapacity=ps->capacity==0?4:2*ps->capacity;STDateType*tmp=(STDateType*)realloc(ps->a,sizeof(STDateType)*newcapacity);if(tmp==NULL){perror("realloc fail");return;}//完成扩容操作ps->a=tmp;ps->capacity=newcapacity;}//扩容结束后 进行插入操作ps->a[ps->top]=x;ps->top++;}//删除voidSTPop(ST*ps){assert(ps);assert(ps->top>0);//top不大于0删不了啊ps->top--;}

这里的扩容操作与顺序表中的几乎一样 注意realloc的类型 和newcapacity的书写即可

3.判断空 找栈顶 获取栈中的个数

这三个功能函数其实都大同小异
都是根据 top来进行实现
判断空 只需看 top==0 如果等于0 则栈为空

找栈顶 也是 看 数组中[top-1]的值即可

获取栈中的个数 其实就是 看top的大小 当有一个值时 top = 1
同理可得 看top大小就能看出 栈中的个数
给到代码给各位

//找栈顶STDateTypeSTTop(ST*ps){assert(ps);assert(ps->top>0);returnps->a[ps->top-1];}//判断空boolSTEmpty(ST*ps){assert(ps);returnps->top==0;}//获取栈中的个数intSTSize(ST*ps){assert(ps);returnps->top;}

总结

栈的代码书写较为简单 但其中重要的原理大家也不能小觑 后进先出的规则不可被忽略 所以各位书写的时候尽量通过画图来解决此类问题
感谢各位彦祖亦非的观看 走之前不妨点个小赞 谢谢！！！