[全网最细数据结构完整版]第六篇:3分钟带你吃透栈并模拟实现

目录

1->栈的概念和结构

1.1栈的概念

 1.2栈的结构

 2->栈的实现

2.1定义关于栈的结构体和各种函数

2.2栈的初始化 STInit 函数

2.3栈的销毁 STDestroy 函数

2.4栈的插入操作 STPush 函数 

2.5栈的判断是否为空操作 STEmpty 函数 

2.6栈的删除操作 STPop 函数

2.7栈的取栈顶元素操作 STTop 函数

2.8求栈的大小即有效元素的个数 STSize 函数

3->测试下我们自己写的栈

4->您的专属鼓励师


1->栈的概念和结构

1.1栈的概念

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。

出栈:栈的删除操作叫做出栈。出数据也在栈顶

 1.2栈的结构

 

 2->栈的实现

栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小.

使用数组模拟原理:

 使用链表模拟原理:

 

// 下面是定长的静态栈的结构,实际中一般不实用,所以我们主要实现下面的支持动态增长的栈
typedef int STDataType;
#define N 10
typedef struct Stack
{
    STDataType _a[N];
    int _top; // 栈顶
}Stack;

2.1定义关于栈的结构体和各种函数

#pragma once
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>


typedef struct Stack
{
	int* _arr;//开辟在堆区上存储数据的数组
	int _top;//栈顶的下一个位置
	int _capacity;//栈的容量
}ST;



//1.栈初始化
void STInit(ST* pst);
//2.栈的销毁
void STDestroy(ST* pst);
//3.栈的插入操作
void STPush(ST* pst, int x);
//4.栈的删除操作
void STPop(ST* pst);
//5.取栈顶元素
int STTop(ST* pst);
//6.判断栈是否为空,空为true,非空为false
bool STEmpty(ST* pst);
//7.求栈的大小即有效元素的个数
int STSize(ST* pst);

2.2栈的初始化 STInit 函数

//1.栈初始化
void STInit(ST* pst)
{
	assert(pst);
	pst->_arr = NULL;
	pst->_capacity = 0;
	pst->_top = 0;//指向栈顶元素的下一个位置,类似于
				  //之前写的顺序表中的_size,指向未使用位置
}

2.3栈的销毁 STDestroy 函数

//2.栈的销毁
void STDestroy(ST* pst)
{
	assert(pst);

	free(pst->_arr);//清理位于堆上的数组
	pst->_arr = NULL;
	pst->_capacity = pst->_top = 0;
}

2.4栈的插入操作 STPush 函数 

//3.栈的插入操作
void STPush(ST* pst, int x)
{
	assert(pst);
	//插入数据之前判断一下容量是否足够,不够就扩容
	if (pst->_top == pst->_capacity)//容量满了,扩容
	{
		//刚开始插入给4个空间,否则就2倍扩容
		int newcapacity = (pst->_capacity == 0 ? 4 : pst->_capacity * 2);

		int* newarr = (int*)realloc(pst->_arr, newcapacity * sizeof(int));
		if (newarr == NULL)
		{
			perror("realloc failed");
			return;
		}
		pst->_arr = newarr;
		pst->_capacity = newcapacity;
	}
	//有容量了,插入数据
	pst->_arr[pst->_top] = x;
	pst->_top++;
}

2.5栈的判断是否为空操作 STEmpty 函数 

//4.判断栈是否为空,空为true,非空为false
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->_top == 0;
}

2.6栈的删除操作 STPop 函数

//5.栈的删除操作
void STPop(ST* pst)
{
	//首先你得有元素才能删除对吧
	assert(pst);
	assert(!STEmpty(pst));

	pst->_top--;
}

2.7栈的取栈顶元素操作 STTop 函数

//6.取栈顶元素
int STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));

	return pst->_arr[pst->_top - 1];
}

2.8求栈的大小即有效元素的个数 STSize 函数

//7.求栈的大小即有效元素的个数
int STSize(ST* pst)
{
	assert(pst);
	return pst->_top;
}

3->测试下我们自己写的栈

#include "Stack.h"



//1.测试栈插入,删除,取栈顶元素
void testStack1()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);

	while (!STEmpty(&st))
	{
		printf("%d : ",STTop(&st));
		STPop(&st);
	}
	STDestroy(&st);

}




int main()
{
	testStack1();
	return 0;
}

运行,看控制台输出:欧耶,我们自己写的栈可以正常运行

4->您的专属鼓励师

        有些事情,你永远都没有办法做到“顶尖”,因为智力跟不上.但是所有的事情,你都可以做到“高段”,因为它需要的是时间的累积和精力的打磨.不聪明与聪明之间的区别,是很微妙的.有时候我们只会通过一次两次的结果,来判断整个人、整件事,其实这是不明智的.从小,邻居和亲戚在谈论我的时候,都会觉得我很聪明。但是只有我自己知道,我从来没有聪明过,只是看上去比较聪明而已.

        修行之路确实枯燥,但是我们把问题搞懂以后就发现他是那样的美妙!一遍学不会没关系吖,多看几遍,我也是学了好多遍呢,小伙伴们肯定学的又快又好!!!最后希望写的内容对小伙伴们有所帮助,我写的如果有哪里不对的地方请在评论区或者私信指出来哦!让我们一起进步吖,任何疑问包括心情不好都可以找我聊聊,我很乐意当你的倾听者吖.   

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

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

相关文章

Uniapp底部导航栏设置(附带PS填充图标教程)

首先需要注册和登录ifconfont官网&#xff0c;然后创建项目添加需要的图标 创建和添加图标库请参考&#xff1a;Uniapp在Vue环境中引入iconfont图标库&#xff08;详细教程&#xff09; 打开iconfont官网&#xff0c;找到之前添加的图标库&#xff0c;下载png图片 如果需要的…

k8s图形化显示(KRM)

在master节点 kubectl get po -n kube-system 这个命令会列出 kube-system 命名空间中的所有 Pod 的状态和相关信息&#xff0c;比如名称、状态、重启次数等。 systemctl status kubelet #查看kubelet状态 yum install git #下载git命令 git clone https://gitee.com/duk…

FTP替代方案:FileLink内外网文件摆渡,助力企业安全高效文件传输

FTP&#xff08;文件传输协议&#xff09;一直是企业进行文件传输的标准解决方案。但随着网络安全威胁的不断增加和企业对于文件传输效率和安全性的更高要求&#xff0c;FTP逐渐显得力不从心。那么&#xff0c;如何安全、便捷地传输大文件和敏感数据呢&#xff1f;FileLink作为…

Python爬虫如何处理验证码与登录

Python爬虫如何处理验证码与登录 Python 爬虫在抓取需要登录的网站数据时&#xff0c;通常会遇到两个主要问题&#xff1a;登录验证和验证码处理。这些机制是网站用来防止自动化程序过度抓取数据的主要手段。本文将详细讲解如何使用 Python 处理登录与验证码&#xff0c;以便进…

论文2—《基于柔顺控制的智能神经导航手术机器人系统设计》文献阅读分析报告

论文报告&#xff1a;基于卷积神经网络的手术机器人控制系统设计 摘要 本研究针对机器人辅助微创手术中定向障碍和缺乏导航信息的问题&#xff0c;设计了一种智能控制导航手术机器人系统。该系统采用可靠和安全的定位技术、7自由度机械臂以及避免关节角度限制的逆运动学控制策…

活动推荐:百度智能云与NVIDIA联合主办千帆思享会「未来领航站-空间智能」,即将启幕!

科技热爱者们&#xff0c;上海集合&#xff01; 由百度智能云与NVIDIA联合主办的千帆思享会「未来领航站-空间智能」将于2024年11月22日&#xff08;周五&#xff09;14:00在上海启幕&#xff0c;大会聚焦AI大模型在游戏开发、动画和影视制作、GenAI&#xff08;图像、3D、视频…

动态迷宫(回溯法)

题目&#xff1a;今天蒜头君打算测试一下动态迷宫。迷宫中有一些动态楼梯&#xff0c;它们每隔一分钟就变动一次方向。比如下面的例子里&#xff0c;一开始楼梯在竖直方向&#xff0c;一分钟以后它移动到了水平方向&#xff0c;再过一分钟它又回到了竖直方向。蒜头君发现对他来…

C++ 【PCL】点云数据归一化、统一化处理

点云数据归一化、统一化&#xff0c;很重要&#xff0c;比如&#xff0c;你做完一个模型后&#xff0c;发现鼠标控制模型时&#xff0c;根本不是以中心点控制&#xff0c;就是因为数据没有归一化等 pcl::PointCloud<pcl::PointXYZ>::Ptr normialize(pcl::PointCloud<…

【深度学习】PromptFix:多功能AI修图

PromptFix:你来提示,我们修图 NeurIPS 2024 最近,在计算机视觉和图像处理领域,一个名为PromptFix的新项目引起了广泛关注。PromptFix是一个基于PyTorch实现的开源项目,旨在根据用户的自然语言指令,对受损或需要处理的图像进行智能修复和优化。 本文将详细介绍PromptFix…

淘宝商品详情API大揭秘:用Python开启探险之旅

淘宝&#xff0c;一个充满奇迹的丛林 在这个名为淘宝的丛林里&#xff0c;每一件商品都是一座神秘的宝藏。而我们&#xff0c;作为勇敢的探险家&#xff0c;将用Python这把瑞士军刀&#xff0c;去揭开这些宝藏的面纱。准备好了吗&#xff1f;让我们一起踏上这段奇妙的探险之旅…

【Android】名不符实的Window类

1.“名不符实”的Window类 Window 是一个窗口的概念&#xff0c;是所有视图的载体&#xff0c;不管是 Activity&#xff0c;Dialog&#xff0c;还是 Toast&#xff0c;他们的视图都是附加在 Window 上面的。例如在桌面显示一个悬浮窗&#xff0c;就需要用到 Window 来实现。Wi…

sql练习专场(一) (16-20)

第十六题&#xff1a;同时在线问题 create table sql1_16 (id int,stt string,edt string ) row format delimited fields terminated by ,; load data local inpath /home/homedata/sql_1/sql1_16.txt into table sql1_16;id stt edt 1001,2021-…

在vscode中开发运行uni-app项目

确保电脑已经安装配置好了node、vue等相关环境依赖 进行项目的创建 vue create -p dcloudio/uni-preset-vue 项目名 vue create -p dcloudio/uni-preset-vue uni-app 选择模版 这里选择【默认模版】 项目创建成功后在vscode中打开 第一次打开项目 pages.json 文件会报错&a…

多线程案例---阻塞队列

1. 阻塞队列 阻塞队列是一种特殊的队列&#xff0c;也遵守 " 先进先出 " 的原则。 阻塞队列是一种线程安全的数据结构&#xff0c;并且具有以下特性&#xff1a; 1. 当队列为满时&#xff0c;继续进行入队列操作就会阻塞&#xff0c;直到有其他线程从队列中取走元素…

【CANOE】【学习】【诊断功能】功能寻址和物理寻址

文章目录 前言一、功能寻址和物理寻址是什么&#xff1f;二、说明三、在脚本Capl里面进行使用 前言 这边文章我们将要学习和理解功能寻址和物理寻址。 一、功能寻址和物理寻址是什么&#xff1f; 可以很简单的一句话去理解&#xff1a; 物理寻址&#xff1a;是每个ECU的物理…

VisionPro —— CogIPOneImgeTool工具详解

CogIPOneImageTool工具主要用来对单张图像进行算法处理操作 CogIPOneImgeTool简介 CogIPOneImageTool 工具可完成高斯平滑、高通滤波和图像量化等基本图像处理操作。Image Processing One Image 工具编辑控件为此工具提供图形用户界面。 Image Processing Operations (图像处…

从分析Vue实例生命周期开始,剖析Vue页面跳转背后执行过程

文章目录 1.概要2.Vue实例生命周期3.生命周期函数解释4.存在父子组件情况页面执行过程5. 分析路由跳转页面执行过程6.扩展补充7.小结 1.概要 本文旨在分析Vue页面进行路由切换时&#xff0c;Vue背后的运行过程&#xff0c;旨在让大家更加清晰地明白Vue页面运行过程中钩子方法的…

43.第二阶段x86游戏实战2-提取游戏里面的lua

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 本次游戏没法给 内容参考于&#xff1a;微尘网络安全 本人写的内容纯属胡编乱造&#xff0c;全都是合成造假&#xff0c;仅仅只是为了娱乐&#xff0c;请不要…

是时候用开源降低AI落地门槛了

过去三十多年&#xff0c;从Linux到KVM&#xff0c;从OpenStack到Kubernetes&#xff0c;IT领域众多关键技术都来自开源。开源技术不仅大幅降低了IT成本&#xff0c;也降低了企业技术创新的门槛。 那么&#xff0c;在生成式AI时代&#xff0c;开源能够为AI带来什么&#xff1f;…

xlwings,让excel飞起来!

excel已经成为必不可少的数据处理软件&#xff0c;几乎天天在用。python有很多支持操作excel的第三方库&#xff0c;xlwings是其中一个。 关于xlwings xlwings开源免费&#xff0c;能够非常方便的读写Excel文件中的数据&#xff0c;并且能够进行单元格格式的修改。 xlwings还…