问题：对stack进行扩展，完成正常的push，pop操作，新增访问最小(大)元素的接口min(max)，使得push，pop，Min的时间复杂度都是O(1)。

难点在于怎么维持stack的最小(大)值，一切排序和查找都不可能实现O(1)的时间复杂度找到最小值。

思路：如下图所示，以空间换取时间。通过增加一个最小值栈来存储上一个最小值，以维持目前的最小值。

1、  入栈的元素比当前的min小：如当min=3时，元素2入栈，则将当前最小值3push进最小值栈，min变为2。

2、  出栈的元素为当前的min：如当min=1时，元素1出栈，则将元素1出栈，最小值栈的元素2出栈，min=2。即回到了上一个状态。

以上是在时间O(1)下求最小值，最大值同样如此，利用额外的栈就可实现。

代码实现：

#include<vector>
#include<iostream>
#include<assert.h>
usingnamespace std;
 
template<typenameT>
classCStack{
public:
         CStack():min_elem(0){}
         ~CStack(){}
        T&pop();
         void push(const T& value);
        Tget_min() const;
private:
         vector<T> _data;
         vector<size_t> _minstore;
         T min_elem;
};
 
template<typenameT>
T&CStack<T>::pop(){
         assert( !_data.empty() );
         T value;
                   value = http://www.mamicode.com/_data.back();>

O(1)时间求栈中最小(大)元素