栈--C语言实现数据结构

在这里插入图片描述

本期带大家一起用C语言实现栈🌈🌈🌈

一、栈的概念🌎

栈是一种常见的数据结构,它遵循后进先出(Last In, First Out)的原则。可以将其类比为现实生活中的一摞书或者一叠盘子。

栈由一个连续的内存区域组成,可以存储一系列的元素。在栈的一端称为栈顶,另一端称为栈底。

栈的主要操作包括入栈(Push)和出栈(Pop):

入栈操作将元素放置在栈顶,新增加的元素成为新的栈顶。
出栈操作将栈顶的元素移除,并将其下面的元素成为新的栈顶。
由于栈的特性,只能访问、插入和删除栈顶元素,不支持在任意位置进行操作。

栈具有局部性原理,即后进入栈的元素会先被访问到,而先进入栈的元素则需要等待后面的元素出栈才能被访问到。

栈常用于函数调用、递归算法、表达式求值、括号匹配等场景。

二、栈的操作流程

在这里插入图片描述

三、栈的结构

栈的话,我们可以使用顺序栈链表栈来实现

1.对于顺序栈而言:
方便的便是尾删和尾插了,因为有记录了下标,那么便可以很快的访问到最后一个元素 ,不需要经过遍历
在这里插入图片描述
2.对于链表栈而言:
对于链表而言,尤其是 单链表,尾部的插入删除是很麻烦的。但是 单链表 的头插和头删就很方便,所以可以把 单链表的头部 作为栈顶,单链表的尾部 作为 栈底。 插入数据的时候我们需要选择头插数据
在这里插入图片描述

如果对于双向链表而言,那么就是随便选了,毕竟双向链表无论哪头插入删除数据都很方便

那么对于 顺序栈链式栈 ,那个更加好呢?那必定是 顺序栈,因为使用顺序栈的 尾插尾删非常方便, 且 cpu缓存利用率也更高。而且对于顺序栈实现起来相对简单,所以我们接下来就实现 顺序栈

四、栈的实现

4.1 结构设计

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;     //栈顶元素的下一个  或者 栈顶的下标
	int capacity;
}ST;

这里的 top 我们需要好好理解一下。当top的初始值不同时,top可以表示 栈顶的下一个位置的下标 或 栈顶下标

1.当 top = 0,top 表示栈顶的下一个位置的下标:
在这里插入图片描述

top一开始等于0的时候,先压栈,top再++

2、当top=-1的时候,top 表示栈顶元素的下标:

在这里插入图片描述

top=-1的时候,++top,再压栈

4.2 初始化栈

因为我们实现的是顺序栈,因此和顺序表的初始化是一样的
我们创建一个ST s,然后传s的地址即可

void STInit(ST* ps)
{

	assert(ps);

	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;

}

这里我们将top置为0,表示下一个数据的下标

4.3压栈

压栈的话,我们需要判断一下我们的我们的容量capacity是否和我们的ttop相等
如果相等的话,那么就扩容操作

void STPush(ST* ps,STDataType x)
{

	assert(ps);

	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity*sizeof(STDataType));

		if (tmp == NULL)
		{
			perror("realloc :fail");
			return;
		}

		ps->a = tmp;

		ps->capacity = newcapacity;

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

}

在这里插入图片描述

4.4 出栈

出栈的话是很简单的,只需要将我们的top--就可以了
不过需要注意的是,如果我们的栈为空的话,那我们就不进行出栈操作

void STPop(ST* ps)
{

	assert(ps);
	assert(!STEmpty(ps));

	ps->top--;
}

在这里插入图片描述

4.5 获取栈顶元素

获取栈顶元素的话,我们同样需要判断栈是否为空
如果为空的话,那我们就不去获取栈顶元素的操作
如果不为空,那我们返回下标为top-1那个元素

STDataType STTop(ST* ps)
{

	assert(ps);

	return ps->a[ps->top - 1];

}

4.6 栈中数据的个数

栈中数据个数的话比较简单,只需要返回我们的top即可

int STSize(ST* ps)
{
	assert(ps);

	return  ps->top;

}

4.7 判断栈是否为空

判断栈是否为空的话,我们只需要返回top==0的真假就行

bool STEmpty(ST* ps)
{

	return ps->top == 0;
}

4.8 栈的销毁

对于栈的销毁,那么我们就只需要释放动态开辟的空间,将指针置空。并将 capacity 和 top 两个变量置 0即可

void STDestroy(ST* ps)
{
	assert(ps);

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

	ps->top = 0;
}

5、有效的括号

链接:有效的括号
在这里插入图片描述
看完题目之后,我们可以有以下的思路
我们可以让左括号压栈
当我们遇到右括号的时候,如果我们的栈不为空的话,我们就拿栈顶的元素去和右括号比较,如果括号不匹配的话,我们先销毁一下我们的栈,然后再去返回false
如果我们的栈为空的话,那我们就先销毁一下我们的栈,然后直接返回false
当然当我们的括号匹配的时候,我们就让s➕➕和删去栈顶元素,然后再去进行下一轮的判断
当我们的括号全部匹配完了之后,如果我们的栈不为空的话,我们就返回false,不然就反回true,并且销毁栈

在这里插入图片描述

在这里插入图片描述
易错点:
遍历结束,栈不为空
在这里插入图片描述

6. 感谢与交流✅

🌹🌹🌹如果大家通过本篇博客收获了,对顺序表有了新的了解的话
那么希望支持一下哦如果还有不明白的,疑惑的话,或者什么比较好的建议的话,可以发到评论区,
我们一起解决,共同进步 ❗️❗️❗️
最后谢谢大家❗️❗️❗️💯💯💯

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

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

相关文章

Mac环境下安装nginx并本地部署项目

1、前提 必须安装了homebrew,可在终端输入命令brew -v查看是否已经安装,如果输入指令出现版本号说明已经安装成功 如果未安装先安装(homebrew官网地址) /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/H…

神经网络之VGG

目录 1.VGG的简单介绍 1.2结构图 3.参考代码 VGGNet-16 架构:完整指南 |卡格尔 (kaggle.com) 1.VGG的简单介绍 经典卷积神经网络的基本组成部分是下面的这个序列: 带填充以保持分辨率的卷积层; 非线性激活函数,如ReLU&a…

1、Redis入门与应用

Redis入门与应用 Redis的技术全景 Redis一个开源的基于键值对(Key-Value)NoSQL数据库。使用ANSI C语言编写、支持网络、基于内存但支持持久化。性能优秀,并提供多种语言的API。 我们要首先理解一点,我们把Redis称为KV数据库&am…

优化SQL查询实现高效数据检索(一)

大家好,SQL(结构化查询语言)可以帮助大家从数据库中收集数据,它是专为此而设计的,换句话说,它使用行和列来处理数据,让使用者能够使用SQL查询来操作数据库中的数据。 SQL查询 SQL查询是一系列…

Nginx Linux安装

参考 : http://test.runoob.com/w3cnote/nginx-install-and-config.html 点击跳转 下载安装包 - 这里选择的是 nginx-1.6.3 pgp 网址 : http://nginx.org/en/download.html 点击跳转 2. 上传Linux - 这里新建了临时文件夹 mkdir /usr/local/tmp 3. 解压 tar -zxvf nginx-1.6.…

Springcloud基础(4)-Ribbon负载均衡

负载均衡 1. Ribbon简单描述2. 在SpringCloud中查看相关处理源码3. ribbon的默认策略,懒加载3. 实操中的相关问题 1. Ribbon简单描述 Spring Cloud Ribbon 是一套基于 Netflix Ribbon 实现的客户端负载均衡和服务调用工具。Ribbon是Netflix发布的开源项目&#xff0…

手机快充协议

高通:QC2.0、QC3.0、QC3.5、QC4.0、QC5.0、 FCP、SCP、AFC、SFCP、 MTKPE1.1/PE2.0/PE3.0、TYPEC、PD2.0、PD3.0/3.1、VOOC 支持 PD3.0/PD2.0 支持 QC3.0/QC2.0 支持 AFC 支持 FCP 支持 PE2.0/PE1.1 联发科的PE(Pump Express)/PE 支持 SFCP 在PP…

火车头小发猫AI伪原创[php源码]

对于大多数站长来说&#xff0c;有点困难&#xff0c;但是如果他们不知道如何原创&#xff0c;我们不知道如何伪原创吗&#xff1f;我把我常用的伪原创的方法列出来&#xff0c;希望对大家有所帮助。 使用教程&#xff1a;火车头采集器AI伪原创 <?php header("Conte…

【面试】Hbase

逻辑模型 1 NameSpace 命名空间&#xff0c;类似于关系型数据库的database概念&#xff0c;每个命名空间下有多个表。Hbase有两个自带的命名空间,分别是hbase和default, hbase中存放的是HBase内置的表, default表是用户默认使用的命名空间。 2 Region 类似于关系型数据库的表…

资深测试整理,APP专项测试方法总结,看这篇就够了...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 APP专项测试 1、…

Python启动TCP服务并监听连接,从客户端发送消息

下面是一个简单的例子&#xff0c;演示如何在Python中启动TCP服务并监听连接&#xff0c;以及如何从客户端发送消息&#xff1a; TCP服务端代码&#xff1a; import socketHOST 192.168.6.211 PORT 8888server_socket socket.socket(socket.AF_INET, socket.SOCK_STREAM) …

【QT】QT搭建OpenCV环境

QT/OpenCV 01、开始之前02、QT03、CMake04、OpenCV05、配置06、测试 01、开始之前 本文版本&#xff1a; 1、QT&#xff1a;Based on Qt 5.12.2 (MSVC 2017, 32 bit)&#xff0c;编译方式是MinGW 2、CMake&#xff1a;cmake-3.27.0-rc4-windows-x86_64.msi 3、OpenCV&#xff1…

深度学习——优化器Optimizer

代码以及详细注释&#xff1a; import torch import torch.utils.data as Data import torch.nn.functional as F import matplotlib.pyplot as plt# torch.manual_seed(1) # reproducible """超参数 """ # 学习率 LR 0.01 # 批大小 BATCH_…

什么是RPC并实现一个简单的RPC

1. 基本的RPC模型 主要介绍RPC是什么&#xff0c;基本的RPC代码&#xff0c;RPC与REST的区别&#xff0c;gRPC的使用 1.1 基本概念 RPC&#xff08;Remote Procedure Call&#xff09;远程过程调用&#xff0c;简单的理解是一个节点请求另一个节点提供的服务本地过程调用&am…

详解Jenkins配置邮件通知

前言 这几天Darren洋在使用Jenkins定时构建jmeter脚本中&#xff0c;要用到邮箱配置&#xff0c;故记录之。 一、Jenkins默认邮箱通知 这里填好smtp服务器地址和邮箱后缀&#xff0c;这样下面的账号就不用加邮箱后缀了。 网易邮箱设置以下我就不说废话文学了&#xff0c;直接上…

智能优化算法——哈里鹰算法(Matlab实现)

目录 1 算法简介 2 算法数学模型 2.1.全局探索阶段 2.2 过渡阶段 2.3.局部开采阶段 3 求解步骤与程序框图 3.1 步骤 3.2 程序框图 4 matlab代码及结果 4.1 代码 4.2 结果 1 算法简介 哈里斯鹰算法(Harris Hawks Optimization&#xff0c;HHO)&#xff0c;是由Ali Asghar Heid…

【深度剖析】 快速排序为什么不稳定?!

文章目录 零、前言一、快速排序的步骤原理二、什么是稳定性&#xff1f;三、不稳定的地方在哪里&#xff1f;四、怎么让快速排序变得稳定&#xff1f;1、采用双指针的快速排序A 思路简述B 参考代码 :C 算法分析 2、基于递归的快速排序A 思路简述B 参考代码C 算法分析 3、采用归…

【K8S系列】深入解析K8S调度

序言 做一件事并不难&#xff0c;难的是在于坚持。坚持一下也不难&#xff0c;难的是坚持到底。 文章标记颜色说明&#xff1a; 黄色&#xff1a;重要标题红色&#xff1a;用来标记结论绿色&#xff1a;用来标记论点蓝色&#xff1a;用来标记论点 Kubernetes (k8s) 是一个容器编…

使用docker部署rancher并导入k8s集群

前言&#xff1a;鉴于我已经部署了k8s集群&#xff0c;那就在部署rancher一台用于管理k8s&#xff0c;这是一台单独的虚拟环境&#xff0c;之前在k8s的master节点上进行部署并未成功&#xff0c;有可能端口冲突了&#xff0c;这个问题我并没有深究&#xff0c;如果非要通过修改…

C#使用Chart进行统计,切换不同的图表类型

WindowsForm应用程序中Chart图表控件所属的命名空间&#xff1a; Chart 命名空间&#xff1a; System.Windows.Forms.DataVisualization.Charting 对应的dll路径&#xff1a; C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework\.NETFramework\v4.6.1\Syst…