【数据结构与算法】使用数组实现栈:原理、步骤与应用
💓 博客主页:倔强的石头的CSDN主页
📝Gitee主页:倔强的石头的gitee主页
⏩ 文章专栏:《数据结构与算法》
期待您的关注
目录
一、引言
🎄栈(Stack)是什么?
🎄为什么使用数组实现栈?
二、定义栈结构
🎄栈的结构
🎄栈顶位置的指向
三、实现栈的基本操作
🍃初始化
🍃销毁
🍃入栈
🍃出栈
🍃查看栈顶元素
🍃对栈判空
🍃获取有效数据个数
四、使用数组实现栈的C语言代码
stack.h 栈的头文件
stack.c 栈的实现源文件
test.c 主函数测试文件
测试结果
五、栈的应用
六、总结
一、引言
🎄栈(Stack)是什么?
- 栈是一种后进先出(LIFO, Last In First Out)的数据结构。
- 栈是一种只能在一端进行插入和删除操作的线性表。
- 允许进行插入和删除操作的一端称为栈顶(top),另一端称为栈底(bottom)。
- 栈中没有元素时,称为空栈。
- 栈的基本操作包括:push(入栈)、pop(出栈)、peek(查看栈顶元素)和isEmpty(判断栈是否为空)等。
🎄为什么使用数组实现栈?
- 数组是一种线性数据结构,能够连续存储数据,且通过索引可以方便地访问任意位置的元素。
- 因为栈只在栈顶增删,所以基于数组实现,既避免了插入需要移动数据的劣势,又保持了数组访问数据的优势,可以实现高效的栈操作。
二、定义栈结构
🎄栈的结构
- 指向数组的指针(动态开辟的空间)
- 标记栈顶位置的变量 top
- 标记栈的大小的变量 capacity
// 支持动态增长的栈
typedef int STDataType;//对数据类型重命名,方便后期修改类型
typedef struct Stack
{STDataType* a;int top; // 栈顶int capacity; // 容量
}Stack;//定义结构同时重命名
🎄栈顶位置的指向
需要注意的是:top的指向应该始终保持一致性
1.如果top指向栈顶元素,初始不能为0,应该指向-1
2.如果top初始为0,其应该指向栈顶元素的下一个元素
对应的判定栈满和栈空有所不同
三、实现栈的基本操作
🍃初始化
- 对形参判空
- 数组指针初始指向空
- top和capacity初始化为0(这里top指向的是栈顶元素的下一个位置)
// 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;
}
🍃销毁
- 对形参判空
- 释放数组空间
- 数组指针指向空
- top和capacity改为0
// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}
🍃入栈
判空
判断是否需要扩容(top和capacity相等)
扩容步骤: 空间二倍增长 ,更新数组指针和容量数据插入到top位置,top位置++
// 入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);//判断是否需要扩容if (ps->top == ps->capacity){int newcapa = ps->capacity == 0 ? 4 : 2 * (ps->capacity);STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapa);if (tmp == NULL){perror("realloc\n");exit(1);}ps->a = tmp;ps->capacity = newcapa;}//确定空间足够之后再插入数据ps->a[ps->top] = data;ps->top++;
}
🍃出栈
- 对形参判空
- 对栈判空
- top--
(该方法对于栈只存在一个元素的情况也可以正确处理)
// 出栈
void StackPop(Stack* ps)
{assert(ps);assert(ps->top);ps->top--;
}
注意:
即使函数只有一两条语句也还是建议封装成函数,这样可以提高程序的可维护性和可读性
🍃查看栈顶元素
- 对形参判空
- 对栈判空
- 返回top前一个位置的元素
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps->top);return ps->a[ps->top-1];
}
🍃对栈判空
- 对形参判空
- 返回top==0的结果(因为这里top指向的是栈顶元素的下一个元素,所以栈空时top==0)
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}
🍃获取有效数据个数
- 对形参判空
- 返回top (top对应的下标是栈顶的下一个元素,top就是元素的个数)
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}
四、使用数组实现栈的C语言代码
stack.h 栈的头文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>// 支持动态增长的栈
typedef int STDataType;//对数据类型重命名,方便后期修改类型
typedef struct Stack
{STDataType* a;int top; // 栈顶int capacity; // 容量
}Stack;//定义结构同时重命名// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
stack.c 栈的实现源文件
#include"stack.h"// 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;
}// 入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);//判断是否需要扩容if (ps->top == ps->capacity){int newcapa = ps->capacity == 0 ? 4 : 2 * (ps->capacity);STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapa);if (tmp == NULL){perror("realloc\n");exit(1);}ps->a = tmp;ps->capacity = newcapa;}//确定空间足够之后再插入数据ps->a[ps->top] = data;ps->top++;
}// 出栈
void StackPop(Stack* ps)
{assert(ps);assert(ps->top);ps->top--;
}// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps->top);return ps->a[ps->top-1];
}// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}
test.c 主函数测试文件
#include"stack.h"void test1()
{Stack st ;StackInit(&st);if (StackEmpty(&st)){printf("栈空\n");}else{printf("栈非空\n");}StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);if (StackEmpty(&st)){printf("栈空\n");}else{printf("栈非空\n");}printf("栈中元素个数:%d\n", StackSize(&st));printf("%d\n", StackTop(&st));StackPop(&st);printf("%d\n", StackTop(&st));StackPop(&st);printf("%d\n", StackTop(&st));StackPop(&st);printf("%d\n", StackTop(&st));StackPop(&st);if (StackEmpty(&st)){printf("栈空\n");}else{printf("栈非空\n");}StackDestroy(&st);}int main()
{test1();return 0;
}
测试结果
五、栈的应用
- 函数调用栈:在程序执行过程中,函数调用是通过栈来实现的。每个函数调用时,其返回地址、局部变量和参数等信息都会被压入栈中,当函数返回时,这些信息会被弹出栈。
- 表达式求值:在编译器中,表达式求值通常使用栈来实现。例如,在解析算术表达式时,可以使用两个栈:一个用于存储操作数,另一个用于存储操作符。
- 浏览器历史记录:浏览器的“前进”和“后退”功能通常使用栈来实现。用户浏览的网页会被压入栈中,当用户点击“后退”按钮时,会从栈中弹出并显示上一个网页。
- 撤销操作:在许多图形编辑器和文本编辑器中,撤销操作通常使用栈来实现。每次编辑操作(如剪切、复制、粘贴等)都会被压入一个撤销栈中,当用户点击“撤销”按钮时,会从栈中弹出并执行相反的操作以撤销上一次编辑。
六、总结
- 使用数组实现栈是一种简单且高效的方法,能够充分利用数组的特性来实现栈的基本操作。
- 在实际应用中,栈具有广泛的应用场景,如函数调用栈、浏览器的前进后退功能以及表达式求值等。
相关文章:

【数据结构与算法】使用数组实现栈:原理、步骤与应用
💓 博客主页:倔强的石头的CSDN主页 📝Gitee主页:倔强的石头的gitee主页 ⏩ 文章专栏:《数据结构与算法》 期待您的关注 目录 一、引言 🎄栈(Stack)是什么? …...
cell的复用机制和自定义cell
cell的复用机制和自定义cell UITableView 在学习cell之前,我们需要先了解UITableView。UITableView继承于UIScrollView,拥有两个两个相关协议 UITableViewDelegate和UITableViewDataSource,前者用于显示单元格,设置行高以及对单…...

Redis 双写一致原理篇
前言 我们都知道,redis一般的作用是顶在mysql前面做一个"带刀侍卫"的角色,可以缓解mysql的服务压力,但是我们如何保证数据库的数据和redis缓存中的数据的双写一致呢,我们这里先说一遍流程,然后以流程为切入点来谈谈redis和mysql的双写一致性是如何保证的吧 流程 首先…...

《软件定义安全》之四:什么是软件定义安全
第4章 什么是软件定义安全 1.软件定义安全的含义 1.1 软件定义安全的提出 虚拟化、云计算、软件定义架构的出现,对安全体系提出了新的挑战。如果要跟上网络演进的步伐和业务快速创新的速度,安全体系应该朝以下方向演变。 𝟭 安全机制软件…...

将AIRNet集成到yolov8中,实现端到端训练与推理
AIRNet是一个图像修复网络,支持对图像进行去雾、去雨、去噪声的修复。其基于对比的退化编码器(CBDE),将各种退化类型统一到同一嵌入空间;然后,基于退化引导恢复网络(DGRN)将嵌入空间修复为目标图像。可以将AIRNet的输出与yolov8进行端到端集成,实现部署上的简化。 本博…...

hcache缓存查看工具
1、hcache概述 hcache是基于pcstat的,pcstat可以查看某个文件是否被缓存和根据进程pid来查看都缓存了哪些文件。hcache在其基础上增加了查看整个操作系统Cache和根据使用Cache大小排序的特性。官网:https://github.com/silenceshell/hcache 2、hcache安装 2.1下载…...

Java 数据类型 -- Java 语言的 8 种基本数据类型、字符串与数组
大家好,我是栗筝i,这篇文章是我的 “栗筝i 的 Java 技术栈” 专栏的第 004 篇文章,在 “栗筝i 的 Java 技术栈” 这个专栏中我会持续为大家更新 Java 技术相关全套技术栈内容。专栏的主要目标是已经有一定 Java 开发经验,并希望进…...

kafka-生产者事务-数据传递语义事务介绍事务消息发送(SpringBoot整合Kafka)
文章目录 1、kafka数据传递语义2、kafka生产者事务3、事务消息发送3.1、application.yml配置3.2、创建生产者监听器3.3、创建生产者拦截器3.4、发送消息测试3.5、使用Java代码创建主题分区副本3.6、屏蔽 kafka debug 日志 logback.xml3.7、引入spring-kafka依赖3.8、控制台日志…...

免费!GPT-4o发布,实时语音视频丝滑交互
We’re announcing GPT-4o, our new flagship model that can reason across audio, vision, and text in real time. 5月14日凌晨,OpenAI召开了春季发布会,发布会上公布了新一代旗舰型生成式人工智能大模型【GPT-4o】,并表示该模型对所有免费…...
DevOps的原理及应用详解(四)
本系列文章简介: 在当今快速变化的商业环境中,企业对于软件交付的速度、质量和安全性要求日益提高。传统的软件开发和运维模式已经难以满足这些需求,因此,DevOps(Development和Operations的组合)应运而生,成为了解决这些问题的有效方法。 DevOps是一种强调软件开发人员(…...

关于选择,关于处事
一个人选择应该选择的是勇敢,选择不应该选择的是无奈。放弃,不该放弃的是懦夫,不放弃应该放弃的是睿智。所以,碰到事的时候要先静,先不管什么事,先静下来,先淡定,先从容。在生活里要…...

大话设计模式解读02-策略模式
本篇文章,来解读《大话设计模式》的第2章——策略模式。并通过Qt和C代码实现实例代码的功能。 1 策略模式 策略模式作为一种软件设计模式,指对象有某个行为,但是在不同的场景中,该行为有不同的实现算法。 策略模式的特点&#…...

展会邀请 | 龙智即将亮相2024上海国际嵌入式展,带来安全合规、单一可信数据源、可追溯、高效协同的嵌入式开发解决方案
2024年6月12日至14日,备受全球嵌入式系统产业和社群瞩目的2024上海国际嵌入式展(embedded world china 2024)即将盛大开幕,龙智将携行业领先的嵌入式开发解决方案亮相 640展位 。 此次参展,龙智将全面展示专为嵌入式行…...

codeforce round951 div2
A guess the maximum 问题: 翻译一下就是求所有相邻元素中max - 1的最小值 代码: #include <iostream> #include <algorithm>using namespace std;const int N 5e4;int a[N]; int n;void solve() {cin >> n;int ans 0x3f3f3f3f;…...
arcgis开发记录
目录 文章目录 [toc]**arcgis JavaScript API安装**1. arcgisAPI下载地址:https://developers.arcgis.com/downloads/2. 4.4版本API:本地配置3. 3.18版本修改方法 **angular2中加载arcgis JS API**** arcgis加载图层 并显示图层上点的信息****使用图层上…...

RPA-UiBot6.0数据整理机器人—杂乱数据秒变报表
前言 友友们是否常常因为杂乱的数据而烦恼?数据分类、排序、筛选这些繁琐的任务是否占据了友友们的大部分时间?这篇博客将为友友们带来一个新的解决方案,让我们共同学习如何运用RPA数据整理机器人,实现杂乱数据的快速整理,为你的工作减负增效! 在这里,友友们将了…...

Application UI
本节包含关于如何用DevExpress控件模拟许多流行的应用程序ui的教程。 Windows 11 UI Windows 11和最新一代微软Office产品启发的UI。 Office Inspired UI Word、Excel、PowerPoint和Visio等微软Office应用程序启发的UI。 如何:手动构建Office风格的UI 本教程演示…...

关于 Redis 中集群
哨兵机制中总结到,它并不能解决存储容量不够的问题,但是集群能。 广义的集群:只要有多个机器,构成了分布式系统,都可以称之为一个“集群”,例如主从结构中的哨兵模式。 狭义的集群:redis 提供的…...

C++必修:探索C++的内存管理
✨✨ 欢迎大家来到贝蒂大讲堂✨✨ 🎈🎈养成好习惯,先赞后看哦~🎈🎈 所属专栏:C学习 贝蒂的主页:Betty’s blog 1. C/C的内存分布 我们首先来看一段代码及其相关问题 int globalVar 1; static…...
python列表---基本语法(浅拷贝,深拷贝等)
文章目录 引言:列表的注意事项1 list中的浅拷贝与深拷贝1.1浅拷贝(Shallow Copy)浅拷贝的方法浅拷贝的效果1.2深拷贝(Deep Copy)深拷贝的方法深拷贝的效果1.3 总结:浅拷贝 vs 深拷贝1.4 为什么浅拷贝顶层元素如果是不可变数据就不能共享,不是传的是引用就相当于传的是地…...

Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...

STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

【UE5 C++】通过文件对话框获取选择文件的路径
目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 ,这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器,右键点击 .uproject 文件,选择 "Generate Visual Studio project files",重…...

云安全与网络安全:核心区别与协同作用解析
在数字化转型的浪潮中,云安全与网络安全作为信息安全的两大支柱,常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异,并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全:聚焦于保…...