栈和队列(一) 栈操作详解
文章目录
- 一、物理结构和逻辑结构
- 二、栈
- 1、什么是栈
- 2、栈中一些基本操作的实现
- Stack.h
- Stack.c
- 栈的初始化
- 栈的销毁
- 入栈
- 出栈
- 获得栈顶元素
- 获得栈的元素数
- 判断栈空
- 三、利用栈解决问题
一、物理结构和逻辑结构

栈和队列都属于逻辑结构,它们既可以用数组实现也可以用链表实现。
二、栈
1、什么是栈
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出(Last In First Out,简称LIFO)的原则。
进栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。

2、栈中一些基本操作的实现
利用数组来实现栈的基本操作

代码结构设计:
- Stack.h: 存放链表结构及需要用到的头文件,函数声明等
- Stack.c: 各种操作函数的具体实现
Stack.h
#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include<stdbool.h>
//方便修改类型
typedef int STDataType;
//栈
typedef struct Stack
{STDataType* a;//实现栈的数组int top;//栈顶int capacity;//栈容量
}ST;//栈的初始化
void STInit(ST* ps);
//栈的销毁
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获得栈顶元素
STDataType STTop(ST* ps);
//获得栈的元素数
int STSize(ST* ps);
//判断栈空
bool STEmpty(ST* ps);
Stack.c
#include "Stack.h"
栈的初始化
void STInit(ST* ps)
{assert(ps);ps->a = NULL;//栈顶元素的下一个ps->top = 0;ps->capacity = 0;
}
栈的销毁
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}
入栈
void STPush(ST* ps, STDataType x)
{assert(ps);//空间不足,扩容if (ps->capacity == ps->top){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType)*newCapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}//更新入栈后内容ps->a[ps->top] = x;ps->top++;
}

出栈
void STPop(ST* ps)
{assert(ps);assert(ps->top > 0);ps->top--;
}

获得栈顶元素
top初始化时是0,是栈顶元素的下一个位置,所以栈顶元素下标是top-1
STDataType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}
获得栈的元素数
top从0开始,栈内多一个元素它就加1,所以top与元素树大小一致
int STSize(ST* ps)
{assert(ps);return ps->top;
}
判断栈空
top等于0时栈空
bool STEmpty(ST* ps)
{return ps->top ==0 ;
}
三、利用栈解决问题
本题来自LeetCode:有效的括号
有效的括号

示例1:
输入:s=“( )”
输出:true
示例2:
输入:s=“( )[ ]{ }”
输出:true
示例3:
输入:s=“( ]”
输出:false
- 1 <= s.length <= 104
- s 仅由括号 ‘( )[ ]{ }’ 组成
题目分析:
- 对于这个题我们需要将字符串内括号的左一半与右一半进行匹配,有"( { [ ] })“、”( ) [ ] { }“等多种情况都是符合情况的,也有像”( { ) }"这种不符合情况的都需要考虑。
- 如果是左括号则入栈
- 如果是右括号,取出栈顶元素与之匹配
- 如果右边括号匹配时栈内已经空了则数量不匹配
- 匹配结束后栈内不为空则数量不匹配
代码:
这里我们用上面实现的栈操作来完成
bool isValid(char * s){ST st;STInit(&st);char topval;while(*s){if(*s=='('||*s=='{'||*s=='['){STPush(&st,*s);}else{//如果栈内为空说明数量不匹配if(STEmpty(&st)){STDestroy(&st);return false;}//取出栈顶元素,然后栈顶元素出栈topval=STTop(&st);STPop(&st);//匹配不成功的情况if((*s==')'&&topval!='(')|| (*s=='}'&&topval!='{')|| (*s==']'&&topval!='[')){STDestroy(&st);return false;}}s++;}//匹配完后如果栈内不为空说明数量不匹配bool ret=STEmpty(&st);STDestroy(&st);return ret;
}
相关文章:
栈和队列(一) 栈操作详解
文章目录 一、物理结构和逻辑结构二、栈1、什么是栈2、栈中一些基本操作的实现Stack.hStack.c栈的初始化栈的销毁入栈出栈获得栈顶元素获得栈的元素数判断栈空 三、利用栈解决问题 一、物理结构和逻辑结构 栈和队列都属于逻辑结构,它们既可以用数组实现也可以用链表…...
软考A计划-系统集成项目管理工程师-信息系统安全管理-下
点击跳转专栏>Unity3D特效百例点击跳转专栏>案例项目实战源码点击跳转专栏>游戏脚本-辅助自动化点击跳转专栏>Android控件全解手册点击跳转专栏>Scratch编程案例点击跳转>软考全系列点击跳转>蓝桥系列 👉关于作者 专注于Android/Unity和各种游…...
Spark知识点总结
1. Spark支持哪几种运行模式? 本地模式(Local Mode):在这种模式下,Spark在单个机器上运行。所有的Spark操作都在一个单独的JVM进程中进行。这种模式适合开发和测试,但不适合处理大规模的数据。 集群模式&a…...
vue el-input 使用 回车键会刷新页面的问题
场景: vue项目中 在输入框输入字符并按下回车键搜索时,不会进行搜索, 而是会刷新页面 原因: 当form表单中只有一个input时,按下回车建会自动触发页面的提交功能, 产生刷新页面的行为 解决: 在…...
【ARM64 常见汇编指令学习 12 -- ARM 汇编函数 的学习】
文章目录 1.1 ARM 汇编函数简介1.1.1 ARM 汇编标签 Label1.1.2 ARM 汇编函数属性指令1.1.3 UEFI 中的函数宏:ASM_FUNC1.1.3.1 UEFI ASM_FUNC 实现汇编函数 1.1.4 UEFI 预编译前缀宏 ASM_PFX 上篇文章:ARM64 常见汇编指令学习 11 – ARM 汇编宏 .macro 的…...
linux下软件安装 - 与GPT对话
1 cmake 没有uninstall 你是对的,CMake 默认情况下并没有提供 make uninstall 目标。这是因为 make install 操作是在特定的目录下进行安装的,CMake 不知道安装到了哪里以及哪些文件被安装了。因此,没有直接支持的 make uninstall 目标来进行卸载。 如果你想要卸载通过 mak…...
idea 2023 新版ui中git的相关操作
前两个月换了新电脑,下了最新版的idea发现可以切换一套新的ui了 切换新ui肯定不太习惯,很多操作都得重新摸索一下 在这里记录几个git相关的操作 忽略我下面截图中当前项目是js的后端项目…… 切换ui 首先说一下怎么切换新旧版ui,我这里就…...
vue3—SCSS的安装、配置与使用
SCSS 安装 使用npm安装scss: npm install sass sass-loader --save-dev 配置 配置到全局 🌟附赠代码🌟 css: {preprocessorOptions: {scss: {additionalData:import "./src/Function/Easy_I_Function/Echarts/ToSeeEcharts/utill.…...
Godot 4 源码分析 - Path2D与PathFollow2D
学习演示项目dodge_the_creeps,发现里面多了一个Path2D与PathFollow2D 研究GDScript代码发现,它主要用于随机生成Mob var mob_spawn_location get_node(^"MobPath/MobSpawnLocation")mob_spawn_location.progress randi()# Set the mobs dir…...
ardupilot 中坐标变换矩阵和坐标系变换矩阵区别
目录 文章目录 目录摘要1.坐标变换矩阵与坐标系变换矩阵摘要 本节主要记录ardupilot 中坐标变换矩阵和坐标系变换矩阵的区别,这里非常重要,特别是进行姿态误差计算时,如果理解错误,很难搞明白后面算法。 1.坐标变换矩阵与坐标系变换矩阵 坐标变换矩阵的本质含义:是可以把…...
VR内容研发公司 | VR流感病毒实验虚拟现实课件
由广州华锐互动开发的《VR流感病毒实验虚拟现实课件》是一种新型的教学模式,可以为学生提供更加真实和直观的流感病毒分离鉴定实验操作体验,从而提高学生的实验技能和工作效率。 《VR流感病毒实验虚拟现实课件》涉及了生物安全二级实验室(BSL-2)和流感病…...
python——案例10:认识if、elif、else
案例10:认识if、elif、elsenumfloat(input("输入数值:")) #用户输入数字if num>0:print("正数")elif num0:print("零") else:print("负数")#输出结果如下:输入数值:-1 负数 输入数值…...
Hadoop中命令检查hdfs的文件是否存在
Hadoop中命令检查hdfs的文件是否存在 在Hadoop中,可以使用以下命令检查HDFS文件是否存在: hadoop fs -test -e 其中,是要检查的HDFS文件的路径。 如果文件存在,命令返回0;如果文件不存在,命令返回非0值…...
计算机网络用户接入层设计
用户接入层为用户提供访问核心网络的能力, 为用户提供共享/交换的带宽分配,按照业主要求,并考虑到端口密度的要求以及 设备的性能价格比,建议选用 Catalyst 3524XL和 Catalyst 3548XL 工作组交换 机,分别放置于配线间中。如同一配线间需两台以…...
全志F1C200S嵌入式驱动开发(应用程序开发)
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】 我们在开发soc驱动的时候,很多情况下也要验证下当前的驱动功能是否正确。当然除了验证驱动功能之外,我们还要编写业务代码和流程代码。这中间就和各行各业有关了,有的是算法,有…...
人工智能学习07--pytorch23--目标检测:Deformable-DETR训练自己的数据集
参考 https://blog.csdn.net/qq_44808827/article/details/125326909https://blog.csdn.net/dystsp/article/details/125949720?utm_mediumdistribute.pc_relevant.none-task-blog-2~default~baidujs_baidulandingword~default-0-125949720-blog-125326909.235^v38^pc_releva…...
Statefulset 实战 1
上一部分与大家分享到 Statefulset 与 RplicaSet 的区别,以及 Statefulset 的特点,能做的一些事情及一些注意事项 现在我们来尝试使用 Statefulset 来部署我们的应用,我们可以需要有应用程序,然后有持久化卷 开始使用 Statefuls…...
没有jodatime,rust怎么方便高效的操作时间呢?
关注我,学习Rust不迷路!! 当使用Rust进行日期操作时,可以使用 chrono 库。下面给出了二十个常见的日期操作的例子: 1. 获取当前日期和时间: use chrono::prelude::*;let current_datetime Local::now()…...
如何把pdf转成cad版本?这种转换方法非常简单
将PDF转换成CAD格式的优势在于,CAD格式通常是用于工程设计和绘图的标准格式。这种格式的文件可以在计算机上进行编辑和修改,而不需要纸质副本。此外,CAD文件通常可以与其他CAD软件进行交互,从而使得工程设计和绘图过程更加高效和精…...
MySQL常用函数方法
字符串函数 函数描述举例left(str, length)从左开始截取字符串,截取length个left(2023-08-04, 7) 2023-08right(str, length)从右开始截取字符串,截取length个 right(2023-08-04, 5) 08-04 substring(str, pos, length) substring(被截取字…...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...
LRU 缓存机制详解与实现(Java版) + 力扣解决
📌 LRU 缓存机制详解与实现(Java版) 一、📖 问题背景 在日常开发中,我们经常会使用 缓存(Cache) 来提升性能。但由于内存有限,缓存不可能无限增长,于是需要策略决定&am…...
怎么让Comfyui导出的图像不包含工作流信息,
为了数据安全,让Comfyui导出的图像不包含工作流信息,导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo(推荐) 在 save_images 方法中,删除或注释掉所有与 metadata …...
