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

【数据结构与算法】第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. 入栈和出栈&#xff08;压栈&#xff09;4. 取栈顶元素并打印5. 栈的练习题5.1 有效的括号 1. 栈 栈&#xff1a;也是一种线性表&#xff0c;其数据结构与动态顺序表的数据结构类似栈分为栈顶和栈底&#xff0c;在栈中&#xff0c;插入…...

开源全站第一个Nextron(NextJS+electron)项目--NextTalk:一款集成chatgpt的实时聊天工具

NextTalk 简介 该项目是一个基于Nextron(NextJSElectron)的桌面端实时聊天工具。 但由于使用了NextJS中的ssr及api route功能&#xff0c;该程序只能在开发环境运行。 关于生产版本&#xff1a;我将其网页端部分分离&#xff0c;并用Pake将其打包成桌面端&#xff0c;生产体…...

多样化的编程模型:并发与并行策略

因为经常看着某些框架设计的编程模型很晕&#xff0c;所以自己梳理总结了一下编程模型的分类&#xff0c;总共六个大类&#xff0c;基本所有常见框架设计的编程模型都是基于这六个大类来实现的&#xff0c;如果有错误的地方&#xff0c;请见谅并不吝赐教&#xff0c;感谢&#…...

npm入门教程2:npm历史

一、起源与诞生 时间背景&#xff1a;npm的诞生与Node.js的兴起紧密相关。Node.js是一个基于Chrome V8引擎的JavaScript运行环境&#xff0c;它允许JavaScript代码在服务器端运行。随着Node.js的流行&#xff0c;开发者们对于包管理和依赖解决的需求日益增长。诞生&#xff1a…...

Cuebric:用AI重新定义3D创作的未来

一、简介 Cuebric 是一家成立于2022年夏天的好莱坞创新公司,致力于为电影、电视、游戏和时尚等行业提供先进的AI多模态SaaS平台。自2024年1月正式推出以来,Cuebric 已经在市场上获得了广泛的认可和积极的反馈。目前,该平台正处于1.0版本的beta测试阶段,已募集约50万美元的…...

前端react常见面试题目(basic)

1. 如果 React 组件的属性没有传值&#xff0c;它的默认值是什么? 如果一个 React 组件的属性&#xff08;props&#xff09;没有传值&#xff0c;那么它的默认值会是 undefined。你可以通过组件内部的逻辑来设置默认值&#xff0c;比如使用逻辑运算符或者 ES6 的默认参数。 …...

机器人技术基础(4章逆运动解算和雅克比矩阵)

逆运动解算&#xff1a; 雅克比矩阵&#xff1a; 将动力学分析转向运动的物体 下图中的 n o y 反映了机器人的姿态矩阵&#xff0c; 最后一列 p 反应了机器人在空间中的位置&#xff1a;...

OpenGL入门002——顶点着色器和片段着色器

文章目录 一些概念坐标转换阶段顶点着色器片段着色器VBOVAO 实战简介main.cppCMakeLists.txt最终效果 一些概念 坐标转换阶段 概述&#xff1a; 模型空间、世界空间、视图空间和裁剪空间是对象在3D场景中经历的不同坐标变换阶段。每个空间对应渲染管道的一个步骤&#xff0c;…...

[数组排序] LCR 164. 破解闯关密码

文章目录 1. 题目链接2. 题目大意3. 示例4. 解题思路5. 参考代码 1. 题目链接 LCR 164. 破解闯关密码 - 力扣&#xff08;LeetCode&#xff09; 2. 题目大意 描述&#xff1a;给定一个非负整数数组 nums。 要求&#xff1a;将数组中的数字拼接起来排成一个数&#xff0c;打印…...

05 Django 框架模型介绍(一)

文章目录 1、Django 模型简介2、Django 中创建并使用模型&#xff08;1&#xff09;新加一个名为 myapp 的应用&#xff08;2&#xff09;定义模型类&#xff08;2&#xff09;激活模型类&#xff08;3&#xff09;创建数据库迁移文件&#xff08;4&#xff09;应用迁移文件 3、…...

【简道云 -注册/登录安全分析报告】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞…...

【C++题解】1970. 判断是什么字符

欢迎关注本专栏《C从零基础到信奥赛入门级&#xff08;CSP-J&#xff09;》 问题&#xff1a;1970. 判断是什么字符 类型&#xff1a;字符串、字符型 题目描述&#xff1a; 从键盘读入一个字符&#xff0c;有可能是大写字母、小写字母、数字中的一种&#xff0c;请编程判断&…...

Python自动化操作Word文档详解

在日常办公和数据处理中&#xff0c;我们经常需要处理Word文档。手动操作Word文档可能会非常繁琐和耗时&#xff0c;而使用Python可以实现自动化操作&#xff0c;提高工作效率。本文将详细介绍如何使用Python自动化操作Word文档&#xff0c;包括读取、写入、修改和格式化等操作…...

常用滤波算法(二)-中位值滤波法

文章目录 一、中位值滤波法简介二、C语言实现中位值滤波法三、程序说明信号初始化&#xff1a;滤波窗口大小&#xff1a;内存分配&#xff1a;中位值滤波函数&#xff1a;中位值计算函数&#xff1a;内存释放&#xff1a; 四、总结 中位值滤波法&#xff0c;作为一种非线性滤波…...

HCIP--以太网交换安全(总实验)

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

C语言 | Leetcode C语言题解之第519题随机翻转矩阵

题目&#xff1a; 题解&#xff1a; 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季&#xff1a;第10章_其他SLAM系统 …...

《双指针篇》---快乐数

题目传送门 1.创建一个bitsum函数用于得到这个数每位的平方和。 2.令快指针等于bitsum&#xff08;n&#xff09; 3.慢指针等于n。 逐步令 fast bitSum(bitSum(fast)); slow bitSum(slow); 若最后fast等于slow&#xff0c;则且等于1.则return true。 否则return false。 cla…...

U盘引导丢失问题的处理办法

项目背景&#xff1a;在使用自制的u盘系统的时候经常遇到引导丢失的问题&#xff0c;那么咱们怎么解决这个问题呢&#xff0c;首先第一步通过手动引导u盘 进入系统&#xff0c;同时再进行引导区的修复这样u盘系统就可以正常工作了。 1 进入grub 的提示符下面&#xff0c;首先…...

layui tree customSelet选中的内容重写,查找父级

layui tree customSelet选中的内容重写&#xff0c;查找父级 需要重新源码 // 递归查找函数 // tree 所有数据 &#xff0c;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的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;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 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

如何在网页里填写 PDF 表格?

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

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

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;在自己的电…...