包含min函数的栈——21

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

创新互联成立于2013年，是专业互联网技术服务公司，拥有项目成都网站制作、成都做网站、外贸营销网站建设网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元滁州做网站,已为上家服务,为滁州各地企业和个人服务,联系电话:18982081108

    首先，栈的特点是“先进后出，后进先出”，因此，对于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)。
《完》
            
            
                        

            网页题目：包含min函数的栈——21            

            网站地址：http://cqcxhl.cn/article/jgosgg.html