栈和队列：实现一个栈，O(1)时间复杂度获取栈内最大元素

实现一个栈，获取栈内最大元素

题目：实现一个栈，使栈的Push、Pop Top和Max的时间复杂度为O(1)，Max()将返回栈内最大的元素。

思路：用两个栈，第一个是常规栈，第二个只存储到来的元素中比栈顶大的元素。

复杂度分析：时间复杂度符合题目要求O(1)。空间复杂度最坏情况附加的stack中需要储存每个元素，故额外使用O(n)

空间。

class stackWithMax{private:stack<int>    valueStack;stack<int>    maxStack;public:void push(int);int pop();int max();
};void stackWithMax::push(int value)
{if(maxStack.empty() || maxStack.top() <= value){maxStack.push(value);}valueStack.push(value);
}int stackWithMax::pop()
{int value = valueStack.top();valueStack.pop();if(value == maxStack.top()){maxStack.pop();}return value;
}int stackWithMax::max()
{return maxStack.top();
}