栈----数据结构

栈
- 🔆栈的概念
- 🔆栈的结构
- 🔆栈的实现
- 🔆括号匹配问题
- 🔆结语
🔆栈的概念
- 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。**进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。**栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
- 压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
- 出栈:栈的删除操作叫做出栈。出数据也在栈顶。
🔆栈的结构


🔆栈的实现
数组栈gitt代码链接
栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
- 数组栈

- 链式栈

🔆括号匹配问题
OJ链接
给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例一:输入:s = “()”
输出:true示例二:
输入:s = “()[]{}”
输出:true示例三:
输入:s = “(]”
输出:false
- 解题思路:

- 答案:
//动态栈的实现
typedef char STDataType;typedef struct Stack {STDataType* a;//top 指向栈顶int top;//capacity表示栈的容量int capacity;
}ST;//创建栈
ST* STCreate() {ST* stack = (ST*)malloc(sizeof(ST));if (stack == NULL) {perror("malloc::");return NULL;}STInit(stack);return stack;
}//栈的初始化
void STInit(ST* ps) {assert(ps);ps->a = NULL;//top为-1时表示指向栈顶,top为0时表示指向栈顶的下一个ps->top = -1;ps->capacity = 0;
}//栈的判空
bool STEmpty(ST* ps) {assert(ps);return ps->top == -1;
}//栈的判满
bool STFull(ST* ps) {assert(ps);return (ps->top + 1 == ps->capacity);
}//入栈
void STPush(ST* ps, STDataType val) {assert(ps);if (STFull(ps)) {int newcapacity = ((ps->capacity == 0) ? 4 : (2 * ps->capacity));STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));if (tmp == NULL) {perror("realloc::");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}(ps->top)++;ps->a[ps->top] = val;
}//出栈
void STPop(ST* ps) {assert(ps);assert(!STEmpty(ps));(ps->top)--;
}//获取栈元素个数
int STSize(ST* ps) {assert(ps);return (ps->top) + 1;
}//获取栈顶元素
STDataType STTop(ST* ps) {assert(ps);return ps->a[ps->top];
}//销毁栈
void STDestroy(ST* ps) {assert(ps);free(ps->a);ps->a = NULL;ps->top = -1;ps->capacity = 0;free(ps);
}bool isValid(char* s){int len = strlen(s);if (len <= 1) {return false;}ST* st = STCreate();char* cur = s;while (*cur) {if (*cur == '(' || *cur == '[' || *cur == '{') {STPush(st, *cur);}else if (*cur == ')' || *cur ==']' || *cur == '}') {if (STEmpty(st) || (*cur == ')' && STTop(st) != '(') || (*cur == ']' && STTop(st) != '[') || (*cur == '}' && STTop(st) != '{')) {return false;}STPop(st);}cur++;}if (!STEmpty(st)) {return false;}STDestroy(st);st = NULL;return true;
}
🔆结语
到这里这篇博客已经结束啦。
这份博客👍如果对你有帮助,给博主一个免费的点赞以示鼓励欢迎各位🔎点赞👍评论收藏⭐️,谢谢!!!
如果有什么疑问或不同的见解,欢迎评论区留言欧👀
相关文章:
栈----数据结构
栈🔆栈的概念🔆栈的结构🔆栈的实现🔆括号匹配问题🔆结语🔆栈的概念 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。**进行数据插入和删除操作的一端称为栈顶&am…...
【人人都能读标准】11. 原理篇总结:一个程序的完整执行过程
本文为《人人都能读标准》—— ECMAScript篇的第11篇。我在这个仓库中系统地介绍了标准的阅读规则以及使用方式,并深入剖析了标准对JavaScript核心原理的描述。 我们一路走了很远很远,终于到了本书原理篇的最后一站。 在原理篇中,我们先讲了…...
sheng的学习笔记-IO多路复用,NIO,BIO,AIO
基础概念IO分为几种:同步阻塞的BIO,同步非阻塞的NIO,异步非阻塞AIO,IO多路复用,信号驱动IO(不常用)对于一个network IO,它会涉及到两个系统对象,一个是调用这个IO的proce…...
【Python入门第三十五天】Python丨文件打开
在服务器上打开文件 假设我们有以下文件,位于与 Python 相同的文件夹中。 demofile.txt Hello! Welcome to demofile.txt This file is for testing purposes. Good Luck!如需打开文件,请使用内建的 open() 函数。 open() 函数返回文件对象ÿ…...
jsoup 框架的使用指南
概述 参考: 官方文档jsoup的使用JSoup教程jsoup 在 GitHub 的开源代码 概念简介 jsoup 是一款基于 Java 的 HTML 解析器,它提供了一套非常省力的 API,不但能直接解析某个 URL 地址、HTML 文本内容,而且还能通过类似于 DOM、CS…...
web前端开发和后端开发哪个难度大?
前言 因为涉及到的具体的应用的领域不同,所以说不能简单地说哪一个难,对于前端而言你会感觉到入门会非常的简单,这也是会给许多人一种错觉,前端很简单,但是只能说是在入门理解上是有利于新手的,前端在主要…...
认证与认可之间有什么区别和联系?
认证与认可之间有什么区别和联系? 当今社会,认证与认可已经深入企业的生活,那么认证与认可之间到底有什么区别和联系呢? 认证,是指由认证机构证明产品、服务、管理体系符合相关技术规范、相关技术规范的强制性要求或者…...
【Java|golang】1626. 无矛盾的最佳球队---最长子序列,不连续,二维数组排序
假设你是球队的经理。对于即将到来的锦标赛,你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和 。 然而,球队中的矛盾会限制球员的发挥,所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名…...
C++ 八股文(简单面试题)
1.左值 可寻址变量,持久性; 2.右值 没有变量名,不可寻址,短暂性; 3.指针 指向的内存地址,指针变量存储的就是指向的对象的首地址 4.引用 为一个变量起别名,定义引用的时候一定要初始化&a…...
RK3588平台开发系列讲解(显示篇)DP显示调试方法
平台内核版本安卓版本RK3588Linux 5.10Android 12文章目录 一、查看 connector 状态二、强制使能/禁⽤ DP三、DPCP 读写四、Type-C 接口 Debug五、查看 DP 寄存器六、查看 VOP 状态七、查看当前显示时钟八、调整 DRM log 等级沉淀、分享、成长,让自己和他人都能有所收获!😄…...
模拟请求发生跨域问题
参考:传送门 问题产生: Access to XMLHttpRequest at ‘http://test-cms.jinhuahuolong.com/api/pages/list’ from origin ‘null’ has been blocked by CORS policy: No ‘Access-Control-Allow-Origin’ header is present on the requested resourc…...
Qt实践项目:仿Everything软件实现一个QtEverything
⭐️我叫忆_恒心,一名喜欢书写博客的在读研究生👨🎓。 如果觉得本文能帮到您,麻烦点个赞👍呗! 近期会不断在专栏里进行更新讲解博客~~~ 有什么问题的小伙伴 欢迎留言提问欧,喜欢的小伙伴给个三…...
WEB网站服务(一)
1.1 Apache网站服务基础1.1.1Apache简介Apache HTTP Server是开源软件项目的杰出代表,基于标准的HTTP网络协议提供网页浏览服务。Apache服务器可以运行在Linux,UNIX,windows等多种操作系统平台中。1.Apache的起源1995年,Apache服务程序的1.0版…...
Python数据分析script必备知识(一)
Python数据分析script必备知识(一) 1.重定向终端输出内容 使生成的结果移动到其他位置 # 重定向, 使生成的结果移动到其他位置 import syssys.stderr = sys.stdoutprint(dir(sys)) # ,,,,,__stderr__, __stdin__, __stdout__,,,,,,# 使用场景:脚本上线时,想要把输出结果…...
初识linux之管道
一、进程间通信的概念大家都知道,进程是具有独立性的,因为一个程序运行起来生成进程时,也会生成它的进程结构体,即PCB,然后然后通过进程结构体中的结构体指针找到它的虚拟地址空间,然后再通过它的页表映射到…...
C++成神之路 | 第一课【步入C++的世界】
目录 一、认识C++ 1.1、关于 C++ 1.2、C++的前世今生 1.2.1、C+...
【面试题】大厂面试官:你做过什么有亮点的项目吗?
大厂面试题分享 面试题库前后端面试题库 (面试必备) 推荐:★★★★★地址:前端面试题库前言大厂面试中除了问常见的算法网络基础,和一些八股文手写体之外,经常出现的一个问题就是,你做过什么项目…...
Springboot Long类型数据太长返回给前端,精度丢失问题 复现、解决
前言 惯例,收到兄弟求救,关于long类型丢失精度的问题: 存在一个初学者不会,就会有第二个初学者不会,所以我出手。 正文 不多说,开搞。 如题, 后端返回的数据 给到 前端, Long类型数…...
Anaconda虚拟环境的创建方法(命令创建)
虚拟环境介绍: 虚拟环境是一为某个项目创建的专属于它的python包,因此做python项目时,一般一个项目用一个虚拟环境。在实际开发中,如果项目A需要某个包的1.0版本,项目B需要此包的2.0版本。如果没有安装虚拟环境&#…...
数据结构——树与二叉树
作者:几冬雪来 时间:2023年3月22日 内容:数据结构树与二叉树的讲解(介绍) 目录 前言: 1.树的概念: 2.树与非树: 3.树的定义: 4.树的应用: 二叉树&…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...
WPF八大法则:告别模态窗口卡顿
⚙️ 核心问题:阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程,导致后续逻辑无法执行: var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题:…...
规则与人性的天平——由高考迟到事件引发的思考
当那位身着校服的考生在考场关闭1分钟后狂奔而至,他涨红的脸上写满绝望。铁门内秒针划过的弧度,成为改变人生的残酷抛物线。家长声嘶力竭的哀求与考务人员机械的"这是规定",构成当代中国教育最尖锐的隐喻。 一、刚性规则的必要性 …...
