2019-08-08 洛谷第四课

• 栈 （STL&手写）

P1165 日志分析

思路：定义一个max数组，当有新的元素时，计算新的max，出站时返回前一个max即可
记录详情STL
记录详情手写

P1981 表达式求值

原来想的碰到+ ， 就直接加，没考虑连乘，改进后AC了
思路：碰到*，先不算，将数字存到一个栈里，碰到+把前面没算的都算了
记录详情

P1175 表达式的转换

问题：前缀、中缀、后缀表达式之间的转化，一般如何用程序实现？？

• 队列（STL&手写）
  P3662 Why Did the Cow Cross the Road II S
  不会写队列版的，只会用贪心算
  image.png
  image.png

记录详情
P1540 机器翻译
AC了，开一个queue模拟一下即可
记录详情 STL
记录详情 手写
问题：优先队列的STL，是不是可以在普及组中使用？如何手写？
“树求最大值可以用优先队列来写” 是什么意思？

• 优先队列（STL）
  P1090 合并果子
  每次合并最轻的两堆即可
  记录详情
• 链表（手写）
  P1996 约瑟夫问题
  能用优先队列实现，但对链表没感觉；目前感觉vector、队列、优先队列、栈用的比较熟，其它数据结构了解概念，但不太清楚如何使用；能不能请老师帮再讲一讲（链表、树的数据结构和算法）
  image.png

P1160 队列安排 （双链表）
P2776 [SDOI2007]小组队列

• 二叉树（手写）
  P1087 FBI树
  P1827 美国血统 American Heritage