定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push、及pop的时间复杂度都是O(1)。
创新互联建站：从2013年创立为各行业开拓出企业自己的“网站建设”服务，为近千家公司企业提供了专业的网站设计、
成都网站设计、网页设计和网站推广服务，
按需策划由设计师亲自精心设计，设计的效果完全按照客户的要求，并适当的提出合理的建议，拥有的视觉效果，策划师分析客户的同行竞争对手，根据客户的实际情况给出合理的网站构架，制作客户同行业具有领先地位的。
首先，栈的特点是“先进后出，后进先出”，因此，对于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
#include
using namespace std;
template
class my_stack
{
public:
my_stack()//栈的默认构造函数，开始时指针为空且将容量设计为3
:_data(NULL)
,_min(NULL)
,_size(0)
,_capacity(3)
{}
void my_push(T data)//push数据
{
if(_data == NULL)//当第一次放数据时
{
_data = new T[_capacity];
_min = new T[_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;
}
void my_pop()//pop数据
{
if(_data == NULL)
return;
--_size;
}
T& min()//取出最小值
{
if(_data == NULL)
{
cout<<"no data..."< 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<<"min data: "<运行程序：
可以看到，每pop一次数据，都能输出当前栈中的最小值，且时间复杂度都为O(1)。
《完》
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
当前标题：包含min函数的栈——21-创新互联
本文路径：http://jkwzsj.com/article/ijecs.html
