本文从漫画算法：最小栈的实现的评论区得到启发，有所感触，从而写下这篇博文.

题目预设

　　假设有这样一个拥有三个操作的队列: 　　　　1. EnQueue(v):将v加入队列中 　　　　2. DeQueue:使队列中的队首元素删除并返回此元素 　　　　3. MaxElement:返回队列中的最大元素 　　设计一种数据结构和算法，保证这三种方法的时间复杂度尽可能的小。

分析与解

解法一:(传统方式)

　　这个问题的关键在于MaxElement这个操作，也就是如何快速的取最大值和最小值。 　　很明显可以看出来:传统方式，利用一个数组或链表来存储队列的元素，利用两个指针分别指向队列的队首和队尾。时间复杂度:在队列的长度为N的条件下，时间复杂度为O(N^2)。

解法二:(最大堆)

　　因为要取最大值，可以考虑用最大堆来维护队列中的元素。队中的每个元素都有指针指向它的后续元素。这样，堆就可以很快实现返回最大元素的操作。同时保证队列的正常插入和删除。 　　MaxElem操作其实是维护一个最大堆，时间复杂度为O(1)，而入队和出队的操作的时间复杂度为O(log<sub>2</sub>N)。

　TIPS: 最大堆:根结点的键值是所有堆结点键值中最大者，且每个结点的值都比其孩子的值大。生成最大堆：最大堆通常都是一棵完全二叉树，因此我们使用数组的形式来存储最大堆的值，从1号单元开始存储，因此父结点跟子结点的关系就是两倍的关系。即：heap[father * 2] = heap[leftChild]; heap[father * 2 + 1] = heap[rightChild];

解法三:(双栈队列?)

　　 在解法三前，我们先总结一下解法三的优点:利用一个指针集合保持了队列中元素的相对大小关系。所以返回最大值只需要O(1)的时间复杂度。所以一种思路是我们去寻找一种新的保存队列中元素相对大小关系的指针集合，并且使得更新这个指针集合的时间复杂度更低。 　　而我们进行深思熟虑之后，发现栈可以做的更好。 　　对于栈来讲，Push和Pop操作都是在栈顶完成的，所以很容易维护栈中的最大值，让它的时间复杂度为O(1)。 Code：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class stack
{
public:

 stack()
 {
  stackTop = -1;
  maxStackItemIndex = -1;
 }
}