问题：

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

1. EnQueue(v): 将v加入队列中

2. DeQueue(): 使队列中的队首元素删除并返回此元素

3. MaxElement: 返回队列中的最大元素

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

#include<iostream>
#include<limits.h>
using namespace std;

class Stack
{
	public:
		Stack()
		{
			stackTop = -1;
			maxStackItemIndex = -1;
		}
		void Push(int x)
		{
			if(stackTop >= MAXN - 1)return;
			stackItem[++stackTop] = x;
			if(x > Max())
			{
				link2NextMaxIten[stackTop] = maxStackItemIndex;//保存下一个最大值的位置
				maxStackItemIndex = stackTop;//保存当前最大值
			}
			else link2NextMaxIten[stackTop] = -1;
		}
		int Pop()
		{
			if(stackTop >= 0)
			{
				int value = http://www.mamicode.com/stackItem[stackTop];>
对比：剑指offer之取栈中最小值操作
题目：定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。
分析：我们需要一个辅助栈。每次push一个新元素的时候，同时将最小元素（或最小元素的位置。考虑到栈元素的类型可能是复杂的数据结构，用最小元素的位置将能减少空间消耗）push到辅助栈中；每次pop一个元素出栈的时候，同时pop辅助栈。具体代码如下
template<class T>
class Stack
{
	public:
		void push(const T& value)
		{
			value_stk.push(value);
			if(!min_stk.empty())
			{
				if(value < min_stk.top())min_stk.push(value);
				else min_stk.push(min_stk.top());
			}
			else min_stk.push(value);
		}
		void pop()
		{
			value_stk.pop();
			min_stk.pop();
		}
		T min()const
		{
			assert(!value_stk.empty() && !min_stk.empty());
			return min_stk.top();
		}
	private:
		stack<T> value_stk;//存放数据的栈
		stack<T> min_stk;//存放最小值的栈
};
两个队列实现一个堆栈：
思路：整个过程中保持一个队列有数据，一个队列为空。push的时候往有数据的一个对列中加入，pop的时候，把有数据的队列除最后一个元素以外的push到另一个空队列中，最后一个元素删除，用inputQueue和outputQueue指针分别指向这两个队列
template <class T>
class Stack
{
	public:
		bool empty()
		{
			return q1.size() == 0 && q2.size() == 0;
		}
		void push(const T& value)
		{
			queue<T>* inputQueue = &q1;
			if(q1.size() == 0)inputQueue = &q2;
			inputQueue -> push(value);
		}
		T top()
		{
			queue<T>* inputQueue,*outputQueue;
			if(q1.size() == 0)
			{
				inputQueue = &q2;
				outputQueue = &q1;
			}
			else 
			{
				inputQueue = &q1;
				outputQueue = &q2;
			}
			assert(inputQueue->size() > 0);
			while(inputQueue->size() > 1)
			{
				outputQueue->push(inputQueue->front());
				inputQueue->pop();
			}
			T value = http://www.mamicode.com/inputQueue->front();>