做电商设计在哪个网站接单,网站与建设实训报告,建设网站的申请信用卡分期,网站建设亿玛酷信赖前言 上篇博客我们讨论了栈和队列的有关结构#xff0c;本篇博客我们继续来讨论有关栈和队列习题 这些题算是经典了 #x1f493; 个人主页#xff1a;小张同学zkf ⏩ 文章专栏#xff1a;数据结构 若有问题 评论区见#x1f4dd; #x1f389;欢迎大家点赞#x1f44d… 前言 上篇博客我们讨论了栈和队列的有关结构本篇博客我们继续来讨论有关栈和队列习题 这些题算是经典了 个人主页小张同学zkf ⏩ 文章专栏数据结构 若有问题 评论区见 欢迎大家点赞收藏⭐文章 目录
1. 括号匹配问题
2.用队列实现栈
3.用栈实现队列
4.设计循环队列 1. 括号匹配问题 由题可知我们需要判断一对括号是否成立成立的话就返回true失败的话就返回false这道题乍一看不好判断其实我们可以用栈来解决栈是后进先出的原则我们可以判断如果是左括号的话让这个括号进栈如果是右括号的话让栈里的括号出栈与右括号匹对若匹对成功则继续判断下一个括号这里我们需要考虑极端情况假如括号都遍历完了栈内还有左括号代表此时左括号多不匹配所以还需要判断栈是否为空还有如果第一个入栈的括号若是右括号必定不匹配直接false。 思路已给出代码如下 对于c语言来说注意先把栈写好写好后再调用栈的函数后续c就不用这么麻烦了 2.用队列实现栈 这道题就是给你两个队列通过队列实现一个栈我们都知道栈是后进先出的原则而队列是先进先出的原则那如何用两个队列实现栈那 首先我们思考假如现在有两个队列q1和q2我们画图分析 根据图上操作要想实现栈的后进先出的原则我们在入栈时先用一个队列q1来做入栈操作若出栈由于后进先出的原则我们可以先把除最后一个元素剩下的元素全部导入q2然后再将还在q1的元素通过出队的方式实现出栈若继续入栈此刻元素都在q2那么就用q2实现入栈操作然后出栈时按照上面的操作来回导入就可以了。
所以出栈比较难其他操作都是常规的我们说一下出栈我们可以用假设法分为空的队列和非空的队列非空的队列前size-1的元素pop出来再push进空的队列再pop最后一个元素
对了判空条件是两个队里都没元素时此刻栈为空
代码如下 3.用栈实现队列 两个队列可以实现栈那两个栈如何实现队列那
队列是先进先出原则那对于栈来说后进先出若两个栈将第一个栈的所有元素全部导入第二个栈此刻我们想想比如第一个栈原本1,2,3,4现在导入第二个栈此刻是不是就是4,3,2,1此刻第二个栈若出栈的话正好符合了队列的先进先出
我们可以在画图看一下 其实对于两个栈将第一个栈导入另一个栈原本第一个栈的元素是后进先出的原则导入第二个栈就变成现进先出了
代码如下 4.设计循环队列
重头戏来了 循环队列就是在一个有限空间里重复利用如图 如图我们用两个指针指向数组头一个是队头指针head一个是队尾指针tailpush数据时tail相当于Tail指向的是最后一个元素的下一个位置·这一点跟栈栈顶元素有点类似当初始化为0时 指针指向最后一个元素的下一个位置pop的话移动头元素head就行了不过上面的图不现实因为队列空和满时对应的条件都一样都是headTail所以我们得找一个办法让这个条件不一样才能判空
一种是用一个size变量加加记录数据这是一种方法。
其实还有另一种方法我们可以多一个空间,开k1个空间但只能放k个元素 如图此刻若放满正好是第四个图相当于tail的下一个位置就是head那么我们是不是可以根据取模得到关系tail1%(k1)head达到这个条件就是满空的条件就很简单headTail 如果是返回尾元素就是tail指针指向的上一个位置tail-1但是我们得考虑如上图这种情况Tail回到前面但是此刻tail1越界了所以这时我们可以根据取模(Tail-1k1)%(k1) 就得到了尾元素的位置
头元素就是head指向的元素
OK剩下的操作就是常规操作代码如下 结束语 栈与队列经典习题就结束了有什么问题可私聊我里面的满足条件多想一想就能想明白特别是最后一道题 OK,本篇博客结束
