包含min函数的栈

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

template <typename T>
class min_stack
{
    public:
        min_stack(){};
        ~min_stack(){};
        T my_min();
        void my_push(const T& data);
        void my_pop();
        void Show_min_stack(void);
    protected:
    private:
        stack<T> data_stack;
        stack<T> auxi_stack;
};

思路：使用两个栈，一个是普通的数据栈，data_stack,和另外一个auxi_stack辅助栈，首先在空的时候都压入两个栈，然后对于压入的序列，比较这个元素和辅助栈栈顶元素，如果小于这个栈顶那么在压入数据栈的时候也压入辅助站，否则，将辅助栈的顶部元素再次压入一次，这样保证了两个栈的大小相等，这样才能在pop的时候同步。这样需要的空间就是两个相等的栈。

#include<stack>   
#include<iostream>   
using namespace std;  
template <typename T>  
class min_stack  
{  
    public:  
        min_stack(){};  
        ~min_stack(){};  
        T my_min();  
        void my_push(const T& data);  
        void my_pop();  
        void Show_min_stack(void);  
    protected:  
    private:  
        stack<T> data_stack;  
        stack<T> auxi_stack;  
};  
template <typename T>  
void min_stack<T>::Show_min_stack(void)  
{  
    stack<T> temp(data_stack);  
    cout<<"\n从栈顶到栈底显示栈数据：\n";  
    while(!temp.empty())  
    {  
        cout<<temp.top()<<"  ";  
        temp.pop();  
    }  
    cout<<"\n最小的数据为：\n";  
    cout<<auxi_stack.top()<<endl;  
}  
template <typename T>  
void min_stack<T>::my_pop()  
{  
    if (auxi_stack.empty() && data_stack.empty())  
        return;  
    else  
    {  
        auxi_stack.pop();  
        data_stack.pop();  
    }  
}  
template <typename T>  
void min_stack<T>::my_push(const T& data)  
{  
    data_stack.push(data);  
    if(auxi_stack.empty() || data < auxi_stack.top())  
        auxi_stack.push(data);  
    else  
        auxi_stack.push(auxi_stack.top());  
}  
template <typename T>  
T min_stack<T>::my_min()  
{  
    if(!auxi_stack.empty())  
        return auxi_stack.top();  
    else  
        return -1;  
}  
int main()  
{  
    min_stack<int> my_min_stack;  
    for(int i=1991;i<1997;i++)  
        my_min_stack.my_push(i);  
    my_min_stack.Show_min_stack();  
  
  
    my_min_stack.my_push(22);  
    my_min_stack.Show_min_stack();  
  
  
    for(int j=0;j<5;j++)  
        my_min_stack.my_pop();  
    my_min_stack.Show_min_stack();  
  
    my_min_stack.my_push(2);  
    my_min_stack.my_push(1);  
    my_min_stack.Show_min_stack();  
}  
/************************ 
运行结果： 
 
从栈顶到栈底显示栈数据： 
1996  1995  1994  1993  1992  1991 
最小的数据为： 
1991 
 
从栈顶到栈底显示栈数据： 
22  1996  1995  1994  1993  1992  1991 
最小的数据为： 
22 
 
从栈顶到栈底显示栈数据： 
1992  1991 
最小的数据为： 
1991 
 
从栈顶到栈底显示栈数据： 
1  2  1992  1991 
最小的数据为： 
1 
 
 
*************************/  

#include<stack>
#include<iostream>
using namespace std;
template <typename T>
class min_stack
{
    public:
        min_stack(){};
        ~min_stack(){};
        T my_min();
        void my_push(const T& data);
        void my_pop();
        void Show_min_stack(void);
    protected:
    private:
        stack<T> data_stack;
        stack<T> auxi_stack;
};
template <typename T>
void min_stack<T>::Show_min_stack(void)
{
    stack<T> temp(data_stack);
    cout<<"\n从栈顶到栈底显示栈数据：\n";
    while(!temp.empty())
    {
        cout<<temp.top()<<"  ";
        temp.pop();
    }
    cout<<"\n最小的数据为：\n";
    cout<<auxi_stack.top()<<endl;
}
template <typename T>
void min_stack<T>::my_pop()
{
    if (auxi_stack.empty() && data_stack.empty())
        return;
    else
    {
        auxi_stack.pop();
        data_stack.pop();
    }
}
template <typename T>
void min_stack<T>::my_push(const T& data)
{
    data_stack.push(data);
    if(auxi_stack.empty() || data < auxi_stack.top())
        auxi_stack.push(data);
    else
        auxi_stack.push(auxi_stack.top());
}
template <typename T>
T min_stack<T>::my_min()
{
    if(!auxi_stack.empty())
        return auxi_stack.top();
    else
        return -1;
}
int main()
{
    min_stack<int> my_min_stack;
    for(int i=1991;i<1997;i++)
        my_min_stack.my_push(i);
    my_min_stack.Show_min_stack();


    my_min_stack.my_push(22);
    my_min_stack.Show_min_stack();


    for(int j=0;j<5;j++)
        my_min_stack.my_pop();
    my_min_stack.Show_min_stack();

    my_min_stack.my_push(2);
    my_min_stack.my_push(1);
    my_min_stack.Show_min_stack();
}
/************************
运行结果：

从栈顶到栈底显示栈数据：
1996  1995  1994  1993  1992  1991
最小的数据为：
1991

从栈顶到栈底显示栈数据：
22  1996  1995  1994  1993  1992  1991
最小的数据为：
22

从栈顶到栈底显示栈数据：
1992  1991
最小的数据为：
1991

从栈顶到栈底显示栈数据：
1  2  1992  1991
最小的数据为：
1


*************************/

补充：综合编程 , 其他综合 ,