LeetCode_栈和队列相关OJ题目

✨✨所属专栏:LeetCode刷题专栏✨✨

✨✨作者主页:嶔某✨✨

上一篇:数据结构_栈和队列(Stack & Queue)-CSDN博客 

 有效的括号

解析:

这里我们用数组实现的栈来解决这个问题,在有了栈的几个基础接口之后,我们运用这几个接口解决问题。

首先新建一个栈并初始化,进入循环如果当前指针指向的字符元素为左括号 {([ 就入栈,反之就出栈,之后判断指针指向的字符是否和出栈的字符左右括号相匹配。

(  (top == '{'&& *s != '}')  ||  (top == '['&& *s != ']')  ||  (top == '('&& *s !=')')  )

 每次循环后s++,如果 *s != '\0' 就进行下一次循环。

写完后提交会发现当只有一个元素的时候这种写法是不能过的

 这里我们在else里面做一个判空,因为如果进了else里面,就说明这是个右括号,那么栈里面一定有其所对应的左括号,如果这时后栈为空,那么显然括号之间是不匹配的。这样就很好的解决了诸如此类的问题。

if(STEmpty(&S))
{
        STDestroy(&S);
        return false;

}

最后s遇到了 '\0' 循环结束,我们判断栈是否为空,如果为空返回true,否则栈中还有元素括号之间也是不匹配的。

return STEmpty(&S);

 可以这么理解这两段代码:一个判断了左括号是否多了,一个判断了右括号是否多了。

 示例代码:

 function/数据结构_栈 · 钦某/c-language-learning - 码云 - 开源中国 (gitee.com)icon-default.png?t=N7T8https://gitee.com/wang-qin928/c-language-learning/tree/master/function/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E6%A0%88

bool isValid(char* s)
{ST S;STInit(&S);while(*s){if(*s == '{' || *s == '[' || *s == '('){STPush(&S,*s);}else{if(STEmpty(&S)){STDestroy(&S);return false;}char top = STTop(&S);STPop(&S);if((top == '{'&& *s != '}')||(top == '['&& *s != ']') ||(top == '('&& *s !=')')){STDestroy(&S);return false;               }}s++;}return STEmpty(&S);
}

 用队列实现栈

解析:

这里我们使用数组实现的队列,只需要创建两个队列,把数据在两个队列之间互相导就行了。

定义结构体MyStack:

将mystack结构体里面创建两个队列q1、q2。

myStackCreate函数:

malloc出结构体pst的内存空间 ,并将q1、q2交给 QueueInit函数,返回这个结构体。

myStackPush函数:

将数据方放进 QueuePush,入队列q1就行。

myStackPop函数:

将q1队列的数据转到q2里面,最后剩一个数据不转,直接删除,之后再将数据从q2转到q1里面。返回删除的那个数据。

myStackTop函数:

和上一个函数一样,只不过myStackTop不删除数据,直接返回就好了。

myStackEmpty函数:

return !QueueSize(&(obj->q1));

 myStackFree函数:

这里一定要先释放q1、q2的空间之后再释放pst。

示例代码:

function/队列 · 钦某/c-language-learning - 码云 - 开源中国 (gitee.com)icon-default.png?t=N7T8https://gitee.com/wang-qin928/c-language-learning/tree/master/function/%E9%98%9F%E5%88%97


typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst = (MyStack*)malloc(sizeof(MyStack));QueueInit(&(pst->q1));QueueInit(&(pst->q2));return pst;
}void myStackPush(MyStack* obj, int x) {QueuePush(&(obj->q1),x);
}int myStackPop(MyStack* obj) {while(QueueSize(&(obj->q1)) != 1){QueuePush(&(obj->q2),QueueFront(&(obj->q1)));QueuePop(&(obj->q1));}int tmp = QueueFront(&(obj->q1));QueuePop(&(obj->q1));while(QueueSize(&(obj->q2))){QueuePush(&(obj->q1),QueueFront(&(obj->q2)));QueuePop(&(obj->q2));}return tmp;
}int myStackTop(MyStack* obj) {return QueueBack(&(obj->q1));
}bool myStackEmpty(MyStack* obj) {return !QueueSize(&(obj->q1));
}void myStackFree(MyStack* obj) {Destory(&(obj->q1));Destory(&(obj->q2));free(obj);
}

 用栈实现队列

解析:

此题与上题思路差不多,有一些细节上的改变,我们在代码里面细说。

定义结构体MyQueue:

创建两个栈st1、st2

myQueueCreate函数:

为MyQueue结构体malloc一块空间,将里面的st1、st2交给 STInit函数。

myQueuePush函数:

直接利用STPush函数插入就行。

myQueuePeek函数:

这里判断一下,如果st2为空的话,就将st1的数据转到st2来,取栈顶元素返回(转过来的时候数据会反过来)如果st2不为空,就直接返回st2栈顶元素。

myQueuePop函数:

这里本来也是要进行判断、转数据的,但是我们可以简化一下代码,直接调用myQueuePeek返回值存起来,这样st2必然就有数据,我们就可以直接pop掉st2里面的数据。

myQueueEmpty函数:

只有st1、st2同时为空,这个队列才为空。

myQueueFree函数:

先用 STDestroy释放掉st1、st2的空间,之后再free掉obj。

总结:此题目不用将st2的数据再转回到st1里,相当于st2是专门用来出数据的,st1专门用来入数据的。

示例代码:

function/数据结构_栈 · 钦某/c-language-learning - 码云 - 开源中国 (gitee.com)icon-default.png?t=N7T8https://gitee.com/wang-qin928/c-language-learning/tree/master/function/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E6%A0%88

typedef struct {ST st1;ST st2;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* Q = (MyQueue*)malloc(sizeof(MyQueue));STInit(&(Q->st1));STInit(&(Q->st2));return Q;
}void myQueuePush(MyQueue* obj, int x) {STPush(&(obj->st1),x);
}int myQueuePop(MyQueue* obj) {int tmp = myQueuePeek(obj);STPop(&(obj->st2));return tmp;
}int myQueuePeek(MyQueue* obj) {if(STEmpty(&(obj->st2))){while(!STEmpty(&(obj->st1))){STPush(&(obj->st2),STTop(&(obj->st1)));STPop(&(obj->st1));}return STTop(&(obj->st2));}else{return STTop(&(obj->st2));}
}bool myQueueEmpty(MyQueue* obj) {return (STEmpty(&(obj->st1)) && STEmpty(&(obj->st2)));
}void myQueueFree(MyQueue* obj) {STDestroy(&(obj->st1));STDestroy(&(obj->st2));free(obj);
}

本期博客到这里就结束了,如果有什么错误,欢迎指出,如果对你有帮助,请点个赞,谢谢!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/326457.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Chrome实用命令笔记】

文章目录 Chrome实用命令笔记1、chrome基本介绍2. 打开开发者工具(DevTools)方法一:快捷键方法二:右键菜单方法三:浏览器设置 2. 开发者工具面板Elements面板Console面板Sources面板Network面板Performance面板Memory面…

(done) Beam search

参考视频1:https://www.bilibili.com/video/BV1Gs421N7S1/?spm_id_from333.337.search-card.all.click&vd_source7a1a0bc74158c6993c7355c5490fc600 (beam search 视频) 参考博客1:https://jasonhhao.github.io/2020/06/19/…

Springboot项目如何创建单元测试

文章目录 目录 文章目录 前言 一、SpringBoot单元测试的使用 1.1 引入依赖 1.2 创建单元测试类 二、Spring Boot使用Mockito进行单元测试 2.1 Mockito中经常使用的注解以及注解的作用 2.2 使用Mockito测试类中的方法 2.3 使用Mockito测试Controller层的方法 2.4 mock…

通过 Java 操作 redis -- list 列表基本命令

目录 使用命令 lpush,lrange,rpush 使用命令 lpop 和 rpop 使用命令 blpop,brpop 使用命令 llen 关于 redis list 列表类型的相关命令推荐看Redis - list 列表 要想通过 Java 操作 redis,首先要连接上 redis 服务器&#xff…

电信网关配置管理系统 rewrite.php 文件上传致RCE漏洞复现

0x01 产品简介 中国电信集团有限公司(英文名称“China Telecom”、简称“中国电信”)成立于2000年9月,是中国特大型国有通信企业、上海世博会全球合作伙伴。电信网关配置管理系统是一个用于管理和配置电信网络中网关设备的软件系统。它可以帮助网络管理员实现对网关设备的远…

【Android】源码解析Activity的结构分析

源码解析Activity的结构分析 目录 1、Activity、View、Window有什么关联?2、Activity的结构构建流程3 源码解析Activity的构成 3.1 Activity的Attach方法3.2 Activity的OnCreate 4、WindowManager与View的关系总结 1、一个Activity对应几个WindowManage&#xff0…

【MySQL数据库开发设计规范】之字段设计规范

欢迎点开这篇文章,自我介绍一下哈,本人姑苏老陈 ,是一名JAVA开发老兵。 本文收录于 《MySQL数据库开发设计规范》专栏中,该专栏主要分享一些关于MySQL数据库开发设计相关的技术规范文章,定期更新,欢迎关注&…

【C++】string类的使用④(字符串操作String operations || 常量成员Member constants)

🔥个人主页: Forcible Bug Maker 🔥专栏: STL || C 目录 前言🔥字符串操作(String operations)c_strdataget_allocatorcopyfindrfindfind_first_offind_last_offind_first_not_offind_last_not…

Dockerfile实践java项目

目的:用java项目测试dockerfil部署(前提是安装好了docker) 部署准备文件如下 1. java项目 java项目demo地址 https://gitee.com/xiaoqu_12/dockerfileDemo.git 或者百度网盘直接下载打包好的jar包 链接:https://pan.baidu.com/s/…

ES扩缩容

ES扩容 1.1 页面扩容ES1 1.2 拷贝插件及ssl文件 JSON [ec_admin@kde-offline3 ~]$ sudo rsync -avP /usr/kde_ec/2.3.6.6-1/elasticsearch1/plugins/* kde-offline6:/usr/kde_ec/2.3.6.6-1/elasticsearch1/plugins/ ;echo $? [ec_admin@kde-offline3 ~]$ sudo rsync -avP /us…

JavaScript 进阶(一)

一、作用域 1. 局部作用域 (1)函数作用域 、 (2)块作用域 2. 全局作用域 3. 作用域链 g 作用域可以访问 f 作用域(子访问父),但是 f 作用域,不能访问 g 作用域(父…

内容与图像一对多问题解决

场景复现 分析: 其实这是两给表,一个内容表,一个图片表,一对多的关系。 解决思路: 1. 先上传图片拿到图片的List集合ids,返回值是集合的ids,给到前端 2. 再添加内容表的数据生成了id,遍历查…

工程师工具箱系列(3)Arthas

文章目录 工程师工具箱系列(3)Arthas安装与准备Arthas插件使用场景查看某个变量值ognl方式调用Bean方法tt(TimeTunel)方式调用Bean的方法ognl调用带参数方法 资源总览 工程师工具箱系列(3)Arthas Java诊断利器 安装与准备 window…

强化学习——马尔可夫过程的理解

目录 一、马尔可夫过程1.随机过程2.马尔可夫性质3.马尔可夫过程4.马尔可夫过程示例 参考文献 一、马尔可夫过程 1.随机过程 随机过程是概率论的“动态”版本。普通概率论研究的是固定不变的随机现象,而随机过程则专注于那些随时间不断变化的情况,比如天…

M 有效算法

M 有效算法 本题考验二分知识&#xff0c;思路是二分k的取值&#xff0c;就按第一组样例来说当我们k取值为1的时候我们遍历数组想让|8-x|<k1的话x的取值范围是7-9&#xff0c;想让|3-x|<k2的话x的取值范围是1-5&#xff0c;两者x的区间不重合&#xff0c;说明肯定没有x能…

测试项目实战--安享理财2(Jmeter接口测试)

说明&#xff1a; 1.访问地址&#xff1a; 本项目实战使用的是传智播客的安享理财项目&#xff08;找了半天这个项目能免费用且能够满足测试实战需求&#xff09; 前台&#xff1a;http://121.43.169.97:8081/ 后台&#xff1a;http://121.43.169.97:8082/ &#xff08;点赞收藏…

运筹系列92:vrp算法包VROOM

1. 介绍 VROOM is an open-source optimization engine written in C20 that aim at providing good solutions to various real-life vehicle routing problems (VRP) within a small computing time. 可以解决如下问题&#xff1a; TSP (travelling salesman problem) CVRP …

数字序列比大小 - 贪心思维

系列文章目录 文章目录 系列文章目录前言一、题目描述二、输入描述三、输出描述四、java代码五、测试用例 前言 本人最近再练习算法&#xff0c;所以会发布自己的解题思路&#xff0c;希望大家多指教 一、题目描述 A&#xff0c;B两个人万一个数字的游戏&#xff0c;在游戏前…

C++学习笔记3

A. 求出那个数 题目描述 喵喵是一个爱睡懒觉的姑娘&#xff0c;所以每天早上喵喵的妈妈都花费很大的力气才能把喵喵叫起来去上学。 在放学的路上&#xff0c;喵喵看到有一家店在打折卖闹钟&#xff0c;她就准备买个闹钟回家叫自己早晨起床&#xff0c;以便不让妈妈这么的辛苦…

Windows2016系统禁止关闭系统自动更新教程

目录 1.输入cmd--适合系统2016版本2.输入sconfig&#xff0c;然后按回车键3.输入5&#xff0c;然后按回车键4.示例需要设置为手动更新&#xff0c;即输入M&#xff0c;然后按回车键 1.输入cmd–适合系统2016版本 2.输入sconfig&#xff0c;然后按回车键 3.输入5&#xff0c;然后…