【数据结构与算法】使用数组实现栈:原理、步骤与应用
💓 博客主页:倔强的石头的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 为什么浅拷贝顶层元素如果是不可变数据就不能共享,不是传的是引用就相当于传的是地…...

label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
c# 局部函数 定义、功能与示例
C# 局部函数:定义、功能与示例 1. 定义与功能 局部函数(Local Function)是嵌套在另一个方法内部的私有方法,仅在包含它的方法内可见。 • 作用:封装仅用于当前方法的逻辑,避免污染类作用域,提升…...
【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统
Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...

云原生安全实战:API网关Envoy的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关 作为微服务架构的统一入口,负责路由转发、安全控制、流量管理等核心功能。 2. Envoy 由Lyft开源的高性能云原生…...