数据结构与算法—栈stack

news/2024/3/29 4:29:10/文章来源:https://blog.csdn.net/WANGYONGZIXUE/article/details/129207719

目录

栈的复杂度

空间复杂度O(1)

时间复杂度O(1)

栈的应用

1、栈在函数调用中的应用;

2、栈在求表达式的值的应用:

栈的实现


        后进先出,先进后出,只允许在一端插入和删除

从功能上,数组和链表可以代替栈。特定的数据结构是对特定场景的抽象,而且数组或链表暴露接口过多,自然容易出错。

符合先进后出特性的数据,可以使用栈

栈的形式

  • 1、顺序栈 数组实现
  • 2、链式栈 链表实现

栈的复杂度

空间复杂度O(1)

        出栈和入栈只需要两个临时变量存储空间,空间复杂度O(1),存n个数据,不能说时间复杂度O(n),因为n个空间是必须的。出来原本的空间,算法还需要额外的存储空间

时间复杂度O(1)

        时间复杂度 O(1),插入在满的时候会退化O(n),平摊也是O(1)

动态扩容的栈

栈满,申请更大数组,将原来数据搬到新数组中。

栈的应用

1、栈在函数调用中的应用;

        为什么函数调用要用“栈”来保存临时变量呢?用其他数据结构不行吗? 其实,我们不一定非要用栈来保存临时变量,只不过如果这个函数调用符合后进先出的特性,用栈这种数据结构来实现,是最顺理成章的选择。

        从调用函数进入被调用函数,对于数据来说,变化的是什么呢?是作用域。所以根本上,只要能保证每进入一个新的函数,都是一个新的作用域就可以。而要实现这个,用栈就非常方便。在进入被调用函数的时候,分配一段栈空间给这个函数的变量,在函数结束的时候,将栈顶复位,正好回到调用函数的作用域内。

2、栈在求表达式的值的应用:

编译器通过两个栈来实现。一个存值,一个存操作数。

比较运算符栈顶元素的优先级,高则将当前运算符压如栈;低或者相同,从运算符栈中取出栈顶运算符。从操作数中取出两个数,进行计算,计算后再将结果压入操作数栈,继续比较。

栈的实现

typedef struct _array_stack
{int size;int pos;int *array;
}arrayStack;   arrayStack *arrayStack_create(int size)
{arrayStack *pStack = NULL;pStack = (arrayStack *)malloc(sizeof(arrayStack));if(pStack == NULL)return NULL;pStack->size = size;pStack->pos = -1;pStack->array = (int *)malloc(sizeof(int)*size);if(pStack->array ==NULL){free(pStack);return NULL;}return pStack;
}int arrayStack_pop(arrayStack *pStack)
{int data = 0;if(arrayStack_is_empty(pStack)){return -1;}data = pStack->array[pStack->pos];pStack->pos--;return data;
}
int arrayStack_push(arrayStack *pStack,int data)
{if(arrayStack_is_full(pStack))return;pStack->pos++;pStack->array[pStack->pos] = data;return 0;
}

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

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

相关文章

【华为OD机试模拟题】用 C++ 实现 - 最多获得的短信条数(2023.Q1)

最近更新的博客 【华为OD机试模拟题】用 C++ 实现 - 分积木(2023.Q1) 【华为OD机试模拟题】用 C++ 实现 - 吃火锅(2023.Q1) 【华为OD机试模拟题】用 C++ 实现 - RSA 加密算法(2023.Q1) 【华为OD机试模拟题】用 C++ 实现 - 构成的正方形数量(2023.Q1) 【华为OD机试模拟…

MATLAB绘制雷达图/蜘蛛图

雷达图/蜘蛛图 1 方法一 函数来源为MATLAB | 如何使用MATLAB绘制雷达图(蜘蛛图) 1.1 调用函数 1.2 案例 2 方法二 函数来源为MATLAB帮助-spider_plot 2.1 调用函数 语法(Syntax): spider_plot(P)spider_plot(P, Name, Value, ...)h …

内网穿透常用方法系列总结

前言在内网渗透时,一个WebShell或CobaltStrike、Metasploit上线等,只是开端,更多是要内网横向移动,扩大战果,打到核心区域。但后渗透的前提是需要搭建一条通向内网的“专属通道”,才能进一步攻击。可实战中…

中国ETC行业市场规模及未来发展趋势

中国ETC行业市场规模及未来发展趋势编辑根据市场调研在线网发布的2023-2029年中国ETC行业发展策略分析及战略咨询研究报告分析:随着政府坚持实施绿色出行政策,ETC行业也受到了极大的支持。根据中国智能交通协会统计,2017年中国ETC行业市场规模…

高端装备的AC主轴头结构

加工机器人的AC主轴头和位置相关动力学特性1. 位置依赖动态特性及其复杂性2. AC主轴头2.1 常见主轴头摆角结构2.2 摆动机构3. 加装AC主轴头的作用和局限性4. 切削机器人的减速器类型5. 其他并联结构形式参考文献资料1. 位置依赖动态特性及其复杂性 However, FRF measurements …

【华为OD机试模拟题】用 C++ 实现 - 求解连续数列(2023.Q1)

最近更新的博客 【华为OD机试模拟题】用 C++ 实现 - 分积木(2023.Q1) 【华为OD机试模拟题】用 C++ 实现 - 吃火锅(2023.Q1) 【华为OD机试模拟题】用 C++ 实现 - RSA 加密算法(2023.Q1) 【华为OD机试模拟题】用 C++ 实现 - 构成的正方形数量(2023.Q1) 【华为OD机试模拟…

【异常】导出Excel异常This archive contains unclosed entries.

一、异常说明 二、定位问题代码 一看问题, 上下文都是与订单相关的内容。 查询代码的使用地方,发现出现在这个Mybatis的select语句中 查看备注,发现是订单物流,那就没跑了, 肯定是商城的物流模块出了问题 那是什么地…

Gin获取Response Body引发的OOM

有轮子尽量用轮子 😭 😭 😭 😭 😭 😭 我们在开发中基于Gin开发了一个Api网关,但上线后发现内存会在短时间内暴涨,然后被OOM kill掉。具体内存走势如下图: 放大其中一次 在…

软件测试之测试模型

软件测试的发展 1960年代是调试时期(测试即调试) 1960年 - 1978年 论证时期(软件测试是验证软件是正确的)和 1979年 - 1982年 破坏性测试时期(为了发现错误而执行程序的过程) 1983年起,软件测…

springboot+vue.js协同过滤算法之智能旅游推荐系统java

目 录 第一章 绪论 3 1.1课题背景 3 1.2课题研究的目的和意义 3 1.3 研究现状 4 1.4论文所做的主要工作 4 第二章 技术介绍 5 2.1B/S结构 5 2.2MySQL 介绍 5 2.3MySQL环境配置 6 第三章 系统分析与设计 8 3.1系统说明 8 3.2系统可行性分析…

xray API漏洞检测

一、介绍 一款功能强大的安全评估工具。国内长亭科技研发,xray 并不开源。目前支持的漏洞检测类型包括:XSS漏洞检测 (key: xss)SQL 注入检测 (key: sqldet)命令/代码注入检测 (key: cmd-injection)目录枚举 (key: dirscan)路径穿越检测 (key: path-traversal)XML 实…

【Linux】进程间通信(无名/有名管道及System V共享内存)

目录 一、通信的相关概念 二、管道(半双工) 1、管道的概念 三、匿名管道(fork实现,用于父子及血缘关系进程间通信) 1、匿名管道的使用 2、匿名管道的读写情况 3、管道的特征 4、基于匿名管道的进程池 四、命名…

【华为OD机试模拟题】用 C++ 实现 - 密室逃生游戏(2023.Q1)

最近更新的博客 华为OD机试 - 入栈出栈(C++) | 附带编码思路 【2023】 华为OD机试 - 箱子之形摆放(C++) | 附带编码思路 【2023】 华为OD机试 - 简易内存池 2(C++) | 附带编码思路 【2023】 华为OD机试 - 第 N 个排列(C++) | 附带编码思路 【2023】 华为OD机试 - 考古…

独家 | 6个Python数据科学库正在狂飙,你一定要学来提升文化素养

作者:Bex T翻译:wwl 校对:张睿毅本文约3200字,建议阅读8分钟 计算类数据科学库,已经不再局限在Pandas、NumPy、Scikit-learn之内了!动机2023年的开始,自然需要探索数据科学和机器学习的新趋势。…

【华为OD机试模拟题】用 C++ 实现 - 分积木(2023.Q1)

最近更新的博客 华为OD机试 - 入栈出栈(C++) | 附带编码思路 【2023】 华为OD机试 - 箱子之形摆放(C++) | 附带编码思路 【2023】 华为OD机试 - 简易内存池 2(C++) | 附带编码思路 【2023】 华为OD机试 - 第 N 个排列(C++) | 附带编码思路 【2023】 华为OD机试 - 考古…

Web Spider Ast-Hook 浏览器内存漫游-数据检索

文章目录一、资源下载二、通过npm安装anyproxy模块三、anyproxy的介绍以及基本使用1. anyproxy的功能介绍2. anyproxy的基本使用四、给浏览器挂代理五、实操极验demo案例总结提示:以下是本篇文章正文内容,下面案例可供参考 一、资源下载 Github&#x…

【华为OD机试模拟题】用 C++ 实现 - 符合条件的子串长度(2023.Q1)

最近更新的博客 华为OD机试 - 入栈出栈(C++) | 附带编码思路 【2023】 华为OD机试 - 箱子之形摆放(C++) | 附带编码思路 【2023】 华为OD机试 - 简易内存池 2(C++) | 附带编码思路 【2023】 华为OD机试 - 第 N 个排列(C++) | 附带编码思路 【2023】 华为OD机试 - 考古…

【华为OD机试模拟题】用 C++ 实现 - 矩阵最值(2023.Q1)

最近更新的博客 华为OD机试 - 入栈出栈(C++) | 附带编码思路 【2023】 华为OD机试 - 箱子之形摆放(C++) | 附带编码思路 【2023】 华为OD机试 - 简易内存池 2(C++) | 附带编码思路 【2023】 华为OD机试 - 第 N 个排列(C++) | 附带编码思路 【2023】 华为OD机试 - 考古…

【华为OD机试模拟题】用 C++ 实现 - 找数字(2023.Q1)

最近更新的博客 华为OD机试 - 入栈出栈(C++) | 附带编码思路 【2023】 华为OD机试 - 箱子之形摆放(C++) | 附带编码思路 【2023】 华为OD机试 - 简易内存池 2(C++) | 附带编码思路 【2023】 华为OD机试 - 第 N 个排列(C++) | 附带编码思路 【2023】 华为OD机试 - 考古…

MIND——Modality independent neighbourhood descriptor 模态无关邻域描述符

参考:https://blog.mbedded.ninja/programming/signal-processing/image-processing/image-registration/modality-independent-neighbourhood-descriptor-mind/《MIND: Modality independent neighbourhood descriptor for multi-modal deformable registration》论…