一本通3.2队列

这一次,我会给大家讲讲队列,讲讲一些例题。主要的解题报告,下周见。

1.问题

常见的问题和疑惑有几个:

(1)队列已空,却继续q.front()或q.pop(),这会导致运行错误。

(2)别把priority_queue和普通(FIFO)的队列queue搞混了,特别是一些函数,如q.top()(优先队列的语句,栈也可以用),以及q.front()(FIFO的普通队列专利,只有它可以用),此外,q.back()语句仅限于普通队列。

(3)其实如何更好的定义一个队列也很重要,首推struct自定义变量,这样在bfs的时候,会更方便。队列大多数都是BFS的题,如果不是很急迫,或是不懂队列(这个嘛,可以去看看我的前几篇文章),就不要用数组。数组废空间,如果不是循环队列,就会造成大量的浪费;如果是循环队列,你会发现,控制数组大小不好弄。

(4)注意,特别是优先队列,注意他的定义,别搞错了。

(5) 给个建议,命名可以用首字母,如q、Q、que等。这样代码会清楚有条理,更不会遗忘一些变量的意思。

2.关于他的应用领域,无非就是BFS,如果是普通的一些队列题,一般不会太难,就按着他做就行了。

3.总结一下,队列的难度,远远没有DP高,dp是很烦人的,状态转移方程一定要搞好;而队列,尤其是BFS,一般可以套模板,比较简单,题目主题内容也比较单一,主要考察最短步数。

4.题目,粗糙一看,无非两个领域,传统队列问题,以及BFS。

似乎1332、1333、1334、1418嘛……比较传统,剩下的好像都是BFS。

1333,似乎也有点BFS的意思,但还是属于传统。

题目

1418,似乎出了些故障……

晚点我看看吧,今天就写到这。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

友情链接更多精彩内容