定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push、及pop的时间复杂度都是O(1)。


首先，栈的特点是“先进后出，后进先出”，因此，对于pop和push两个操作自然都是直接放入栈顶和直接在栈顶删除元素，那么如果要找栈中的最小值min，因为要求时间复杂度为O(1)，因此肯定不能遍历栈找出最小元素，这里可以想到使用在这个栈的数据结构中使用两个栈，一个栈用来正常的存放删除数据，另一个栈就用来存放当前栈中的最小值；

当第一次push进栈的时候，就将数据也push进min栈中，并且min栈中的栈顶元素为当前栈的最小值，当push的数据比min栈中的栈顶元素小的时候，就将push的数据也放进min栈中，当push的数据比min栈中的栈顶元素大的时候，就在再次将min栈中的栈顶元素再压进栈，因此，这样下去，min栈中栈顶元素始终为当前数据栈的最小值；而进行pop数据的时候，在pop数据栈的栈顶元素时也pop出min栈的栈顶元素，这样的话还是保证了min栈中栈顶元素为最小值，且时间复杂度为O(1)；

上述内容可画图如下：

程序设计如下：

#include<iostream>#include<stdlib.h>usingnamespacestd;template<classT>classmy_stack{public:my_stack()//栈的默认构造函数，开始时指针为空且将容量设计为3:_data(NULL),_min(NULL),_size(0),_capacity(3){}voidmy_push(Tdata)//push数据{if(_data==NULL)//当第一次放数据时{_data=newT[_capacity];_min=newT[_capacity];_data[_size]=data;_min[_size++]=data;return;}_CheckCapacity();//检查容量_data[_size]=data;if(data<_min[_size-1])//若果要放入的数据比栈顶元素小，直接放入，否则，再次放入栈顶元素_min[_size]=data;else_min[_size]=_min[_size-1];++_size;}voidmy_pop()//pop数据{if(_data==NULL)return;--_size;}T&min()//取出最小值{if(_data==NULL){cout<<"nodata..."<<endl;exit(0);}return_min[_size-1];}~my_stack()//析构函数{if(_data!=NULL){delete[]_data;delete[]_min;_data=NULL;_min=NULL;_size=0;}}voidprint_stack()//打印栈元素{if(_data!=NULL){for(inti=0;i<_size;++i){cout<<_data[i]<<"";}cout<<endl;}}private:void_CheckCapacity()//容量检查{if((_size+1)<=_capacity){_capacity*=2;T*tmp_data=newT[_capacity];T*tmp_min=newT[_capacity];for(inti=0;i<_size;++i){tmp_data[i]=_data[i];tmp_min[i]=_min[i];}swap(_data,tmp_data);swap(_min,tmp_min);delete[]tmp_data;delete[]tmp_min;}}private:T*_data;T*_min;size_t_size;size_t_capacity;};intmain(){my_stack<int>stack;stack.my_push(3);stack.my_push(5);stack.my_push(1);stack.my_push(2);stack.my_push(0);stack.my_push(6);stack.print_stack();cout<<"mindata:"<<stack.min()<<endl;stack.my_pop();cout<<"mindata:"<<stack.min()<<endl;stack.my_pop();cout<<"mindata:"<<stack.min()<<endl;stack.my_pop();cout<<"mindata:"<<stack.min()<<endl;stack.my_pop();cout<<"mindata:"<<stack.min()<<endl;return0;}


运行程序：


可以看到，每pop一次数据，都能输出当前栈中的最小值，且时间复杂度都为O(1)。



《完》