问题

(来自编程之美3.7)实现一个有MaxElement()方法的队列，并使得MaxElement方法的时间复杂度尽可能的低。

初步想法

拿一个指针指向最大值，每次enqueue的时候更新这个指针。这个想法比较天真，当dequeue的时候，如果正好这个指针所指的元素要被删除，现在全队列中第二大的元素应该变成新的最大的元素，但是现在找不到。

优化

第一步

那么现在问题变成保证：

1. 当头部不是最大值时，随便dequeue。
2. 当头部是最大值时，他应该有指针指向除了他以外谁是最大的。

所以1)我们应该有一个指针始终指向当前最大值，2)另外每个元素自己拥有一个指针指向他后面的元素中的最大值next_max[]。

注意到2)中每个元素自己进入队列的时候是无法知道后面的元素的情况的，所以我们可以尝试利用一个后进先出的结构试着让每个元素知道他后面所有元素的情况。

比如我们现在有队列[3,1,2]。先push 2，最大值是2，没有比他小的next_max[0]=-1 。再push 1，最大值还是2，因为1比现在的最大值小，所以删除无所谓next_max[1]=-1。再push 3, 此时3>2 所以最大值变成了3，next_max[2]=0(指向2所在的位置)。

第二步

问题又来了，如果这时我们需要enqueue几个元素比如{4,7,5} 怎么办? 理论上我们得等到第一步那个stack清空后才能放入这几个元素。同时这几个新添加的元素中也可能有最大值, 我们也需要记录下来。这时我们可以回顾一下初步想法，当队列不发生dequeue时，我们完全可以只用一个变量记录最大值就好了。最后我们考虑到第一步的enqueue需要从后往前放，我们不妨使用一个普通的stack来存储enqueue进来但暂时还不能放入第一步的stack中的元素。

复杂度

一个元素的一个生命周期最多被弹3次，所以分摊复杂度是O(1)的。