问题：假设有这样一个拥有3个操作的队列：1. EnQueue(v): 将v加入队列中2. DeQueue(): 使队列中的队首元素删除并返回此元素3. MaxElement: 返回队列中的最大元素
设计一种数据结构和算法，让MaxElement操作的时间复杂度尽可能地低。
方法：用两个栈来模拟队列
在代码中，，maxStackItemIndex代表栈中最大的数的下标
link2NextMaxItem[index]表示当前index这个下标代表的数字（当前是最大的）如果没有的话，那么最大的那个数字的下标
代码：
#include <iostream>#include <string>#include <set>using namespace std;#define MAXN 1000#define INF 10000000class Stack{public:Stack() {stackTop = -1;maxStackItemIndex = -1;}void push(int x) {stackTop++;if(stackTop > MAXN) ThrowException(); //如果超出了栈的范围，则抛出异常。else {stackItem[stackTop] = x;if(x > MAX()) {link2NextMaxItem[stackTop] = maxStackItemIndex;maxStackItemIndex = stackTop;} else link2NextMaxItem[stackTop] = -1;}}int pop() {int ret;if(stackTop < 0) ThrowException(); //如果超出了栈的范围，则抛出异常。else {ret = stackItem[stackTop];if(maxStackItemIndex == stackTop) maxStackItemIndex = link2NextMaxItem[stackTop];stackTop–;}return ret;}int MAX() {if(maxStackItemIndex >= 0) return stackItem[maxStackItemIndex];else return -INF;}private:int stackItem[MAXN];int stackTop;int link2NextMaxItem[MAXN];int maxStackItemIndex;};class Queue {public:int maxValue(int x, int y) {if(x > y) return x;else return y;}int MAX() {return maxValue(stackA.MAX(), stackB.MAX());}void push(int x) {stackB.push(x);}int pop() {if(stackA.empty()) {while(!stackB.empty()) stackA.push(stackB.pop());}return stackA.pop();}private:Stack stackA;Stack stackB;}
累死累活不说，走马观花反而少了真实体验，
