当前位置: 首页 > 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; 二叉树&…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...