备战蓝桥杯---数据结构与STL应用（基础实战篇1）

话不多说，直接上题：

当然我们可以用队列，但是其插入复杂度为N,总的复杂度为n^2,肯定会超时，于是我们可以用链表来写，同时把其存在数组中，这样节点的访问复杂度也为o(1).下面是AC代码：

下面我们来一个栈的简单应用：

下面进行分析：

因为输出的位数一样，第一位肯定为栈中的最大值，此时栈中可能已经有其他元素，那我们是选择弹出还是继续添加，注意到，我们要让第二位尽可能大，而我们只有两种选择1.选它自己2.选后面序列的最大值，因此重复这个过程并维护好后缀最大值即可。

下面是AC代码：

让我们再来一道今典的题吧：

后缀表达式避免了括号，我们只要把数值依次放入栈中，遇到运算符就取栈顶两元素，运算后放回即可。

我们再来一题：

我们不妨把a看成（，b看成），于是问题转换成括号匹配问题，我们用计数最后与0判断即可。

下面是AC代码：