【数据结构与算法】第6课—数据结构之栈
文章目录
- 1. 栈
- 2. 栈的初始化和栈的销毁
- 3. 入栈和出栈(压栈)
- 4. 取栈顶元素并打印
- 5. 栈的练习题
- 5.1 有效的括号
1. 栈
- 栈:也是一种线性表,其数据结构与动态顺序表的数据结构类似
- 栈分为栈顶和栈底,在栈中,插入数据和删除数据被称为入栈和出栈
- 栈的相关操作都是在栈顶实现的,而栈底通常不会改变
- 栈的底层结构可以通过数组和链表实现,但是链表在入栈和出栈操作上,会出现指针指向改变的问题,相对而言,数组反而只需要改变其size(在栈中被称为栈顶top)大小即可,因此用数组来实现栈的底层更佳
2. 栈的初始化和栈的销毁
//初始化
void StackInit(Stack* ps)
{assert(ps);ps->arr = NULL;ps->top = ps->capacity = 0;
}//销毁
void StackDestroy(Stack* ps)
{assert(ps);if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}
3. 入栈和出栈(压栈)
//入栈
void StackPush(Stack* ps, STDataType x)
{assert(ps);//空间满了--增容if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr,newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//直接尾插ps->arr[ps->top] = x;ps->top++;
}//出栈
void StackPop(Stack* ps)
{assert(ps && ps->top);ps->top--;
}
4. 取栈顶元素并打印
//取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps && ps->arr);return ps->arr[ps->top - 1];
}//获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}//打印
void StackPrint(Stack* ps)
{assert(ps);while (ps->top){//栈顶元素依次出栈STDataType top = StackTop(ps);printf("%d ", top);//每次出栈top--ps->top--;}
}
5. 栈的练习题
5.1 有效的括号
- 题目
- 思路
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
//栈的数据结构
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;int capacity;
}Stack;//初始化
void StackInit(Stack* ps)
{assert(ps);ps->arr = NULL;ps->top = ps->capacity = 0;
}//销毁
void StackDestroy(Stack* ps)
{assert(ps);if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}//入栈
void StackPush(Stack* ps, STDataType x)
{assert(ps);//空间满了--增容if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//直接尾插ps->arr[ps->top] = x;ps->top++;
}//出栈
void StackPop(Stack* ps)
{assert(ps && ps->top);ps->top--;
}//取栈顶元素
STDataType StackTop(Stack* ps)
{return ps->arr[ps->top - 1];
}//获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}//判断栈是否为空
bool StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}bool isValid(char* s)
{Stack st;StackInit(&st);char* pi = s;//遍历字符串while (*pi != '\0'){//入栈if (*pi == '(' || *pi == '[' || *pi == '{')StackPush(&st, *pi);else{//取栈顶,判断char top = StackTop(&st);if ((top == '(' && *pi == ')') || (top == '[' && *pi == ']') || (top == '{' && *pi == '}'))StackPop(&st);else{StackDestroy(&st);return false;}}pi++;}//对比结束bool ret = StackEmpty(&st) ? true : false;StackDestroy(&st);return ret;
}
相关文章:

【数据结构与算法】第6课—数据结构之栈
文章目录 1. 栈2. 栈的初始化和栈的销毁3. 入栈和出栈(压栈)4. 取栈顶元素并打印5. 栈的练习题5.1 有效的括号 1. 栈 栈:也是一种线性表,其数据结构与动态顺序表的数据结构类似栈分为栈顶和栈底,在栈中,插入…...

开源全站第一个Nextron(NextJS+electron)项目--NextTalk:一款集成chatgpt的实时聊天工具
NextTalk 简介 该项目是一个基于Nextron(NextJSElectron)的桌面端实时聊天工具。 但由于使用了NextJS中的ssr及api route功能,该程序只能在开发环境运行。 关于生产版本:我将其网页端部分分离,并用Pake将其打包成桌面端,生产体…...
多样化的编程模型:并发与并行策略
因为经常看着某些框架设计的编程模型很晕,所以自己梳理总结了一下编程模型的分类,总共六个大类,基本所有常见框架设计的编程模型都是基于这六个大类来实现的,如果有错误的地方,请见谅并不吝赐教,感谢&#…...
npm入门教程2:npm历史
一、起源与诞生 时间背景:npm的诞生与Node.js的兴起紧密相关。Node.js是一个基于Chrome V8引擎的JavaScript运行环境,它允许JavaScript代码在服务器端运行。随着Node.js的流行,开发者们对于包管理和依赖解决的需求日益增长。诞生:…...

Cuebric:用AI重新定义3D创作的未来
一、简介 Cuebric 是一家成立于2022年夏天的好莱坞创新公司,致力于为电影、电视、游戏和时尚等行业提供先进的AI多模态SaaS平台。自2024年1月正式推出以来,Cuebric 已经在市场上获得了广泛的认可和积极的反馈。目前,该平台正处于1.0版本的beta测试阶段,已募集约50万美元的…...
前端react常见面试题目(basic)
1. 如果 React 组件的属性没有传值,它的默认值是什么? 如果一个 React 组件的属性(props)没有传值,那么它的默认值会是 undefined。你可以通过组件内部的逻辑来设置默认值,比如使用逻辑运算符或者 ES6 的默认参数。 …...

机器人技术基础(4章逆运动解算和雅克比矩阵)
逆运动解算: 雅克比矩阵: 将动力学分析转向运动的物体 下图中的 n o y 反映了机器人的姿态矩阵, 最后一列 p 反应了机器人在空间中的位置:...

OpenGL入门002——顶点着色器和片段着色器
文章目录 一些概念坐标转换阶段顶点着色器片段着色器VBOVAO 实战简介main.cppCMakeLists.txt最终效果 一些概念 坐标转换阶段 概述: 模型空间、世界空间、视图空间和裁剪空间是对象在3D场景中经历的不同坐标变换阶段。每个空间对应渲染管道的一个步骤,…...
[数组排序] LCR 164. 破解闯关密码
文章目录 1. 题目链接2. 题目大意3. 示例4. 解题思路5. 参考代码 1. 题目链接 LCR 164. 破解闯关密码 - 力扣(LeetCode) 2. 题目大意 描述:给定一个非负整数数组 nums。 要求:将数组中的数字拼接起来排成一个数,打印…...

05 Django 框架模型介绍(一)
文章目录 1、Django 模型简介2、Django 中创建并使用模型(1)新加一个名为 myapp 的应用(2)定义模型类(2)激活模型类(3)创建数据库迁移文件(4)应用迁移文件 3、…...

【简道云 -注册/登录安全分析报告】
前言 由于网站注册入口容易被黑客攻击,存在如下安全问题: 暴力破解密码,造成用户信息泄露短信盗刷的安全问题,影响业务及导致用户投诉带来经济损失,尤其是后付费客户,风险巨大,造成亏损无底洞…...

【C++题解】1970. 判断是什么字符
欢迎关注本专栏《C从零基础到信奥赛入门级(CSP-J)》 问题:1970. 判断是什么字符 类型:字符串、字符型 题目描述: 从键盘读入一个字符,有可能是大写字母、小写字母、数字中的一种,请编程判断&…...
Python自动化操作Word文档详解
在日常办公和数据处理中,我们经常需要处理Word文档。手动操作Word文档可能会非常繁琐和耗时,而使用Python可以实现自动化操作,提高工作效率。本文将详细介绍如何使用Python自动化操作Word文档,包括读取、写入、修改和格式化等操作…...
常用滤波算法(二)-中位值滤波法
文章目录 一、中位值滤波法简介二、C语言实现中位值滤波法三、程序说明信号初始化:滤波窗口大小:内存分配:中位值滤波函数:中位值计算函数:内存释放: 四、总结 中位值滤波法,作为一种非线性滤波…...

HCIP--以太网交换安全(总实验)
实验背景 假如你是公司的网络管理员,为了提高公司网络安全性,你决定在接入交换机部署一些安全技术:端口隔、端口安全、DHCP snooping、IPSG。 实验拓扑图 实验的要求: 1.在R1、R2连接在GE0/0/1和GE0/0/2接口下,均划…...

C语言 | Leetcode C语言题解之第519题随机翻转矩阵
题目: 题解: typedef struct {unsigned long long val;UT_hash_handle hh; } Hash;typedef struct {Hash *hash;int n_rows;int n_cols; } Solution, SL;Solution* solutionCreate(int n_rows, int n_cols) {SL *obj malloc(sizeof(SL));obj->hash …...

《机器人SLAM导航核心技术与实战》第1季:第10章_其他SLAM系统
视频讲解 【第1季】10.第10章_其他SLAM系统-视频讲解 【第1季】10.1.第10章_其他SLAM系统_RTABMAP算法-视频讲解 【第1季】10.2.第10章_其他SLAM系统_VINS算法-视频讲解 【第1季】10.3.第10章_其他SLAM系统_机器学习与SLAM-视频讲解 第1季:第10章_其他SLAM系统 …...

《双指针篇》---快乐数
题目传送门 1.创建一个bitsum函数用于得到这个数每位的平方和。 2.令快指针等于bitsum(n) 3.慢指针等于n。 逐步令 fast bitSum(bitSum(fast)); slow bitSum(slow); 若最后fast等于slow,则且等于1.则return true。 否则return false。 cla…...
U盘引导丢失问题的处理办法
项目背景:在使用自制的u盘系统的时候经常遇到引导丢失的问题,那么咱们怎么解决这个问题呢,首先第一步通过手动引导u盘 进入系统,同时再进行引导区的修复这样u盘系统就可以正常工作了。 1 进入grub 的提示符下面,首先…...
layui tree customSelet选中的内容重写,查找父级
layui tree customSelet选中的内容重写,查找父级 需要重新源码 // 递归查找函数 // tree 所有数据 ,nodeId选中数据id值 function findParent(tree, nodeId, parent null) {for (let i 0; i < tree.length; i) {if (tree[i].id nodeId) {return …...

Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...

.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...

如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...

无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...

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