3.7　队列中取最大值操作问题

假设有这样一个拥有三个操作的队列：

1．EnQueue(v)：将v加入队列中

2．DeQueue：使队列中的队首元素删除并返回此元素

3．MaxElement：返回队列中的最大元素

请设计一种数据结构和算法，让MaxElement操作的时间复杂度尽可能地低。

分析与解法

【解法一】

这个问题的关键在于取最大值的操作，并且得考虑当队列里面的元素动态增加和减少的时候，如何能够非常快速地把最大值取出。

显然，最直接的思路就是按传统方式来实现队列：利用一个数组或链表来存储队列的元素，利用两个指针分别指向队列的队首和队尾。如果采用这种方法，那么MaxElement操作需要遍历队列的所有元素。在队列的长度为N的条件下，时间复杂度为O（N）。

注：小飞看到这里时心想，在解法一的基础上，我们按照空间换时间的思路，多设置一个变量MaxVal，每入队一个元素，就更新一下MaxVal，使MaxVal总保存着队列中最大的元素。这样，MaxElement函数只需要返回MaxVal的值就可以了，这就实现了一种时间复杂度为O（1）的算法。想到这些，小飞感到很高兴。

你觉得小飞的想法对吗？

【解法二】

队列是遵守“先入先出”原则的一种复杂数据结构。其底层的数据结构不一定要用数组来实现，还可以使用其他特殊的数据结构来实现，以达到降低MaxElement操作复杂度的目的。

根据取最大值的要求，可以考虑用最大堆来维护队列中的元素。堆中每个元素都有指针指向它的后续元素。这样，堆就可以很快实现返回最大元素的操作。同时，我们也能保证队列的正常插入和删除。MaxElement操作其实就是维护一个最大堆，其时间复杂度为O（1）。而入队和出队操作的时间复杂度为O（log₂N）。

图3-10为这种解法的示意图。其中实线为普通最大堆的示意图，从中可以看出子节点都比父节点的值小。而箭头表示指针，节点用以描述插入队列的先后顺序。

图3-10　最大堆示意图

【解法三】

还能做得更好些吗？让我们再回忆一下解法二。其实，抽象一些地说，解法二之所以求最大值操作的速度比解法一快，是因为它利用一个指针集合保持了队列中元素的相对大小关系。所以返回最大值只需要O（1）的时间复杂度，而在元素入队或出队时，更新这个指针集合都需要O（log₂N）的时间复杂度。所以一种思路是我们去寻找一种新的保存队列中元素相对大小关系的指针集合，并且使得更新这个指针集合的时间复杂度更低。

让我们带着这个目标，考虑用其他的底层数据结构来实现“先入先出”的功能。由于栈是一个和队列极其相似的数据结构，我们不妨先看看栈。

对于栈来讲，Push和Pop操作都是在栈顶完成的，所以很容易维护栈中的最大值，它的时间复杂度为O（1）。其基本实现如下：

代码清单3-9

这里，维护一个最大值的序列（link2NextMaxItem）来保证Max操作的时间复杂度为O（1），相当于用空间复杂度换取了时间复杂度。

如果能够用栈有效地实现队列，而栈的Max操作又很容易实现，那么队列的Max操作也就能有效地完成了。那如何使用栈实现队列，基本操作的时间复杂度又是多少呢？

考虑使用两个栈来实现一个队列，设为栈A和栈B。

这样队列的类可以如下定义：

代码清单3-10

上述代码能够用栈来实现一个队列。出队的时候，如果A堆栈为空，那么“把B堆栈的数据都弹出并压入A堆栈”这个操作不是O（1）的，虽然如此，但从每个元素的角度来看，它被移动的次数最多可能有3次，这3次分别是：从B堆栈进入；当A堆栈为空时，从B堆栈弹出并压入A堆栈；从A堆栈被弹出。相当于入队经过一次操作，出队经过两次操作。所以这种方法的平均时间复杂度是线性的。

总结

通过这道题，我们了解到可以用不同的底层结构来实现队列这个抽象的容器，并且可以用空间换时间的方法来降低时间复杂度。读者不妨再试试其他方法，并比较不同方法的优劣。