当前位置: 首页 > news >正文

栈----数据结构

在这里插入图片描述

  • 🔆栈的概念
  • 🔆栈的结构
  • 🔆栈的实现
  • 🔆括号匹配问题
  • 🔆结语

🔆栈的概念

  • 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。**进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。**栈中的数据元素遵守后进先出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;
}

🔆结语

到这里这篇博客已经结束啦。
这份博客👍如果对你有帮助,给博主一个免费的点赞以示鼓励欢迎各位🔎点赞👍评论收藏⭐️,谢谢!!!
如果有什么疑问或不同的见解,欢迎评论区留言欧👀

相关文章:

栈----数据结构

栈&#x1f506;栈的概念&#x1f506;栈的结构&#x1f506;栈的实现&#x1f506;括号匹配问题&#x1f506;结语&#x1f506;栈的概念 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素操作。**进行数据插入和删除操作的一端称为栈顶&am…...

【人人都能读标准】11. 原理篇总结:一个程序的完整执行过程

本文为《人人都能读标准》—— ECMAScript篇的第11篇。我在这个仓库中系统地介绍了标准的阅读规则以及使用方式&#xff0c;并深入剖析了标准对JavaScript核心原理的描述。 我们一路走了很远很远&#xff0c;终于到了本书原理篇的最后一站。 在原理篇中&#xff0c;我们先讲了…...

sheng的学习笔记-IO多路复用,NIO,BIO,AIO

基础概念IO分为几种&#xff1a;同步阻塞的BIO&#xff0c;同步非阻塞的NIO&#xff0c;异步非阻塞AIO&#xff0c;IO多路复用&#xff0c;信号驱动IO&#xff08;不常用&#xff09;对于一个network IO&#xff0c;它会涉及到两个系统对象&#xff0c;一个是调用这个IO的proce…...

【Python入门第三十五天】Python丨文件打开

在服务器上打开文件 假设我们有以下文件&#xff0c;位于与 Python 相同的文件夹中。 demofile.txt Hello! Welcome to demofile.txt This file is for testing purposes. Good Luck!如需打开文件&#xff0c;请使用内建的 open() 函数。 open() 函数返回文件对象&#xff…...

jsoup 框架的使用指南

概述 参考&#xff1a; 官方文档jsoup的使用JSoup教程jsoup 在 GitHub 的开源代码 概念简介 jsoup 是一款基于 Java 的 HTML 解析器&#xff0c;它提供了一套非常省力的 API&#xff0c;不但能直接解析某个 URL 地址、HTML 文本内容&#xff0c;而且还能通过类似于 DOM、CS…...

web前端开发和后端开发哪个难度大?

前言 因为涉及到的具体的应用的领域不同&#xff0c;所以说不能简单地说哪一个难&#xff0c;对于前端而言你会感觉到入门会非常的简单&#xff0c;这也是会给许多人一种错觉&#xff0c;前端很简单&#xff0c;但是只能说是在入门理解上是有利于新手的&#xff0c;前端在主要…...

认证与认可之间有什么区别和联系?

认证与认可之间有什么区别和联系&#xff1f; 当今社会&#xff0c;认证与认可已经深入企业的生活&#xff0c;那么认证与认可之间到底有什么区别和联系呢&#xff1f; 认证&#xff0c;是指由认证机构证明产品、服务、管理体系符合相关技术规范、相关技术规范的强制性要求或者…...

【Java|golang】1626. 无矛盾的最佳球队---最长子序列,不连续,二维数组排序

假设你是球队的经理。对于即将到来的锦标赛&#xff0c;你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和 。 然而&#xff0c;球队中的矛盾会限制球员的发挥&#xff0c;所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名…...

C++ 八股文(简单面试题)

1.左值 可寻址变量&#xff0c;持久性&#xff1b; 2.右值 没有变量名&#xff0c;不可寻址&#xff0c;短暂性&#xff1b; 3.指针 指向的内存地址&#xff0c;指针变量存储的就是指向的对象的首地址 4.引用 为一个变量起别名&#xff0c;定义引用的时候一定要初始化&a…...

RK3588平台开发系列讲解(显示篇)DP显示调试方法

平台内核版本安卓版本RK3588Linux 5.10Android 12文章目录 一、查看 connector 状态二、强制使能/禁⽤ DP三、DPCP 读写四、Type-C 接口 Debug五、查看 DP 寄存器六、查看 VOP 状态七、查看当前显示时钟八、调整 DRM log 等级沉淀、分享、成长,让自己和他人都能有所收获!😄…...

模拟请求发生跨域问题

参考&#xff1a;传送门 问题产生&#xff1a; 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

⭐️我叫忆_恒心&#xff0c;一名喜欢书写博客的在读研究生&#x1f468;‍&#x1f393;。 如果觉得本文能帮到您&#xff0c;麻烦点个赞&#x1f44d;呗&#xff01; 近期会不断在专栏里进行更新讲解博客~~~ 有什么问题的小伙伴 欢迎留言提问欧&#xff0c;喜欢的小伙伴给个三…...

WEB网站服务(一)

1.1 Apache网站服务基础1.1.1Apache简介Apache HTTP Server是开源软件项目的杰出代表&#xff0c;基于标准的HTTP网络协议提供网页浏览服务。Apache服务器可以运行在Linux,UNIX&#xff0c;windows等多种操作系统平台中。1.Apache的起源1995年&#xff0c;Apache服务程序的1.0版…...

Python数据分析script必备知识(一)

Python数据分析script必备知识(一) 1.重定向终端输出内容 使生成的结果移动到其他位置 # 重定向, 使生成的结果移动到其他位置 import syssys.stderr = sys.stdoutprint(dir(sys)) # ,,,,,__stderr__, __stdin__, __stdout__,,,,,,# 使用场景:脚本上线时,想要把输出结果…...

初识linux之管道

一、进程间通信的概念大家都知道&#xff0c;进程是具有独立性的&#xff0c;因为一个程序运行起来生成进程时&#xff0c;也会生成它的进程结构体&#xff0c;即PCB&#xff0c;然后然后通过进程结构体中的结构体指针找到它的虚拟地址空间&#xff0c;然后再通过它的页表映射到…...

C++成神之路 | 第一课【步入C++的世界】

目录 一、认识C++ 1.1、关于 C++ 1.2、C++的前世今生 1.2.1、C+...

【面试题】大厂面试官:你做过什么有亮点的项目吗?

大厂面试题分享 面试题库前后端面试题库 &#xff08;面试必备&#xff09; 推荐&#xff1a;★★★★★地址&#xff1a;前端面试题库前言大厂面试中除了问常见的算法网络基础&#xff0c;和一些八股文手写体之外&#xff0c;经常出现的一个问题就是&#xff0c;你做过什么项目…...

Springboot Long类型数据太长返回给前端,精度丢失问题 复现、解决

前言 惯例&#xff0c;收到兄弟求救&#xff0c;关于long类型丢失精度的问题&#xff1a; 存在一个初学者不会&#xff0c;就会有第二个初学者不会&#xff0c;所以我出手。 正文 不多说&#xff0c;开搞。 如题&#xff0c; 后端返回的数据 给到 前端&#xff0c; Long类型数…...

Anaconda虚拟环境的创建方法(命令创建)

虚拟环境介绍&#xff1a; 虚拟环境是一为某个项目创建的专属于它的python包&#xff0c;因此做python项目时&#xff0c;一般一个项目用一个虚拟环境。在实际开发中&#xff0c;如果项目A需要某个包的1.0版本&#xff0c;项目B需要此包的2.0版本。如果没有安装虚拟环境&#…...

数据结构——树与二叉树

作者&#xff1a;几冬雪来 时间&#xff1a;2023年3月22日 内容&#xff1a;数据结构树与二叉树的讲解&#xff08;介绍&#xff09; 目录 前言&#xff1a; 1.树的概念&#xff1a; 2.树与非树&#xff1a; 3.树的定义&#xff1a; 4.树的应用&#xff1a; 二叉树&…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...