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

数据结构《栈》

数据结构《栈》

  • 1、栈的概念及结构
    • 2、栈的实现
      • 3、练习:

1、栈的概念及结构

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端
称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶
出栈:栈的删除操作叫做出栈。出数据也在栈顶

在这里插入图片描述

2、栈的实现

栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的
代价比较小。

在这里插入图片描述

进栈、出栈展示:
在这里插入图片描述

实现栈,最好声明与定义分开成俩个文件来处理(头文件,h(介绍接口),实现文件.c(实现接口功能))

1、头文件.h

#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>typedef int type;
#define N 10;
//静态栈(不常用,所以我们要实现的是动态栈)
typedef struct Stack
{type arr[N];int top;//栈顶
}Stack;//动态栈
typedef struct Stack
{type* a;int top;int capacity;
}sl;// 初始化栈
void Slint(sl* p);
// 入栈
void pushpop(sl* p, type x);
// 出栈
void STpop(sl* p);
// 获取栈顶元素
type STTop(sl* p);
// 获取栈中有效元素个数
int STsize(sl* p); 
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
bool empty(sl* p);
// 销毁栈
void destroy(sl* p);

实现文件.c

void Slint(sl* p)
{assert(p);p->a = NULL;p->capacity = 0;p->top = 0;
}void pushpop(sl* p, type x)
{assert(p);if (p->top == p->capacity){int newcapacity = p->capacity == 0 ? sizeof(type) : 2 * p->capacity;type* new = (type*)realloc(p->a, sizeof(type) * newcapacity);if (new == NULL){perror("realloc fail");return;}p->a = new;p->capacity = newcapacity;}p->a[p->top] = x;p->top++;}void STpop(sl* p)
{assert(p);p->top--;
}type STTop(sl* p)
{assert(p);assert(p->top > 0);return p->a[p->top - 1];
}bool empty(sl* p)
{assert(p);return p->top == 0;
}void destroy(sl* p)
{free(p->a);p->a = NULL;p->capacity = 0;p->top = 0;
}int STsize(sl* p)
{assert(p);return p->top;
}

3、练习:

括号匹配问题

第一步->实现一个栈,在用栈的后进先出特性来匹配括号。
情况1:如果为‘(’、‘[’、‘{’。左括号入栈

情况2:如果为‘)’,‘}’,‘]’右括号与栈顶匹配

//实现一个栈
typedef char type;typedef struct Stack
{type* a;int top;int capacity;
}sl;void Slint(sl* p);void destroy(sl* p);void pushpop(sl* p, type x);void STpop(sl* p);type STTop(sl* p);bool empty(sl* p);int STsize(sl* p);void Slint(sl* p)
{assert(p);p->a = NULL;p->capacity = 0;p->top = 0;
}void pushpop(sl* p, type x)
{assert(p);if (p->top == p->capacity){int newcapacity = p->capacity == 0 ? sizeof(type) : 2 * p->capacity;type* new = (type*)realloc(p->a, sizeof(type) * newcapacity);if (new == NULL){perror("realloc fail");return;}p->a = new;p->capacity = newcapacity;}p->a[p->top] = x;p->top++;}void STpop(sl* p)
{assert(p);p->top--;
}type STTop(sl* p)
{assert(p);assert(p->top > 0);return p->a[p->top - 1];
}bool empty(sl* p)
{assert(p);return p->top == 0;
}void destroy(sl* p)
{free(p->a);p->a = NULL;p->capacity = 0;p->top = 0;
}int STsize(sl* p)
{assert(p);return p->top;
}
//匹配括号
bool isValid(char* s) {sl s3;Slint(&s3);while (*s){if (*s == '(' || *s == '{' || *s == '[')//情况1{pushpop(&s3, *s);}else//情况2{if(empty(&s3)){return false;}char top = STTop(&s3);STpop(&s3);if ((top == '(' && *s != ')') || (top == '[' && *s != ']') || (top == '{' && *s != '}')){return false;}}s++;}bool ret=empty(&s3);//判断栈有没有数据destroy(&s3);return ret ;}
}

相关文章:

数据结构《栈》

数据结构《栈》 1、栈的概念及结构2、栈的实现3、练习: 1、栈的概念及结构 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶&#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO&…...

说一说mysql的having?和where有什么区别?

在 MySQL 中&#xff0c;HAVING 子句和 WHERE 子句都是用于过滤查询结果的&#xff0c;但它们之间有一些重要的区别。下面我将详细介绍这两个子句的区别以及它们的使用场景。 1. HAVING 子句 作用: HAVING 子句用于过滤聚合后的结果集。它通常与 GROUP BY 子句一起使用&#x…...

LeetCode45. 跳跃游戏 II

题目链接&#xff1a; 45. 跳跃游戏 II - 力扣&#xff08;LeetCode&#xff09; 思路分析&#xff1a;这属于上一题的变种&#xff0c;思路有所不同&#xff0c;要用到贪心的思想。从第一步开始&#xff0c;在可以跳跃的范围内&#xff0c;选择能够到达最远位置的点将其作为…...

算法打卡 Day19(二叉树)-平衡二叉树 + 二叉树的所有路径 + 左叶子之和 + 完全二叉树的节点个数

Leetcode 101-平衡二叉树 文章目录 Leetcode 101-平衡二叉树题目描述解题思路 Leetcode 257-二叉树的所有路径题目描述解题思路 Leetcode 404-左叶子之和题目描述解题思路 Leetcode 222-完全二叉树的节点个数题目描述解题思路 题目描述 https://leetcode.cn/problems/balanced…...

国际以太网专线 (IEPL)/国际专线(IPLC)-全球覆盖,无界沟通

中国联通国际公司产品&#xff1a;国际以太网专线 (IEPL)/国际专线&#xff08;IPLC&#xff09;—— 跨境数据传输的坚实桥梁 在全球化日益加深的今天&#xff0c;跨境、跨地域的数据传输需求激增&#xff0c;企业对数据传输的速度、安全性和稳定性提出了前所未有的高要求。中…...

信息安全管理知识体系攻略(至简)

信息安全管理知识体系主要包括信息安全管理体系、信息安全策略、信息安全系统、信息安全技术体系等。 一、信息安全管理 1、信息安全管理体系&#xff08;ISMS&#xff09;。ISO27001是国际标准化组织&#xff08;ISO&#xff09;和国际电工委员会&#xff08;ICE&#xff09…...

HCIE学习笔记:IPV6 地址、ICMP V6、NDP 、DAD (更新补充中)

系列文章目录 提示&#xff1a;写完文章后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 系列文章目录前言一、IPV4、IPv6包头对比1. IPV4包头2.IPv6包头3.IPV6扩展包头 二、IPV6基础知识地址结构、地址分类三、ICMPV4、ICMPV61、 lnternet控…...

人工智能】Transformers之Pipeline(九):物体检测(object-detection)

目录​​​​​​​ 一、引言 二、物体检测&#xff08;object-detection&#xff09; 2.1 概述 2.2 技术原理 2.3 应用场景 2.4 pipeline参数 2.4.1 pipeline对象实例化参数 2.4.2 pipeline对象使用参数 2.4 pipeline实战 2.5 模型排名 三、总结 一、引言 pipel…...

[SWPUCTF 2021 新生赛]easy_md5

分析代码&#xff1a;1.包含flag2.php 2.GET传name&#xff0c;POST传password $name ! $password && md5($name) md5($password) 属于MD5绕过中的php 弱类型绕过 解题方法: 方法一 import requests# 网站的URL url "http://node7.anna.nssctf.cn:28026&q…...

Redis面试题大全

文章目录 Redis有哪几种基本类型Redis为什么快&#xff1f;为什么Redis6.0后改用多线程?什么是热key吗&#xff1f;热key问题怎么解决&#xff1f;什么是热Key&#xff1f;解决热Key问题的方法 什么是缓存击穿、缓存穿透、缓存雪崩&#xff1f;缓存击穿缓存穿透缓存雪崩 Redis…...

【langchain学习】BM25Retriever和FaissRetriever组合 实现EnsembleRetriever混合检索器的实践

展示如何使用 LangChain 的 EnsembleRetriever 组合 BM25 和 FAISS 两种检索方法&#xff0c;从而在检索过程中结合关键词匹配和语义相似性搜索的优势。通过这种组合&#xff0c;我们能够在查询时获得更全面的结果。 1. 导入必要的库和模块 首先&#xff0c;我们需要导入所需…...

【C语言】预处理详解(上)

文章目录 前言1. 预定义符号2. #define 定义常量3. #define定义宏4. 带有副作用的宏参数5. 宏替换的规则 前言 在讲解编译和链接的知识点中&#xff0c;我提到过翻译环境中主要由编译和链接两大部分所组成。 其中&#xff0c;编译又包括了预处理、编译和汇编。当时&#xff0c…...

uni-app内置组件(基本内容,表单组件)()二

文章目录 一、 基础内容1.icon 图标2.text3.rich-text4.progress 二、表单组件1.button2.checkbox-group和checkbox3.editor 组件4.form5.input6.label7.picker8.picker-view 和 picker-view-column9.radio-group 和 radio10.slider11.switch12.textarea 一、 基础内容 1.icon…...

linux搭建redis超详细

1、下载redis包 链接: https://download.redis.io/releases/ 我以7.0.11为例 2、上传解压 mkdir /usr/local/redis tar -zxvf redis-7.0.11.tar.gz3、进入redis-7.0.11&#xff0c;依次执行 makemake install4、修改配置文件redis.conf vim redis.conf为了能够远程连接redis…...

Flink-DataWorks第二部分:数据集成(第58天)

系列文章目录 数据集成 2.1 概述 2.1.1 离线&#xff08;批量&#xff09;同步简介 2.1.2 实时同步简介 2.1.3 全增量同步任务简介 2.2 支持的数据源及同步方案 2.3 创建和管理数据源 文章目录 系列文章目录前言2. 数据集成2.1 概述2.1.1 离线&#xff08;批量&#xff09;同步…...

4个从阿里毕业的P7打工人,当起了包子铺的老板

吉祥知识星球http://mp.weixin.qq.com/s?__bizMzkwNjY1Mzc0Nw&mid2247483727&idx1&sndb05d8c1115a4539716eddd9fde4e5c9&chksmc0e47813f793f105017fb8551c9b996dc7782987e19efb166ab665f44ca6d900210e6c4c0281&scene21#wechat_redirect 《网安面试指南》h…...

javaweb_07:分层解耦

一、三层架构 &#xff08;一&#xff09;基础 在请求响应中&#xff0c;将代码都写在controller中&#xff0c;看起来内容很复杂&#xff0c;但是复杂的代码总体可以分为&#xff1a;数据访问、逻辑处理、接受请求和响应数据三个部分。在程序中我们尽量让一个类或者一个方法…...

调用 Python 开源库,获取油管英文视频的手动或自动英文srt字幕,以及自动中文简体翻译srt字幕

前提条件 非常抱歉&#xff0c;这个程序就是个雏形&#xff0c;非常不完善&#xff0c;输入需要手动编辑&#xff0c;凑活着可以用&#xff0c;请自己完善吧。 开源声明&#xff1a;此文代码引用了一个开源MIT License的Python库&#xff0c;其他代码是本人自写自用。你可以随…...

UDP协议实现通信与数据传输(创建客户端和服务器)

目录 一、UDP &#xff08;传输层&#xff0c;用户数据报协议&#xff09; 二、服务器Server的创建 三、客户端Client的创建 四、效果实现&#xff08;描述&#xff09; 一、UDP &#xff08;传输层&#xff0c;用户数据报协议&#xff09; UDP&#xff08;User Datagram Pr…...

【红黑树】

红黑树 小杨 红黑树的概念 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但在每个结点上增加一个存储位表示结点的颜色&#xff0c;可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制&#xff0c;红黑树确保没有一条路径会比其他路径长出俩倍&am…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...