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

【数据结构】栈和队列OJ面试题

20. 有效的括号 - 力扣(LeetCode)

思路:由于C语言没有栈的接口,所以我们需要自己造一个“模子”。我们直接copy之前的实现的栈的接口就可以了(可以看我之前的博客【数据结构】栈和队列-CSDN博客copy接口),同时要注意要将typedef的STDataType从int类型改成char类型。在此之后,依次取出字符串中的字符判断,如果是左括号,则入栈。如果是右括号,则依次和栈顶字符去进行配对,然后出栈。再进行判断,配对则返回false,否则判断下一个字符。再while循环结束后还要再一次判空,排除栈中还有字符未进行判断的情况。

225. 用队列实现栈 - 力扣(LeetCode)

思路:由于C语言没有队列的接口,所以同样也需要我们自己造出一个“模子”来。再【数据结构】栈和队列-CSDN博客这篇博客中同样也有关于队列的接口,再这里我们直接copy一下队列的接口。

关于用队列实现栈,我们的思路是这样的,首先,创建出两个队列,一个队列用来在出栈时拷贝,一个队列用来在出栈时接受拷贝,所以这就要求一个队列必须是空的,而另一个队列的功能就是扮演栈的角色(因为队列出入数据是先进先出的,栈出入数据是先进后出的,所以在数据出栈的时候,只能用队列的拷贝来实现栈的数据出栈)。其他接口直接使用队列的接口就基本可以完成。

另外,要注意的是,在最后销毁栈的时候,需要先销毁两个队列再销毁栈,以免出现有野指针的情况。

 

232. 用栈实现队列 - 力扣(LeetCode)

思路:这道题同样需要用之前写的栈造一个“模子”。在解决这道题目时,需要我们创建两个栈去实现(st1用来存放数据,st2用来导数据)。当我们pop数据的时候,需要先将创建好的st1中的数据依次出栈到st2的栈中,然后将st2中的栈顶数据pop掉 ,最后将st2中的数据重新导回到st1中。在实现myQueuePeek(myQueuePeek接口要求我们返回队列开头的元素)接口的时候也是同样的方法,先将st1中的数据导到st2中,只不过接下来不需要pop栈顶元素,只需要记录下栈顶元素,然后再导回st1中,最后再返回记录下的元素就好了。其他的接口用之前实现栈的接口就可以基本解决了。

 

622. 设计循环队列 - 力扣(LeetCode)

思路:在这道题目中,我们采用顺序表的方法来完成。首先需要动态申请一个数组,然后初始化结构体。结构体中的head指向数组中的第一个节点,tail指向数组中最后一个节点的下一个节点,k的意思是数组中一共有k个数据。这里有接口需要我们判空和判满,但是如果就按这种思路写下去的话,我们会发现判空和判满的条件是一样的,都是head==tail。

那么我们应该如何去解决这个问题呢?这里我们有两种解决方案。第一种是在多开一个数组的空间,这样当队列满的时候的判空条件就变成了tail+1==head了,就避免了判空和判满条件一样的情况了。第二种方法是加一个size去判断队列中数据的个数。在此我们采用第一种方法来完成代码。

还需要注意的一个接口是取队尾的接口,这个接口需要取tail前一个结点,但是有一种特殊的情况就是tail是数组中第一个空间,这时候tail在-1的话就会变成-1,而不是指向第5块空间。这是我们可以进行一个判断,如果tail是第一块空间,那么则返回地5块空间的数据,否则返回第tail-1块的空间就可以了。或者我们可以取第((tail-1)+(k+1))%(k+1)个数据就是队列的队尾数据。

http://www.lryc.cn/news/348485.html

相关文章:

  • 【联邦学习——手动搭建简易联邦学习】
  • Springboot项目如何创建单元测试
  • Win10 如何同时保留两个CUDA版本并自由切换使用
  • 实验室纳新宣讲会(java后端)
  • class常量池、运行时常量池和字符串常量池的关系
  • Java | Leetcode Java题解之第88题合并两个有序数组
  • 韵搜坊(全栈)-- 前后端初始化
  • Android:资源的管理,Glide图片加载框架的使用
  • conll-2012-formatted-ontonotes-5.0中文数据格式说明
  • SpringBoot集成Seata分布式事务OpenFeign远程调用
  • 视觉检测系统,是否所有产品都可以进行视觉检测?
  • 通过金山和微软虚拟打印机转换PDF文件,流程方法及优劣对比
  • 采用java+B/S开发的全套医院绩效考核系统源码springboot+mybaits 医院绩效考核系统优势
  • 驱动开发-用户空间和内核空间数据传输
  • 【408精华知识】速看!各种排序的大总结!
  • 【STM32 |程序实例】按键控制、光敏传感器控制蜂鸣器
  • Spring boot使用websocket实现在线聊天
  • 品牌设计理念和logo设计方法
  • Python | Leetcode Python题解之第88题合并两个有序数组
  • vscode新版本remotessh服务端报`GLIBC_2.28‘ not found解决方案
  • 盘他系列——oj!!!
  • 洛谷 P2657 [SCOI2009] windy 数 题解 数位dp
  • Python爬虫入门:网络世界的宝藏猎人
  • 【NodeMCU实时天气时钟温湿度项目 6】解析天气信息JSON数据并显示在 TFT 屏幕上(心知天气版)
  • 重构四要素:目的、对象、时机和方法
  • 基于Echarts的大数据可视化模板:服务器运营监控
  • Python3 笔记:Python的常量
  • 【Linux】自动化构建工具make/Makefile和git介绍
  • C语言—关于字符串(编程实现部分函数功能)
  • picoCTF-Web Exploitation-Trickster