n2.堆栈

1.堆栈的介绍

表达式求值

在这里插入图片描述
因为不同的符号优先级不同,所以计算起来相对困难一些

后缀表达式

在这里插入图片描述
这里后缀表达式就用到了堆栈。它先从左向右进行扫描,碰到运算数就记住,碰到运算符就将离着这个运算符最近的两个运算数进行运算
堆栈是一种储存方法,能够按照所给的顺序记住运算数,当需要运算的时候,把排在最后的两个数进行运算,倒序输出。先放进去的后拿出来,后放进去的先拿出来——后入先出
在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述
时间复杂度是线性的O(N)
在这里插入图片描述
生活中,一堆放在一起的碗就是堆栈,在栈顶top拿碗,最后放的碗先拿出来使用。top是随着栈中的元素进行变化的。

堆栈的相关操作

在这里插入图片描述其中最重要的就是插入(入栈)和删除(出栈)操作。插入的时候要判断有没有满;出栈的时候要看是不是空

图解

在这里插入图片描述
其中push和pop可以交替进行,由此出栈的顺序也会大有不同
在这里插入图片描述注意并不是ABC所有的序列都可实现。

栈的顺序储存

在这里插入图片描述

#define MaxSize 最大个数
typedef struct SNode* Stack;
struct SNode{
int Top;
ElementType Data[MaxSize];
};

通常使用一个数组和指示Top来实现堆栈的顺序储存。其中Top是指一个整型变量,作为栈顶元素的下标[ ],记录栈顶的实时位置
*

  • 当栈空的时候,Top = -1,表示没有元素。Top
    一直表示栈顶的下标,当有元素入栈,Top值要+1。
    在这里插入图片描述

入栈

入栈操作需要先进行判断栈是否已满

void Push(Stack PtrS, int item)
{
	if ( PtrS == NULL || PtrS->Top == MaxSize - 1)
	{
		printf("%s","栈已经满了,无法入栈");
	}
	else
	{
		PtrS->Data[++(PtrS->Top)] = item;//使用前自增运算符,简洁
	}
}

出栈

返回下标为Top的元素的值,Top值-1。因为实现遍历数组等操作的时候,通常以Top为标准界限,Top-1就相当于删除了原来在栈顶的那个元素。出栈前要先检查堆栈空不空。

ElementType Pop(Stack PtrS)
{
	if (PtrS->Top == -1)
	{
	printf("栈已经空了,无法再删除");
	}
	else
	{
	return PtrS->Data[(PtrS->Top)--];
	}
}

一个数组实现两个堆栈

使用一个数组实现两个堆栈,要求最大可能的利用空间,只要数组还有空间就允许入栈操作:
最优解是两个栈从两头开始向中间入栈,两个栈共用空间,只要中间有空间就可以入栈。当两个栈的指针相遇的时候表示数组空间已经满了

#define MaxSize 自定义最大数
struct DStack{
	int Top1;
	int Top2;
	ElementType Data[MaxSize];
}S;

Top1 = -1;Top2 = MaxSize 的时候表示两个栈都是空的

插入

将变量item放到某一个堆栈中去

void Push(struck DStack* PtrS,int item,int Tag)//如果Tag=1,放到第一个堆栈...
{//理解1:计算:(MaxSize - Top2) + (Top1 + 1) > MaxSize 时,堆栈就满了
//理解2:当两个Top挨在一起的时候堆栈就满了
	if( (PtrS->Top1 + 1) > (PtrS->Top2) )
	{
		printf("堆栈已经满了,无法入栈");
	}
	else
	{
		if(Tag == 1)//插入哪个堆栈判断
			PtrS->Data[++(PtrS->Top1)] = item;
		else
			PtrS->Data[--(PtrS->Top2)] = item;
	}
}

删除

同样的首先要进行判断哪个堆栈,接下来判断对应的堆栈空不空。

ElementType Pop(int Tag,struct DStack PtrS)
{
	if(Tag == 1)
	{
		if(PtrS->Top1 == -1)
			printf("第一个堆栈是空的,无法Pop);
		else
			 return PtrS->Data[(PtrS->Top1)--];//往左边挪
	}
	else 
	{
		if(PtrS->Top2 == -1)
			printf("第二个堆栈是空的,无法Pop);
		else
			 return PtrS->Data[(PtrS->Top2)++];//往右边挪
	}
}

栈的链式储存(链栈)

在这里插入图片描述
因为单链表只能从前向后进行检索,不能后退,所以应该将链表的头作为Top

初始化

typedef struct SNode* Stack;
struct SNode{
	ElementType Data;
	Stack Next;
};

  • 可以加一个栈头指针,它不代表任何一个元素,Data部分是空的,它的Next部分充当指示作用,使用这个节点可以找到链表中的具体某个元素,便于插入和删除。
Stack CreateStack()//建立一个空的堆栈,只是有个头
{
	Stack S = malloc(sizeof(struct SNode));
	S->Next = NULL;
	return S;
}

插入

void Push(ElementType item,Stack S)
{//无需判断满不满,只要申请空间即可
	Stack TmpCell = malloc(sizeof(struct SNode));
	TmpCell->Data = item;
	if(S->Next)//是得需要判断S之后有没有节点
		TemCell->Next = S->Next;
	S->Next = TmpCell;
}

图解:请添加图片描述
关于链表指针的新思考:
这里的S是作为一个堆栈头结点,没有Data部分。其实可以把结构指针变量当做名字,它包括两部分:Data部分和Next部分。比如头指针(结构指针)S,可以认为S->DataS->Next属于性质不太一样的访问,一个是访问自己本身的储存,另一个是访问指向的下一个节点。S->Data 其实就是 结点1S->Next->Data = 节点1->Data.

删除

删除并返回堆栈S的栈顶元素Data部分的值

ElementType Pop(Stack S)
{
	if(!S->Next)//没有节点存在(判断空不空)
		printf("堆栈为空,无法出栈");
	Stack One = S->Next;//注意删除的节点一定要释放它的空间,所以要把他赋值给一个指针变量One
	ElementType Copy = One->Data;
	if(!One->Next)//只有一个节点存在
		{
			S->Next = NULL;
			free(One);
		}
	else//至少存在两个节点
	{
		S->Next = One->Next;
		free(One);
	}
	return Copy;
}

堆栈应用

表达式求值

根据后缀表达式求值更好地理解堆栈
在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述

堆栈的其他应用

  • 函数的调用及递归实现
    顺序储存,倒序返回

  • 深度优先搜索

  • 回溯算法
    比如走迷宫,这一步进行到下一步有好多条路,当选择的路走不通的时候,需要返回上一步再进行试探。

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

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

相关文章

六、从零实战企业级K8S本地部署ThingsBoard专业版集群

1、从 docker hub 拉取 ThingsBoard PE 映像(所有节点) 1.1、查看k8s信息(主节点) kubectl cluster-info #查看k8s集群信息 kubectl get node #查看节点信息 kubectl get pod -A #查看内部组件1.2、从 d…

Docker:探索容器化技术,重塑云计算时代应用交付与管理

一,引言 在云计算时代,随着开发者逐步将应用迁移至云端以减轻硬件管理负担,软件配置与环境一致性问题日益凸显。Docker的横空出世,恰好为软件开发者带来了全新的解决方案,它革新了软件的打包、分发和管理方式&#xff…

【C++第二阶段】继承多态电脑组装实例

你好你好! 以下内容仅为当前认识,可能有不足之处,欢迎讨论! 文章目录 继承继承语法继承方式继承中的对象模型继承中构造和析构顺序同名成员处理同名静态成员处理多继承语法菱形继承问题 多态多态基本概念重写&重载 多态原理多…

中仕公考:不同省事业编考试内容一样吗?

在各省份的事业单位公开招聘过程中,考试内容是不一样的。虽然每一年都有很多省份参加事业编联考,且这些联考的考试日期相同,但是考试内容并不一样。各省将依据当地的特定情况来设计考试题目,其中会涉及到与本省的地理、经济、文化…

文章分享:《呼吸道传染病标本采集及检测专家共识》

【摘要】呼吸道传染病临床特点多表现为发热和(或)呼吸道症状,病原学组成复杂,标本类型选择多样,如何从发热伴呼吸道症候群患者中早期正确识别出潜在呼吸道传染病患者是防控的关键环节。增强医务人员对呼吸道传染病临床…

【现代C++】Lambda表达式

在现代C中,Lambda表达式提供了定义匿名函数对象的能力,这在很多场合,如STL算法、线程构造函数、事件处理等,都非常有用。Lambda表达式使得函数定义更加灵活和简洁。 1. 基本语法 Lambda表达式的基本形式包括一个捕获列表、参数列…

【微信小程序】流量主-激励视频(激励广告)下发策略,每天三次免费体验,然后再次点击触发激励视频,当日不再触发。

如题: 允许用户有三次体验效果,然后弹出激励视频弹窗,之后当日不再弹出。 体验小程序: /*** 判断当前项目当天是否点击超过3次,触发广告效果。* 若,当天低于三次,则新增,若高于…

未来电商怎么走,是腾讯视频号,还是抖音小店?你更看好谁?

大家好,我是电商花花。 现在想做一些项目,做些生意基本上就离不开电商,网络这么发达,直播短视频这么火,未来的发展依然是直播电商。 现在线下很多实体店都被电商所冲击,而且不少实体店也都在网上开店卖货…

Spring 整合 Log4j2日志框架

1. Log4j2日志概述 在项目开发中,日志十分的重要,不管是记录运行情况还是定位线上问题,都离不开对日志的分析。日志记录了系统行为的时间、地点、状态等相关信息,能够帮助我们了解并监控系统状态,在发生错误或者接近某…

【面试HOT200】数组篇

系列综述: 💞目的:本系列是个人整理为了秋招面试coding部分的,整理期间苛求每个算法题目,平衡可读性与代码性能(leetcode运行复杂度均打败80%以上)。 🥰来源:材料主要源于…

linux删除 buff/cache缓存

1.查看当前内存占用 free -h如图,缓存占用了将近9G,接下来进行清理 释放页缓存 echo 1 > /proc/sys/vm/drop_caches释放dentries和inodes echo 2 > /proc/sys/vm/drop_caches释放所有缓存 echo 3 > /proc/sys/vm/drop_caches再次查看&#…

MQ

目录 MQ优点 异步 解耦 削峰填谷 mq的缺点 MQ常见的几种模式 Kafka、ActiveMQ、RabbitMQ、RocketMQ 区别 MQ优点 mq是一种常见的中间件,在项目中经常用到,它具有异步、解耦、削峰填谷的作用。 异步 比如下单流程,A服务—>B服务&a…

为什么称FreeRTOS为轻量级OS,和Linux相比,有哪些具体的区别?

要理解它们,就要看这些最终的概念是怎么来的,其实这些都是在不同资源(硬件)上处理不同场景问题所得的结果。 FreeRTOS一般跑在几十Mhz,几十KB的硬件上,比如Cortex-M系列MCU上,资源很有限&#…

论文精读--GPT4

现有的所有模型都无法做到在线学习,能力有限,而让大模型拥有一个tools工具库,则可以使大模型变成一个交互式的工具去协调调用API完成任务,同时GPT4还联网了,可以不断地更新自己的知识库 多模态模型,接受文…

面经分享(Flask,轻量级Web框架)

1. Flask的核心特点 a. 轻量级:核心简洁,只提供了基本的功能,其他高级功能可以通过插件或扩展来添加。 b. 灵活性:允许开发者选择适合自己项目的组件和工具,没有强制的项目结构和设计模式。 c. 易于扩展:提…

JVM 内存溢出排查

说明:记录一次JVM内存溢出的排查过程; 场景 项目开发完成后,首次提交到测试环境。测试、产品同事反馈页面先是操作响应慢,抛出超时异常,最后直接无法使用。查看日志后得知是内存溢出。 重启服务后,我对前…

接口测试实战教程(加密解密攻防)

🍅 视频学习:文末有免费的配套视频可观看 🍅 关注公众号【互联网杂货铺】,回复 1 ,免费获取软件测试全套资料,资料在手,涨薪更快 一、对称加密 对称加密算法是共享密钥加密算法,在加…

RuntimeError: Error compiling objects for extension虚拟环境和系统环境——添加、删除、修改环境变量

前言:因为一个报错RuntimeError: Error compiling objects for extension 没有配置cl.exe环境变量,我的应用场景是需要搞定虚拟环境变量配置 RuntimeError: Error compiling objects for extension手把手带你解决(超详细)-CSDN博…

Mybatis 之 useGeneratedKeys

数据库中主键基本都设置为自增,当我们要插入一条数据想要获取这条数据的 Id 时,就可使用 Mybatis 中的 useGeneratedKeys 属性。 背景 这里以 苍穹外卖 中的 新增菜品 功能为例,有 菜品表(dish table)和 口味表(dish_flavor table)&#xf…

HTML标签之有序列表,无序列表,自定义链表

无序列表 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthdevice-width, i…