[数据结构]栈的实现与应用
文章目录
- 一、引言
- 二、栈的基本概念
- 1、栈是什么
- 2、栈的实现方式对比
- 3、函数栈帧
- 三、栈的实现
- 1、结构体定义
- 2、初始化
- 3、销毁
- 4、显示
- 5、数据操作
- 四、分析栈
- 1、优点
- 2、缺点
- 五、总结
- 1、练习题
- 2、源代码
一、引言
栈,作为一种基础且重要的数据结构,在计算机科学领域中有着广泛的应用。它不仅为函数调用提供了必要的支持,还在算法设计和问题解决中发挥着关键作用。本文将对栈的基本概念、实现方式以及函数栈帧进行详细的介绍和分析。
二、栈的基本概念
1、栈是什么
栈是一种特殊的线性数据结构,其只允许在固定的一端进行插入和删除操作。插入和删除的这一端被称为栈顶,而另一端则被称为栈底。栈遵循后进先出的原则,即最后插入的元素会最先被删除。这种特性使得栈在算法设计和问题解决中具有独特的优势。

2、栈的实现方式对比
- 数组实现:将数组的尾部充当栈顶,数据的插入与删除操作变得非常高效。同时数组的结构,使得其CPU高速缓存的命中率较高。唯一的缺陷就是,扩容或缩容会有一定的性能开销。
- 链表实现:采用单链表结构,将链表头部设为栈顶,数据的插入与删除操作同样能高效完成。但链表需要额外的存储空间来保存指针信息,且由于链表的结构,CPU高速缓存的命中率相对较低。此外,链表实现的复杂度相较于数组实现也更高一些。
3、函数栈帧
在函数调用过程中,系统会为每个函数分配一个栈帧。栈帧中存储了函数的局部变量、参数以及返回地址等信息。当函数执行完毕后,其栈帧会被销毁,从而释放占用的栈空间。函数栈帧的分配和销毁过程体现了栈的后进先出原则。
函数栈帧的存在使得函数调用具有嵌套性,即一个函数可以调用另一个函数,而被调用的函数又可以继续调用其他函数。这种嵌套调用关系通过栈来维护,确保了函数调用的正确性和稳定性。
三、栈的实现
1、结构体定义
首先,定义了栈的数据结构。栈使用动态数组来存储元素,同时记录了栈顶索引和栈的容量。
typedef int DataType;
typedef struct Stack {DataType* array;int top;int capacity;
}S;
2、初始化
接下来,实现了栈的初始化函数。该函数为栈分配内存,并初始化栈顶索引和容量。
void Init(S* ps, int capacity)
{assert(ps != NULL && capacity >= 0);DataType* pos = (DataType*)malloc(sizeof(DataType) * capacity);if (pos == NULL){fprintf(stderr, "内存分配失败");exit(EXIT_FAILURE);}ps->array = pos;ps->capacity = capacity;ps->top = -1;
}
3、销毁
实现了栈的销毁函数。该函数释放栈所占用的内存,并将栈的指针、容量和栈顶索引重置为初始状态。
void Destroy(S* ps)
{if (ps == NULL)return;free(ps->array);ps->array = NULL;ps->capacity = 0;ps->top = -1;
}
4、显示
实现了栈的显示函数。该函数遍历栈中的元素,并调用用户定义的打印函数来打印每个元素。
void Print(S* ps, void (*Prin)(DataType))
{assert(ps != NULL);for (int i = ps->top; i >= 0; i--){Prin(ps->array[i]);}printf("\n");
}
5、数据操作
void Push(S* ps, DataType data)
{assert(ps != NULL);if (ps->top == ps->capacity - 1){int capacity = ps->capacity == 0 ? 2 : ps->capacity * 2;DataType* pos = (DataType*)realloc(ps->array, sizeof(DataType) * capacity * 2);if (pos == NULL){fprintf(stderr, "内存分配失败");exit(EXIT_FAILURE);}ps->array = pos;ps->capacity = capacity;}ps->array[++(ps->top)] = data;
}void Pop(S* ps)
{assert(ps != NULL && ps->top != -1);if (ps->capacity > 64 && ps->top < ps->capacity / 3){int capacity = ps->capacity / 3;DataType* pos = (DataType*)realloc(ps->array, sizeof(DataType) * capacity);if (pos == NULL){fprintf(stderr, "内存分配失败");exit(EXIT_FAILURE);}ps->array = pos;ps->capacity = capacity;}ps->top--;
}DataType Top(S* ps)
{assert(ps != NULL);return ps->array[ps->top];
}
四、分析栈
1、优点
- 操作简便:栈提供了简洁的接口,如push(入栈)和pop(出栈),使得元素的操作非常直观和方便。
- 高效性:对于大多数栈实现,push和pop操作的时间复杂度均为O(1),保证了高效的元素访问速度。
- 应用场景广泛:栈在多种算法和数据结构中都有重要应用,如深度优先搜索(DFS)、表达式求值、括号匹配等。
2、缺点
- 访问限制:栈只允许在栈顶进行元素的插入和删除操作,无法直接访问栈内的其他元素,限制了其灵活性。
五、总结
1、练习题
- 有效的括号
- 最小栈
- 用栈操作构建数组
- 堆盘子
2、源代码
对于栈的源代码我已经开源在GItee:传送门。
相关文章:
[数据结构]栈的实现与应用
文章目录 一、引言二、栈的基本概念1、栈是什么2、栈的实现方式对比3、函数栈帧 三、栈的实现1、结构体定义2、初始化3、销毁4、显示5、数据操作 四、分析栈1、优点2、缺点 五、总结1、练习题2、源代码 一、引言 栈,作为一种基础且重要的数据结构,在计算…...
ESP32-C3 入门笔记04:gpio_key 按键 (ESP-IDF + VSCode)
1.GPIO简介 ESP32-C3是QFN32封装,GPIO引脚一共有22个,从GPIO0到GPIO21。 理论上,所有的IO都可以复用为任何外设功能,但有些引脚用作连接芯片内部FLASH或者外部FLASH功能时,官方不建议用作其它用途。 通过开发板的原…...
C语言(函数)—函数栈帧的创建和销毁
目录 前言 补充知识 一、函数线帧是什么? 二、函数线帧的实现(举例说明) 两数之和代码 编辑两数之和 汇编代码分析 执行第一条语句 执行第二条语句 执行第三条语句 执行第四、五、六条语句 执行第七条语句 执行第八、九、十条语句 执行第十…...
点餐小程序实战教程20广告管理
目录 1 创建数据源2 添加轮播容器3 创建变量4 绑定变量5 预览应用总结 一般餐厅需要有一些宣传,在我们的点餐页面可以在顶部加载广告位。广告主要是用轮播图的形式进行展示,本节我们介绍一下如果显示广告。 1 创建数据源 打开控制台,点击应用…...
市场上几个跨平台开发框架?
跨平台桌面应用开发框架是一种工具或框架,它允许开发者使用一种统一的代码库或语言来创建能够在多个操作系统上运行的桌面应用程序。传统上,开发者需要为每个操作系统编写不同的代码,使用不同的开发工具和语言。而跨平台桌面应用开发框架通过…...
同步和异步、引用、变量声明、全局变量
同步和异步 如果计算机足够快,任何资源的访问速度都像Cache一样,没有异步的必要。 编程语言的同步和异步 越早期的编程语言,支持语言级别的异步越欠缺。 JS提供某些操作的同步和异步函数,例如文件读取,fs.readFile和fs…...
2024年10月份实时获取地图边界数据方法,省市区县街道多级联动【附实时geoJson数据下载】
首先,来看下效果图 在线体验地址:https://geojson.hxkj.vip,并提供实时geoJson数据文件下载 可下载的数据包含省级geojson行政边界数据、市级geojson行政边界数据、区/县级geojson行政边界数据、省市区县街道行政编码四级联动数据࿰…...
@RequestMapping对不同参数的接收方式
1、简单参数 1、参数名与形参变量名相同,定义形参即可接收参数,且会自动进行类型转换。 RequestMapping("/simple")public String simpleParam(String name,int age){String username name;int userAge age;System.out.println(username&…...
机器学习_KNN(K近邻)算法_FaceBook_Location案例(附数据集下载链接)
Facebook_location_KNN 流程分析: 1.数据集获取(大型数据怎么获取? 放在电脑哪里? 算力怎么搞?) 2.基本数据处理(数据选取-确定特征值和目标值-分割数据集) 缩小数据范围 选择时间特征 去掉签到较少的地方 确定特征值和目标值 分割数据集 3.特征工程(特征预处理:标…...
【str_replace替换导致的绕过】
双写绕过 随便输入一个 usernameadmin&passwords 没有回显测试注入点 usernameadmin or 11%23&passwords 回显hello admin测试列数 usernameadmin order by 3%23&passwords测试回显位 usernameadmi union select 1,2,3%23&passwords 没有显示数据,推…...
如何用AI大模型提升挖洞速度
工具背景 越权漏洞在黑盒测试、SRC挖掘中几乎是必测的一项,但手工逐个测试越权漏洞往往会耗费大量时间,而自动化工具又存在大量误报, 基于此产生了AutorizePro, 那它是怎么提升效率一起来看看 AutorizePro 是一款专注于越权检测的 Burp 插件…...
两个数列问题
# 问题描述 给定长度分别为 n 和 m 的两个数列a[n]、b[m],和一个整数k。求|(a[i] - b[j])^2 - k^2|的最小值。 ## 输入格式 第一行有 2 个整数 n、m、k,分别表示数列 a、b 的长度,以及公式中的整数 k。 第二行有 n 个整数,表示…...
python中堆的用法
Python 堆(Headp) Python中堆是一种基于二叉树存储的数据结构。 主要应用场景: 对一个序列数据的操作基于排序的操作场景,例如序列数据基于最大值最小值进行的操作。 堆的数据结构: Python 中堆是一颗平衡二叉树&am…...
轮班管理新策略,提高效率与降低员工抱怨
良好轮班管理对企业关键,需提前计划、明确期望、保持灵活公平、加强沟通并利用轮班调度系统。ZohoPeople作为智能排班系统,提供轻松创建班次、自动更换、分配管理员、设置津贴及即时通知等功能,助力企业高效管理。 一、HR轮班管理的5大技巧 …...
spring-cloud-alibaba-nacos-config2023.0.1.*启动打印配置文件内容
**背景:**在开发测试过程中如果可以打印出配置文件的内容,方便确认配置是否准确;那么如何才可以打印出来呢; spring-cloud-alibaba-nacos-config 调整日志级别 logging:level:com.alibaba.cloud.nacos.configdata.NacosConfigD…...
数据结构:二叉树、堆
目录 一.树的概念 二、二叉树 1.二叉树的概念 2.特殊类型的二叉树 3.二叉树的性质 4.二叉树存储的结构 三、堆 1.堆的概念 2.堆的实现 Heap.h Heap.c 一.树的概念 注意,树的同一层中不能有关联,否侧就不是树了,就变成图了ÿ…...
hi3798mv100 linux 移植
# Linux开发环境搭建 ## uboot编译 1. 必须先安装gcc,要不然make 等命令无法使用 2. 配置arm 交叉编译链 # gcc sudo apt-get install gcc-9 gcc -v# 安装 Linaro gcc-arm-linux-gnueabihf,注意不是arm-linux-gnueabihf-gcc sudo apt-get install ar…...
Docker-Harbor概述及构建
文章目录 一、Docker Harbor概述1.Harbor的特性2.Harbor的构成 二、搭建本地私有仓库三、部署 Docker-Harbor 服务四、在其他客户端上传镜像五、维护管理Harbor 一、Docker Harbor概述 Harbor 是 VMware 公司开源的企业级 Docker Registry 项目,其目标是帮助用户迅…...
部署项目最新教程
3.3安装mysql 运行代码: yum install mysql 运行代码: yum install mysql-server 中间还是一样要输入y然后回车 运行代码: yum install mysql-devel 好,经过上面三步,mysql安装成功,现在启动mysql…...
linux证明变量扩展在路径名扩展之前执行
题目:怎么设计一组命令来证明变量扩展在路径名扩展之前执行。 为了证明变量扩展在路径名扩展之前执行,可以通过编写一个简单的 shell 脚本来观察这两个过程的顺序。我们可以使用以下步骤进行设计: 步骤 1:准备环境 在你选择的 …...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...
Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
LabVIEW双光子成像系统技术
双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制,展现出显著的技术优势: 深层组织穿透能力:适用于活体组织深度成像 高分辨率观测性能:满足微观结构的精细研究需求 低光毒性特点:减少对样本的损伤…...
