这一次,我会给大家讲讲队列,讲讲一些例题。主要的解题报告,下周见。
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,似乎出了些故障……
晚点我看看吧,今天就写到这。