剑指 Offer（力扣版）-59-II-队列的最大值_力扣 链表 最大值

题目链接

题意：

定义一个新队列数据结构，支持入队，出队，查询三种操作，可以快速O(1)时间内查找队中最大值

思路：

在队列中添加一个链表，用于维护当前队列最大值，该链表指向该最大值出队后剩余列表的最大值。于是，每次最大元素出队时，该链表后移，即可找到下一个最大值，这样，出队和查询都变得异常简单，那么接下来就需要考虑一下入队构造这个链表的操作。

对于空队，显然，入队的值即为最大值。

接下来，如果入队的新元素比最大值大，则之前的最大值可以直接舍弃，新元素为最大值。反正，需要将新元素连到最大值的后方，当最大值出队时该元素即成为新的最大值。

不难发现，这样维护下来的链表是一个单调递减的链，因为每次链的前一个节点出队后，后一个节点才成为最大值，因此前一个节点一定比后一个节点大。

于是，每次入队操作即可总结为：从链尾开始向前遍历链，对于所有小的节点全都舍弃，然后将新节点接在末尾。

为了方便操作，用双向链表来实现这个数据结构，front和back模拟队首和队尾，p和pb模拟链头和链尾

该题有以下三大个坑点：

1.判断队中最大值操作和出队操作前需要提前判断队是否为空

2.当出队操作完成时若队空，需要将所有指针都清空

3.出队后，若出队元素为最大元素，将指针后移后需将移出的指针断链