华师一附中OI组

标题: 队列和栈大楼 [打印本页]

作者: admin 时间: 2018-9-11 14:56
标题: 队列和栈大楼
队列和栈是常见的两种基本的线性数据结构，对于队列，

作者: admin 时间: 2018-9-11 15:01
广度优先搜索一般使用队列来实现的，深度优先搜索一般是用递归来实现的，其实也可以手工模拟一个栈来实现。比如有些典型的题目全搜索的题目，分解因数，最少乘法次数等等，采用不同的搜索方案可以得到不同的结果。
最少乘法次数：BFS http://hsyit.cn/forum.php?mod=viewthread&tid=35912
DFS http://hsyit.cn/forum.php?mod=viewthread&tid=3663
分解因数：http://hsyit.cn/forum.php?mod=viewthread&tid=36345

作者: admin 时间: 2018-9-11 15:47
表达式求值是栈的经典应用，一般的做法应该是将中缀表达式转成后缀表达式然后求值。
典型的练习题：
1、P1739 表达式括号匹配 http://hsyit.cn/forum.php?mod=viewthread&tid=36379
2、P1449 后缀表达式 http://hsyit.cn/forum.php?mod=viewthread&tid=36335
3、P1981 表达式求值 http://hsyit.cn/forum.php?mod=viewthread&tid=36378
4、P1054 等价表达式 http://hsyit.cn/forum.php?mod=viewthread&tid=35906

还有一个栈的应用就是手动模拟递归。大家可以试着写一个pmn的算法，但是不要用递归。

作者: admin 时间: 2018-9-11 15:52
优先队列，循环队列，单调队列，单调栈是队列和堆栈的变形使用，详情跳楼

欢迎光临华师一附中OI组 (http://hsyit.cn/)