今天内推腾讯实习生一面
其中问道一个问题是，怎样在不消除递归的情况下防止栈溢出？（无论如何都要使用递归）
面试的时候，一点都不知道，只能说使用循环来消除，但是那样不满足要求，后来看看这篇博客http://blog.zhaojie.me/2009/03/tail-recursion-and-continuation.html 才懂了。
还有一个不知道的问题是优先队列的实现，原来没有接触过这种数据结构，所以当时想了半天也不知道。。
看《数据结构与算法分析——C语言描述》中有提到，结果发现是我自己没有理解题目的意思。
实现方式可以见连接：http://www.cnblogs.com/wuchanming/p/3809496.html
《编程之美》中有这样一个题目：
队列中取最大值操作问题，题目描述：
假设有这样一个拥有3个操作的队列：
1 Enqueue(v): 将v加入队列
2 DeQueue：使队列中的队首元素删除并返回此元素
3 MaxElement：返回队列中的最大元素
请设计一种数据结构和算法，让MaxElement操作的时间复杂度尽可能地低。
队列是遵守“先入先出”原则的一种复杂数据结构。其底层的数据结构不一定要用数组来实现，还可以使用其他特殊的数据结构来实现，以达到降低MaxElement操作复杂度的目的。
分析与解法：
解法一
这个问题的关键在于取最大值的操作，并且考虑但队列里面的元素动态增加和减少的时候，如何能够非常快速地把最大值取出。
虽然，最直接的思路就是按传统方式来实现队列。利用一个数组或链表来存储队列的元素，利用两个指针分别指向队列的队首和队尾。如果采用这种方法，那么MaxElement操作需要遍历队列的所有元素。在队列的长度为N的条件下，时间复杂度为O（N）。
解法二
根据取最大值的要求，可以考虑用最大堆来维护队列中的元素。堆中每个元素都有指针指向它的后续元素。这样，堆就可以很快实现返回最大元素的操作。同时，我们也能保证队列的正常插入和删除。MaxElement操作其实就是维护一个最大堆，其时间复杂度为O（1）。而入队和出队操作的时间复杂度为O（lgN)
开始不太能理解，后来想想好像是这样的，比如，队列是先进先出的，所以用一种数据结构来记录元素的进出顺序，而使用最大堆来维持找到最大值的效率。假如使用queue来存放所有的数据，当入队的时候直接插入队尾，而最大堆也需要将加入的值放在堆的最后，然后进行调整，直到满足最大堆。如果是进行访问最大值，可以直接访问堆顶的元素。如果是进行出队操作，从队列的首部删除该元素，并在最大堆中找到该元素，删除之后，进行调整。这样既能够达到满足队列的“先进先出”，也能满足在O（1）的条件下访问到最大值。
解法三
曾经做过一种类似的题目是最小栈，也就是在O（1）的情况下访问到栈中的最小元素。如是想到也可以使用这种方式来实现优先队列，
如果使用两个数组分别存放，第一个数组按进入的顺序存放所有的元素，另一个数组中存放最大值的下标，另外还用一个变量记录当前的最大值下标。
实现代码：
class stack { public: stack() { stackTop=-1; maxStackItemIndex=-1; } void push(Type x) { stackTop++; if(stackTop>=Max) ; //栈满 else { stackItem[stackTop]=x; if(x>Max()) { link2NextMaxItem[stackTop]=maxStackItemIndex; maxStackItemIndex=stackTop; } else link2NextMaxItem[stackTop]=-1; } } Type Pop() { Type ret; if(stackTop<0) ThrowException(); //已经没有元素来，所以不能pop else { ret=stackItem[stackTop]; if(stackTop==maxStackItemIndex) { maxStackItemIndex=link2NextMaxItem[stackTop]; } stackTop--; } return ret; } Type Max() { if(maxStackItemIndex>=0) return stackItem[maxStackItemIndex]; else return -INF; } private: Type stackItem[MAXN]; int stackTop; int link2NextMaxItem[MAXN]; int maxStackItemIndex; };
这里，维护一个最大值的序列来保证Max操作的时间复杂度为O（1），相当于用空间复杂度换取了时间复杂度。
如果能够用栈有效第实现队列，而栈的Max操作又很容易，那么队列的Max操作也就能有效地完成了。
