什么是栈,如何实现?

欢迎来到 Claffic 的博客 💞💞💞 

“但有一枝堪比玉,何须九畹始征兰?”

前言:

栈是一种特殊的线性表,就像开盖的桶一样,从底部开始放数据,从顶部开始取数据,那么栈具体是如何实现的呢?这篇博客为你解答:


目录

💩Part1:何为栈

1.栈的概念

2.栈的结构 

🪲Part2: 栈的实现

1.前期准备

1.1创建项目

1.2栈的结构

1.3栈的初始化

2.相关功能实现

2.1入栈

2.2检测栈是否为空 

2.3出栈

2.4获取栈顶元素

2.5获取栈中有效元素的个数

2.6销毁栈 


Part1:何为栈

1.栈的概念

栈是一种特殊的线性表,只允许从特定的一端插入或删除元素,栈中数据的元素遵循后进先出原则(Last In First Out)

进行数据插入和删除的一端称为栈顶,另一端称栈底。 

就像个桶子一样,总是先从顶部放入或取出元素。

2.栈的结构 

说完了栈的概念,大家的脑海里也许就会有栈的基本样子了,这里画图解释: 

 我是图示

Part2: 栈的实现

1.前期准备

1.1创建项目

老样子,三个项:

SList.h:头文件,声明所有函数;

SList.c:源文件,实现各函数;

test.c:  源文件,主函数所在项,可调用各函数。

1.2栈的结构

在创建结构体之前,我们不妨要考虑一个问题:
用数组还是链表来实现栈?

数组:存储空间在物理上连续,随机访问时间复杂度O(1)

链表:存储空间在逻辑上连续,但物理上不一定连续,随机访问时间复杂度O(N).

就栈的特点来说,数组更接近。还是数组香哇。

所以我们 用数组来实现栈

创建一个结构体,其中的元素包含: 

数组首元素的地址;

栈顶;

容量。

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top; // 栈顶
	int capacity; // 容量
}Stack;

1.3栈的初始化

既然创建了栈,就要进行初始化

无非就是对结构体中的元素进行初始化:

数组容量,先定义一个初始大小:4个元素大小,并且是动态的。

栈顶的话,可以是0,也可以是-1:

0时,top 的位置就是栈顶元素的下一个位置;

-1时,top 的位置就是栈顶元素的位置。

在这里我们取 top = 0

// 初始化栈
void StackInit(Stack* ps)
{
	assert(ps);

	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}

	ps->capacity = 4;
	ps->top = 0;
}

2.相关功能实现

2.1入栈

所谓入栈,就相当于尾部插入新的数据。

要注意插入数据前需检查是否满容,判断方法也很简单,就看 栈顶与容量 是否相等就可以。

// 入栈
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);

	if (ps->capacity == ps->top)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
	
		ps->a = tmp;
		ps->capacity *= 2;
	}

	ps->a[ps->top] = data;
	ps->top++;
}

2.2检测栈是否为空 

这里把检测栈是否为空单独封装成一个函数,是为了出栈做铺垫;

在栈为空的情况下是不能出栈的,所以出栈前要检测栈是否为空;

这里我们约定 如果为空返回非0结果,如果为不为空返回0

// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);

	return ps->top == 0;//表达式,真为非0,假为0
}

2.3出栈

出栈就相当于删除数据,但又不完全等于删除数据

只是改变了栈顶 ,栈顶之外的元素占有的空间不需要释放。

// 出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//注意逻辑反,为空就报错

	ps->top--;
}

2.4获取栈顶元素

因为是栈,总要在栈顶取元素的

// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps);

	return ps->a[ps->top-1];//注意元素个数与下标差1
}

2.5获取栈中有效元素的个数

其实就是栈顶啦,栈顶的数值代表了栈中有效元素的个数;

// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);

	return ps->top;
}

2.6销毁栈 

用完了栈,要记得销毁哦。

其实就是该释放的释放,容量归0,栈顶置为-1,表示没有元素。

// 销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = -1;
}

代码已上传至 我的gitee

拿走不谢~ 


总结:

栈也是线性表,具有后进先出的特点,在有这总需求的情况下可以应用,你学会了吗?

码文不易 

如果你觉得这篇文章还不错并且对你有帮助,不妨支持一波哦  💗💗💗

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/1128.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

最适合游戏开发的语言是什么?

建议初学者学习主流的开发技术 主流开发技术有大量成熟的教程、很多可以交流的学习者、及时的学习反馈等;技术的内里基本都是相同的,学习主流技术的经验、知识可以更好更快地疏通学习新知识和技术。 因此,对C#或者C二选一进行学习较好。 Un…

Linux: 以太网 PHY 驱动简析

文章目录1. 前言2. 背景3. 硬件拓扑4. 以太网卡 PHY 驱动实现4.1 MDIO 总线对象的创建和注册4.2 MDIO 总线从设的 创建注册 和 驱动注册的加载4.2.1 以太网的 PHY 设备创建和注册4.2.2 以太网的 PHY 设备驱动注册和加载4.3 绑定以太网卡的 MAC 和 PHY4.4 以太网卡 PHY 和 MAC 的…

2022-2023 年度广东省职业院校学生专业技能大赛中职组“网络安全”赛项竞赛任务书(样题)

2022-2023 年度广东省职业院校学生专业技能大赛中职组“网络安全”赛项竞赛任务书(样题) 一、竞赛时间 总计:210 分钟 二、竞赛阶段 竞赛阶段 任务阶段 竞赛任务 竞赛时间 分值 A 模块 A-1 登录安全加固 90 分钟 200…

重构·改善既有代码的设计.03之重构手法(上)

1. 前言 之前的重构系列中,介绍了书中提到的重构基础,以及识别代码的坏味道。今天继续第三更,讲述那些重构手法(上)。看看哪些手法对你的项目能有所帮助… 2. 重新组织函数 对函数进行整理,使之更恰当的…

51单片机入门 -驱动 8x8 LED 点阵屏

硬件型号、软件版本、以及烧录流程 操作系统:Windows 10 x84-64单片机:STC89C52RC编译器:SDCC烧录软件:stcgal 1.6开发板:普中51单片机开发板A2套件(2022) 在 VS Code 中新建项目到烧录的过程…

[ROC-RK3568-PC] [Firefly-Android] 10min带你了解I2C的使用

🍇 博主主页: 【Systemcall小酒屋】🍇 博主追寻:热衷于用简单的案例讲述复杂的技术,“假传万卷书,真传一案例”,这是林群院士说过的一句话,另外“成就是最好的老师”,技术…

5.springcloud微服务架构搭建 之 《springboot集成Hystrix》

1.springcloud微服务架构搭建 之 《springboot自动装配Redis》 2.springcloud微服务架构搭建 之 《springboot集成nacos注册中心》 3.springcloud微服务架构搭建 之 《springboot自动装配ribbon》 4.springcloud微服务架构搭建 之 《springboot集成openFeign》 目录 1.项目…

C语言刷题(7)(字符串旋转问题)——“C”

各位CSDN的uu们你们好呀,今天,小雅兰的内容依旧是复习之前的知识点,那么,就是做一道小小的题目啦,下面,让我们进入C语言的世界吧 实现一个函数,可以左旋字符串中的k个字符。 例如: A…

2023最新性能测试八股文【附答案】,软测人必备!

1. 请描述什么是性能测试、什么是负载测试、什么是压力测试?【参考答案】性能测试:性能测试是和功能测试相对应的。根据用户场景进行的单个用户操作,是属于功能测试领域,主要是验证软件是否可以满足用户的功能需求。比如&#xff…

【刷题之路Ⅱ】LeetCode 11.盛水最多的容器

【刷题之路Ⅱ】LeetCode 11.盛水最多的容器一、题目描述二、解题1、方法1——暴力法1.1、思路分析1.2、代码实现2、方法2——双指针2.1、思路分析2.2、代码实现一、题目描述 原题连接: 11.盛水最多的容器 题目描述: 给定一个长度为 n 的整数数组 height…

44岁了,我从没想过在CSDN创作2年,会有这么大收获

1998年上的大学,02年毕业,就算从工作算起,我也有20余年的码龄生涯了。 但正式开启博文的写作,却是2021年开始的,差不多也就写了2年的博客,今天我来说说我在CSDN的感受和收获。 我是真的没想到,…

QT串口助手开发3串口开发

系列文章目录 QT串口助手开发3串口开发 QT串口助手开发3系列文章目录一、UI界面程序的编写二、发送框程序编写一、UI界面程序的编写 根据上文的未解决问题:我们打开串口按钮打开后只能选择关闭串口,所以这个是循环的过程 上文链接 所以按钮对应的槽函数…

【C++】搜索二叉树(保姆教程)

🍅二叉树底层是堆,之前学习的简单二叉树不是大堆就是小堆,今天是二叉树进阶,一定要好好掌握! 目录 ☃️1.搜索二叉树介绍 ☃️2.底层实现 ☃️3.key模型和key,value模型 ☃️1.搜索二叉树介绍 右>根&…

蜻蜓优化算法Python代码(详细注释)

1.代入例子,目标函数求最优解迭代过程:蜻蜓算法流程:蜻蜓算法(Dragonfly Algorithm)是一种基于种群的优化算法,灵感来自于蜻蜓的群集行为。该算法通过模拟蜻蜓之间的吸引力和斥力,以及蜻蜓的移动…

IDEA好用插件:MybatisX快速生成接口实体类mapper.xml映射文件

目录 1、在Idea中找到下载插件,Install,重启Idea 2、一个测试java文件,里面有com包 3、在Idea中添加数据库 --------以Oracle数据库为例 4、快速生成entity-service-mapper方法 5、查看生成的代码 6、自动生成(增删查改&#xff0…

C++ | 对比inline内联函数和宏的不同点

文章目录一、前言二、宏的优缺点分析1、概念回顾2、宏的缺点3、宏的优点三、inline内联函数1、概念2、特性①:空间换时间🎁趣味杂谈:庞大的游戏更新包3、特性②:inline实现机制4、特性③:inline的声明与定义反汇编观察…

【链表OJ题(八)】相交链表

​ ​📝个人主页:Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:数据结构 🎯长路漫漫浩浩,万事皆有期待 文章目录链表OJ题(八)8. 相交…

【C++笔试强训】第三十二天

🎇C笔试强训 博客主页:一起去看日落吗分享博主的C刷题日常,大家一起学习博主的能力有限,出现错误希望大家不吝赐教分享给大家一句我很喜欢的话:夜色难免微凉,前方必有曙光 🌞。 💦&a…

Spring Bean实例化和初始化的过程

承接上文Spring Bean生命周期应用程序在运行过程中能否去读取当前系统的环境变量或系统属性?这里涉及到一个非常重要的接口Environment,System.getenv,System.getProperties都是获取当前系统环境变量,Environment接口的实现类AbstractEnviro…

浏览器前进与后退的秘密——栈 (栈的理解与实现)

文章目录前言:浏览器与栈的纠缠如何理解“栈”?如何实现一个“栈”?基于数组的顺序栈基于链表的链式栈解答开篇🐱‍🐉作者简介:大家好,我是黑洞晓威,一名大二学生,希望和…