joomla 网站图标,做军事网站的项目背景图片,东莞公司企业设计网站建设,兰州彩票网站制作#x1f618;个人主页#xff1a;Cx330❀ #x1f440;个人简介#xff1a;一个正在努力奋斗逆天改命的二本觉悟生 #x1f4d6;个人专栏#xff1a;《C语言》《LeetCode刷题集》《数据结构-初阶》 前言#xff1a;在之前几篇博客中#xff0c;我们学习了顺序表和链表个人主页Cx330❀ 个人简介一个正在努力奋斗逆天改命的二本觉悟生 个人专栏《C语言》《LeetCode刷题集》《数据结构-初阶》 前言在之前几篇博客中我们学习了顺序表和链表接下来我们将学习栈的相关知识希望大家继续坚持下去 目录 一、栈的概念与结构
二、栈的初始化和销毁
注意事项
三、、入栈
四、出栈
五、取栈顶元素
注意事项
测试结果
六、获取栈中元素个数
七、全部代码实现
Stack.h
Stack.c
test.c 一、栈的概念与结构
栈⼀种特殊的线性表其只允许在固定的一端进行插⼊和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。
压栈栈的插入操作叫做进栈/压栈/入栈入数据也在栈顶
栈战栈的删除操作叫做出栈。出数据也在栈顶 例子我们可以将栈想象为水杯水杯的地步就是栈底开口的地方就是栈顶在水杯里面放石头直到放满为止先放进杯子的石头是最后才能拿出来的。 注意栈的实现一般可以用数组或者链表来实现但是相对而言数组的结构实现更优一些将数组的尾部作为栈顶数组的头部作为栈顶插入删除数据的时间复杂度都为O(1)但是链表使用头部也可以进行插入删除时间复杂度也为O(1)但是每次插入都会申请一个节点大小的空间在空间上相对而言数组的结构更加优秀 栈的结构
//定义栈的结构
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;//指向栈顶的位置--刚好就是栈中有效数据个数int capacity;//栈的空间大小
}ST; 二、栈的初始化和销毁
初始化
//初始化
void STInit(ST* ps)
{ps-arr NULL;ps-capacity ps-top 0;
}
销毁
//销毁
void STDesTroy(ST* ps)
{if (ps-arr)free(ps-arr);ps-arr NULL;ps-capacity ps-top 0;
}
注意事项 这里的结构和顺序表几乎是一样的但是为了区分size这里我们使用top作为栈顶 三、、入栈
//入栈--栈顶
void STPush(ST* ps, STDataType x)
{assert(ps);//判断空间是否足够if (ps-capacity ps-top){//增容int newCapacity ps-capacity0 ? 4 : 2 * ps-capacity;STDataType* tmp (STDataType*)realloc(ps-arr, newCapacity * sizeof(STDataType));if (tmpNULL){perror(realloc fail!);exit(1);}ps-arr tmp;ps-capacity newCapacity;}//空间足够ps-arr[ps-top] x;
} 相信大家看到这些代码的时候并不陌生这里的逻辑和顺序表几乎一模一样当在栈中插入数据时由于栈顶插入所以要先判断栈的空间是否足够若不够先增容足够的话就将x赋给ps-arr[ps-top]就可以了 四、出栈
在出栈之前首先要判断栈是否为空若不为空才可以进行出栈操作所以这里封装一个判空的接口
//栈是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;//栈顶为0栈就为空
}
出栈
//出栈--栈顶
void STPop(ST* ps)
{assert(!STEmpty(ps));ps-top--;
} 栈不为空直接让ps-top--就可以了非常简单 五、取栈顶元素
//取栈顶元素
STDataType STTop(ST* ps)
{assert(!STEmpty(ps));return ps-arr[ps-top-1];//易错top是空的top-1才是栈顶元素
}
注意事项 这里要注意的是top是栈顶而top-1才是栈顶元素 test.c:
#includestack.hvoid test1()
{ST ps;STInit(ps);//入栈STPush(ps, 1);STPush(ps, 2);STPush(ps, 3);STPush(ps, 4);while (!STEmpty(ps)){//取栈顶元素打印STDataType top STTop(ps);printf(%d , top);//出栈STPop(ps);}printf(\n);//销毁STDestory(ps);
}int main()
{test1();
}
测试结果 六、获取栈中元素个数
//获取栈中有效数据个数
int STSize(ST* ps)
{assert(ps);return ps-top;
} 实现起来也是非常简单了直接返回ps-top刚好就是有效元素个数 七、全部代码实现
Stack.h
#pragma once
#includestdio.h
#includestdlib.h
#includestdbool.h
#includeassert.h
//定义栈的结构
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;//指向栈顶的位置--刚好就是栈中有效数据个数int capacity;//栈的空间大小
}ST;
//初始化
void STInit(ST* ps);
//销毁
void STDesTroy(ST* ps);
//入栈--栈顶
void STPush(ST* ps, STDataType x);
//栈是否为空
bool STEmpty(ST* ps);
//出栈--栈顶
void STPop(ST* ps);
//取栈顶元素
STDataType STTop(ST* ps);
Stack.c
#includestack.h
//初始化
void STInit(ST* ps)
{ps-arr NULL;ps-capacity ps-top 0;
}
//销毁
void STDesTroy(ST* ps)
{if (ps-arr)free(ps-arr);ps-arr NULL;ps-capacity ps-top 0;
}//入栈--栈顶
void STPush(ST* ps, STDataType x)
{assert(ps);//判断空间是否足够if (ps-capacity ps-top){//增容int newCapacity ps-capacity0 ? 4 : 2 * ps-capacity;STDataType* tmp (STDataType*)realloc(ps-arr, newCapacity * sizeof(STDataType));if (tmpNULL){perror(realloc fail!);exit(1);}ps-arr tmp;ps-capacity newCapacity;}//空间足够ps-arr[ps-top] x;
}//栈是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}//出栈--栈顶
void STPop(ST* ps)
{assert(!STEmpty(ps));ps-top--;
}//取栈顶元素
STDataType STTop(ST* ps)
{assert(!STEmpty(ps));return ps-arr[ps-top-1];//易错top是空的top-1才是栈顶元素
}//获取栈中有效数据个数
int STSize(ST* ps)
{assert(ps);return ps-top;
}
test.c
#includestack.h
void test01()
{ST st;STInit(st);STPush(st, 1);STPush(st, 2);STPush(st, 3);STPush(st, 4);printf(size:%d\n, STSize(st));while (!STEmpty(st)){//取栈顶STDataType top STTop(st);printf(%d , top);//出栈STPop(st);}printf(\n);STDesTroy(st);
}
int main()
{test01();return 0;
} 往期回顾
【数据结构初阶】--双向链表一
【数据结构初阶】--双向链表二
总结这篇博客带着给大家实现了栈的全部接口了其实可以看出来栈的结构很简单但是大家不能眼高手低下去一定要自己画图操作那么下篇博客将带着大家实现队列大家敬请期待如果文章对你有帮助的话欢迎评论点赞收藏加关注感谢大家的支持
