【算法】队列与栈就是这么简单(结束篇)

作者: | 更新日期:

前面学习了队列和栈的基础知识和简单实践,现在来看看高级用法吧。

本文首发于公众号:天空的代码世界,微信号:tiankonguse

一、背景

之前写了五篇文章来讲解了《数组就是这么简单》系列,后来写了一系列堆栈的文章,如《队列就是这么简单》、《栈理论就是这么简单》、《栈DFS就是这么简单》。
这里写一篇堆栈的结束篇,主要以练习题为主,各种题型都举一个。
如果这些题大家明白了,那堆栈以后就再也不需要害怕了。

PS1:清明节三天回家了,一直在陪家人,所以没写文章。
PS2:后来的前两天,工作上事情比较多,现在才把总结篇写出来。
PS3:回家的几天,思考了两个问题,接下来的两篇文章就写我思考的东西吧。

二、用栈实现队列

题意:顾名思义,使用栈这个数据结构来实现队列。

思路:栈的特征是后进后出,而队列的特征是先进先出。
对于进队列操作,无所谓,直接放在进栈即可。
而对于出队列操作,就有问题了:需要删除栈最里面的那个元素。

大家想一想,假设你有一摞盘子,一次只能拿一个盘子。现在要得到最底下的盘子,该如何操作呢?
很容易想到,一个一个的把盘子拿出来,剩余之后一个的时候,就得到最底下的盘子。
然后在一个一个的把盘子放回去,这样就把最底下的盘子拿出来了,而上面的盘子顺序保持不变。

所以这里,你要做的也是准备一个临时栈。
先把上面的数据一个个移到临时栈,得到最底下的元素后,把剩余的再一个个恢复。

三、用队列实现栈

题意:与栈实现队列类似,这里是队列实现栈。

思路:和栈实现队列完全一样,找一个临时队列来折腾即可。

四、字符串解码

题意:给一个规则k[encoded_string],代表对中括号里的数据进行重复k次。
中括号的数据可能嵌套的有这个规则。
求展开后的字符串。

思路:最基础的递归思想。
输入数据可能是aaa12[ccc34[bbb]ddd]eee

所以这里要分几种情况。
一种是纯字符串,累积到答案上即可。
一种是num[],先读数字,然后遇到做括号,递归读括号的字符串即可。
这里的关键是遇到]时,代表当前递归结束,这个是唯一的递归出口。

五、图像渲染

题意:给一个二维矩阵、一个坐标、一个值X,将和坐标值相等的连续区域,都修改为给的值X

思路:标准的搜索题,之前你们应该已经做过孤岛的题了。
这道题和那道题完全一样,使用栈或者队列都可以做。

六、01 矩阵

题意:给一个0/1矩阵,求每个位置离0的最近距离。

思路:求最值,BFS搜索即可。
这里的特殊之处是起点有很多。

七、钥匙和房间

题意:给出每个房间里的钥匙,求是否可以从第一个房间可以所有房间。

思路:问是否到达,那就是孤岛问题(是否覆盖所有房间)。
使用栈或者队列都可以,搜索即可。

八、最后

做了这六道题,其实我们可以总结出一些队列和栈题目的题型来。

第一种:嵌套规则型。
由于嵌套的存在,一般都需要递归去解决。
因为递归其实就是一种嵌套。

第二种:连通题型。
这种题型的变种很多。
比如从起点按照一定的规则可以到达哪些点或者到达点的最大个数。
比如地图满足规则的最大连通值。

这类题型有一个特征就是对于能到达的点,对先后顺序没有要求。
这个使用栈或者队列都可以解决。

第三种:最优值题型。
对于最优值问题,一般都是使用BFS广度优先搜索解决。

总结一下,你使用队列和栈,可以解决三类问题:递归类问题、地图连通性问题、最优值问题。

-EOF-

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面关注公众号进行留言。

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越