栈的实现以及c语言解决括号匹配问题

一、栈的实现

1、头文件

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); 

2、函数实现

a、初始化

top为栈顶的位置但是给其初始化时要考虑其初始化为什么(因为我们访问栈顶元素时,是通过top实现的,即下标访问,且栈的特点为先出后进,所以用栈时只考虑栈顶元素,其他位置不考虑),所以会有如下情况:

这里我选择第二种方式,因为判断栈空间时直接比较top和capacity的大小即可:
 

// 初始化栈 
void StackInit(Stack* ps)
{assert(ps);ps->_a = NULL;ps->_capacity = ps->_top = 0;//此时top为栈顶元素的下一个位置
}

b、销毁栈

void StackDestroy(Stack* ps)
{assert(ps);free(ps->_a);ps->_a = NULL;ps->_capacity = ps->_top = 0;//为了严谨置为0
}

c、入栈

入栈之前要像和实现顺序表的时候,去判断空间是否够用:

void StackPush(Stack* ps, STDataType data)
{assert(ps);int newcapacity = 0;STDataType* tmp = NULL;if (ps->_top == ps->_capacity){if (ps->_capacity == 0)//为0给空间为4{newcapacity = 4;}else//扩二倍{newcapacity = 2 * ps->_capacity;}//int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;也可以直接一个三目操作符搞定tmp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");exit(0);// 退出程序}ps->_capacity = tmp;ps->_capacity = newcapacity;}ps->_a[ps->_top] = data;//top指向下一个位置直接加ps->_top++;
}

d、出栈

出栈其实非常简单只需要将top减1就可以了,但要注意top不能减到0,因为指向0的时候就没有元素了,数组大小为0;

void StackPop(Stack* ps)
{assert(ps);assert(ps->_top > 0);ps->_top--;
}

e、获取栈顶元素

STDataType StackTop(Stack* ps)
{assert(ps);assert(ps->_top > 0);//保证有栈顶元素return ps->_a[ps->_top - 1];
}

f、获取栈元素个数

int StackSize(Stack* ps)
{assert(ps);assert(ps->_top >= 0);//数组元素个数不能为负return ps->_top://top就是数组元素个数
}

g、判断栈是否为空

int StackEmpty(Stack* ps)
{assert(ps);return ps->_top == 0;//返回这个表达式的结果即可
}

二、括号匹配问题

这题恰好用到了我们刚昂实现的栈的知识,我们就会有这样的思路,如果为左括号则入栈,再将栈顶元素和下一个字符匹配,如果匹配成功则出栈,否则继续匹配,直到字符串读完.(这里注意题目中传的是字符串的首地址,那么我们可以通过一个一个解引用,来实现入栈)。

实际上我们也可以先将所以的左括号入完栈后再一个一个进行比较,如果不对字符串向下走,但是这样会遍历两次,时间复杂度为O(N),那么,我们不如变入栈边比较,因为会对字符串进行调整,对比成功的直接出栈 ,所以不用担心会对比两次的情况,时间复杂度还是O(N)。

那么有没有可能出现错过的情况?这里我们就要认真审题

随便 举个例子:我们会发现左括号和右括号总是成对出现的,当左括号入栈时,下一个一定是其对应的右括号。

这是第一种特殊情况,如果字符穿读完栈不为空时,说明不匹配,最后出循环时要加一个判断是否为空

这是第二种特殊情况,当开始为右边括号,则开始不入栈,最后出栈栈为空,根据前面,判断为真,但是为假,所以我们要在比对前加一步判断栈是否为空的情况,如果为空,则为假(因为没有左括号和右括号匹配)。

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

上位机图像处理和嵌入式模块部署(树莓派4b镜像烧录经验总结)

【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing 163.com】 陆陆续续也烧录了好多次树莓派的镜像了,这里面有的时候很快,有的时候很慢。特别是烧录慢的时候,也不知道是自己…

Partisia Blockchain 生态首个zk跨链DEX现已上线

在5月1日,由Partisia Blockchain与zkCross创建合作推出的Partisia zkCrossDEX在Partisia Blockchain生态正式上线。Partisia zkCrossDEX是Partisia Blockchain上重要的互操作枢纽,其融合了zkCross的zk技术跨链互操作方案,并利用Partisia Bloc…

Python批量计算多张遥感影像的NDVI

本文介绍基于Python中的gdal模块,批量基于大量多波段遥感影像文件,计算其每1景图像各自的NDVI数值,并将多景结果依次保存为栅格文件的方法。 如下图所示,现在有大量.tif格式的遥感影像文件,其中均含有红光波段与近红外…

pytest教程-39-钩子函数-pytest_runtest_setup

领取资料,咨询答疑,请➕wei: June__Go 上一小节我们学习了pytest_runtest_protocol钩子函数的使用方法,本小节我们讲解一下pytest_runtest_setup钩子函数的使用方法。 pytest_runtest_setup 钩子函数在每个测试用例的 setup 阶段被调用。这…

代码随想录算法训练营DAY44|C++动态规划Part6|完全背包理论基础、518.零钱兑换II、377. 组合总和 Ⅳ

文章目录 完全背包理论基础完全背包问题的定义与01背包的核心区别为什么完全背包的循环顺序可以互换?CPP代码 ⭐️518.零钱兑换II思路CPP代码 ⭐️377. 组合总和 Ⅳ思路CPP代码 扩展题 完全背包理论基础 卡码网第52题 文章链接:完全背包理论基础 视频链接…

练习题(2024/5/7)

1验证二叉搜索树 给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下: 节点的左 子树 只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。 示例 …

互联网十万个为什么之什么是云计算

云计算是一种通过互联网提供计算资源和服务的技术。它允许用户随时随地访问和使用云平台上的数据、软件和硬件资源。在数字化时代,互联网已经成为基础设施。云计算使得数据中心能够像一台计算机一样去工作。通过互联网将算力以按需使用、按量付费的形式提供给用户&a…

城市二手房数据分析与房价预测

实现功能 数据分析 二手房价格-时间分析 二手房数量-时间分析 二手房分布-区域分析 二手房户型分析 二手房朝向分析 二手房价格-区域分析 二手房热词词云 房价预测 采用合适的算法模型,对模型进行评估。通过输入影响因素输出预测价格。 采用技术与框架 M…

【MM32F3270 Micropython】pwm输出

文章目录 前言一、PWM脉宽调制技术介绍二、machine.PWM 类2.1 machine.PWM 类的构造对象2.2 PWM 对象初始化2.3 关闭PWM设备2.4 设置pwm的周期2.5 设置占空比 三、pwm示例代码总结 前言 MicroPython是一种精简的Python 3编程语言实现,旨在在微控制器和嵌入式系统上…

从0到1提审苹果商店(appstore)上线一款新APP

本篇主要复盘和介绍一款APP如何从0到1上线到苹果商店,将我自己项目遇到的坑跟大家分享,希望能为同样做开发或者运营的你提供经验,少走弯路。 如果你是24年1月1日之后开始首次提审APP,还需要先将自己的APP在工信部备案,苹果后台增加了工信部备案号的填写,备案方法和经验如…

揭秘 IEEE/ACM Trans/CCF/SCI,谁才是科研界的王者?

会议之眼 快讯 在学术探索的浩瀚星海中,每一篇论文都像是一颗璀璨的星辰,而那些被顶级期刊或会议收录的论文,则无疑是最耀眼的几颗。 在众多评价标准中,IEEE/ACM Transactions、CCF推荐期刊和会议、SCI分区期刊,它们…

18 内核开发-内核重点数据结构学习

课程简介: Linux内核开发入门是一门旨在帮助学习者从最基本的知识开始学习Linux内核开发的入门课程。该课程旨在为对Linux内核开发感兴趣的初学者提供一个扎实的基础,让他们能够理解和参与到Linux内核的开发过程中。 课程特点: 1. 入门级别&…

Qt---day2-信号与槽

1、思维导图 2、 拖拽式 源文件 #include "mywidget.h" #include "ui_mywidget.h" MyWidget::MyWidget(QWidget *parent) : QWidget(parent) , ui(new Ui::MyWidget) { ui->setupUi(this); //按钮2 this->btn2new QPushButton("按钮2",th…

什么是多模态大模型,有了大模型,为什么还要多模态大模型?

随着人工智能技术的愈演愈烈,其技术可以说是日新月异,每隔一段时间就会有新的技术和理念被创造出来;而多模态大模型也是其中之一。 什么是多模态 想弄明白什么是多模态大模型,那么首先就要弄明白什么是多模态。 简单来说&#x…

【Git】Commit后进行事务回滚

起因 因为一直使用git add .,在学习pytorch中添加了一个较大的数据集后,导致git push失败,而这个大数据集并不是必须要上传到仓库的,但是因为自己在设置.gitignore前已经进行了git comit,所以,需要进行事务…

嵌入式linux学习第三天汇编语言点灯

嵌入式linux学习第三天汇编语言点灯 今天学习如何在linux板子上点灯。 I.MX6U GPIO 详解 我们发现I.MX6U GPIO是分为两类的,:SNVS 域的和通用的。在讨论i.MX6U或类似的复杂微处理器时,了解其GPIO(通用输入输出)引脚…

Windows环境编译 VVenC 源码生成 Visual Studio 工程

VVenC介绍 Fraunhofer通用视频编码器(VVenC)的开发是为了提供一种公开可用的、快速和有效的VVC编码器实现。VVenC软件基于VTM,其优化包括软件重新设计以减轻性能瓶颈、广泛的SIMD优化、改进的编码器搜索算法和基本的多线程支持以利用并行。此外,VVenC支…

深度学习之基于YOLOv5目标检测可视化系统

欢迎大家点赞、收藏、关注、评论啦 ,由于篇幅有限,只展示了部分核心代码。 文章目录 一项目简介 二、功能三、系统四. 总结 一项目简介 一、项目背景与意义 随着深度学习技术的快速发展,目标检测在多个领域中的应用日益广泛,包括…

125.两两交换链表中的节点(力扣)

题目描述 代码解决及思路 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), …

很快就可以试用Domino 15了

大家好,才是真的好。 前几天在比利时的安普卫特举办的Engage2024大会已经结束,流出的现场照片很多,主要是会议场地照片很多,说是令人震撼;可惜这次一手的PPT和会议内容不多.是的,本来我也是在等与会者写的…