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

栈和队列(一) 栈操作详解

文章目录

  • 一、物理结构和逻辑结构
  • 二、栈
    • 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 仅由括号 ‘( )[ ]{ }’ 组成

题目分析:

  1. 对于这个题我们需要将字符串内括号的左一半与右一半进行匹配,有"( { [ ] })“、”( ) [ ] { }“等多种情况都是符合情况的,也有像”( { ) }"这种不符合情况的都需要考虑。
  2. 如果是左括号则入栈
  3. 如果是右括号,取出栈顶元素与之匹配
  4. 如果右边括号匹配时栈内已经空了则数量不匹配
  5. 匹配结束后栈内不为空则数量不匹配

代码:

这里我们用上面实现的栈操作来完成

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栈的初始化栈的销毁入栈出栈获得栈顶元素获得栈的元素数判断栈空 三、利用栈解决问题 一、物理结构和逻辑结构 栈和队列都属于逻辑结构&#xff0c;它们既可以用数组实现也可以用链表…...

软考A计划-系统集成项目管理工程师-信息系统安全管理-下

点击跳转专栏>Unity3D特效百例点击跳转专栏>案例项目实战源码点击跳转专栏>游戏脚本-辅助自动化点击跳转专栏>Android控件全解手册点击跳转专栏>Scratch编程案例点击跳转>软考全系列点击跳转>蓝桥系列 &#x1f449;关于作者 专注于Android/Unity和各种游…...

Spark知识点总结

1. Spark支持哪几种运行模式&#xff1f; 本地模式&#xff08;Local Mode&#xff09;&#xff1a;在这种模式下&#xff0c;Spark在单个机器上运行。所有的Spark操作都在一个单独的JVM进程中进行。这种模式适合开发和测试&#xff0c;但不适合处理大规模的数据。 集群模式&a…...

vue el-input 使用 回车键会刷新页面的问题

场景&#xff1a; vue项目中 在输入框输入字符并按下回车键搜索时&#xff0c;不会进行搜索&#xff0c; 而是会刷新页面 原因&#xff1a; 当form表单中只有一个input时&#xff0c;按下回车建会自动触发页面的提交功能&#xff0c; 产生刷新页面的行为 解决&#xff1a; 在…...

【ARM64 常见汇编指令学习 12 -- ARM 汇编函数 的学习】

文章目录 1.1 ARM 汇编函数简介1.1.1 ARM 汇编标签 Label1.1.2 ARM 汇编函数属性指令1.1.3 UEFI 中的函数宏&#xff1a;ASM_FUNC1.1.3.1 UEFI ASM_FUNC 实现汇编函数 1.1.4 UEFI 预编译前缀宏 ASM_PFX 上篇文章&#xff1a;ARM64 常见汇编指令学习 11 – ARM 汇编宏 .macro 的…...

linux下软件安装 - 与GPT对话

1 cmake 没有uninstall 你是对的,CMake 默认情况下并没有提供 make uninstall 目标。这是因为 make install 操作是在特定的目录下进行安装的,CMake 不知道安装到了哪里以及哪些文件被安装了。因此,没有直接支持的 make uninstall 目标来进行卸载。 如果你想要卸载通过 mak…...

idea 2023 新版ui中git的相关操作

前两个月换了新电脑&#xff0c;下了最新版的idea发现可以切换一套新的ui了 切换新ui肯定不太习惯&#xff0c;很多操作都得重新摸索一下 在这里记录几个git相关的操作 忽略我下面截图中当前项目是js的后端项目…… 切换ui 首先说一下怎么切换新旧版ui&#xff0c;我这里就…...

vue3—SCSS的安装、配置与使用

SCSS 安装 使用npm安装scss&#xff1a; npm install sass sass-loader --save-dev 配置 配置到全局 &#x1f31f;附赠代码&#x1f31f; css: {preprocessorOptions: {scss: {additionalData:import "./src/Function/Easy_I_Function/Echarts/ToSeeEcharts/utill.…...

Godot 4 源码分析 - Path2D与PathFollow2D

学习演示项目dodge_the_creeps&#xff0c;发现里面多了一个Path2D与PathFollow2D 研究GDScript代码发现&#xff0c;它主要用于随机生成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流感病毒实验虚拟现实课件》是一种新型的教学模式&#xff0c;可以为学生提供更加真实和直观的流感病毒分离鉴定实验操作体验&#xff0c;从而提高学生的实验技能和工作效率。 《VR流感病毒实验虚拟现实课件》涉及了生物安全二级实验室(BSL-2)和流感病…...

python——案例10:认识if、elif、else

案例10&#xff1a;认识if、elif、elsenumfloat(input("输入数值&#xff1a;")) #用户输入数字if num>0:print("正数")elif num0:print("零") else:print("负数")#输出结果如下&#xff1a;输入数值&#xff1a;-1 负数 输入数值…...

Hadoop中命令检查hdfs的文件是否存在

Hadoop中命令检查hdfs的文件是否存在 在Hadoop中&#xff0c;可以使用以下命令检查HDFS文件是否存在&#xff1a; hadoop fs -test -e 其中&#xff0c;是要检查的HDFS文件的路径。 如果文件存在&#xff0c;命令返回0&#xff1b;如果文件不存在&#xff0c;命令返回非0值…...

计算机网络用户接入层设计

用户接入层为用户提供访问核心网络的能力&#xff0c; 为用户提供共享/交换的带宽分配&#xff0c;按照业主要求,并考虑到端口密度的要求以及 设备的性能价格比,建议选用 Catalyst 3524XL和 Catalyst 3548XL 工作组交换 机&#xff0c;分别放置于配线间中。如同一配线间需两台以…...

全志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 的区别&#xff0c;以及 Statefulset 的特点&#xff0c;能做的一些事情及一些注意事项 现在我们来尝试使用 Statefulset 来部署我们的应用&#xff0c;我们可以需要有应用程序&#xff0c;然后有持久化卷 开始使用 Statefuls…...

没有jodatime,rust怎么方便高效的操作时间呢?

关注我&#xff0c;学习Rust不迷路&#xff01;&#xff01; 当使用Rust进行日期操作时&#xff0c;可以使用 chrono 库。下面给出了二十个常见的日期操作的例子&#xff1a; 1. 获取当前日期和时间&#xff1a; use chrono::prelude::*;let current_datetime Local::now()…...

如何把pdf转成cad版本?这种转换方法非常简单

将PDF转换成CAD格式的优势在于&#xff0c;CAD格式通常是用于工程设计和绘图的标准格式。这种格式的文件可以在计算机上进行编辑和修改&#xff0c;而不需要纸质副本。此外&#xff0c;CAD文件通常可以与其他CAD软件进行交互&#xff0c;从而使得工程设计和绘图过程更加高效和精…...

MySQL常用函数方法

字符串函数 函数描述举例left(str, length)从左开始截取字符串&#xff0c;截取length个left(2023-08-04, 7) 2023-08right(str, length)从右开始截取字符串&#xff0c;截取length个 right(2023-08-04, 5) 08-04 substring(str, pos, length) substring&#xff08;被截取字…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

JavaScript 数据类型详解

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

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...