欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

实现一个出栈,入栈,返回最小值的操作的时间复杂度为O(1)的栈

程序员文章站 2022-06-03 13:33:15
...

栈的特点的是先进后出,这里实现的栈是在这个基础上加以特定的功能。

用一个原生栈实现
这种方法需要_min来记录栈顶元素到栈底元素的最小值,每次入栈之前需要先比较入栈元素和_min的值,接着将它两依次入栈;出栈的时候需要每次Pop两次,并记录第二次的值,即为新栈出栈的元素顺序。

根据上述方法将组数据 “9 2 2 6 3 3 1”入栈可得到下面的栈模型:

实现一个出栈,入栈,返回最小值的操作的时间复杂度为O(1)的栈

从上面模型可以看出如果最小值出现过早的话,在接下来的入栈操作中会一直被入栈,造成数据的冗余。

#include<iostream>
#include<stdlib.h>
#include<stack>
using namespace std;

template<class T>
class Stack
{
public:
    stack<T> Num;
    T _min;
    Stack(const T& x)
        :_min(x)
    {}
    //入栈
    void Push(const T& x)
    {
        Num.push(x);
        //比较小的数值
        if (_min <= x)
        {
            Num.push(_min);
        }
        else if (_min > x)
        {
            _min = x;
            Num.push(_min);
        }
    }
    //出栈
    void Pop()
    {
        Num.pop();
        cout << "Num.Pop:" << Num.top() << endl;//打印栈中num的值
        Num.pop();
    }
    //取最小值
    T& MinNum()
    {
        return Num.top();
    }
};
//测试代码
int main()
{
    Stack<int> S(9);

    S.Push(9);
    S.Push(2);
    S.Push(2);
    S.Push(6);
    S.Push(3);
    S.Push(3);
    S.Push(1);
    cout << "S.MinNum: " << S.MinNum()<<endl;
    S.Pop();
    S.Pop();
    S.Pop();
    S.Pop();
    S.Pop();
    S.Pop();
    S.Pop();    
    system("pause");
}

实现一个出栈,入栈,返回最小值的操作的时间复杂度为O(1)的栈

用两个原有的栈实现一个有特定功能的栈
一个原生栈用来存所有进栈数据,另一个用来存相比较小的数据。比较的方法是:如果Num栈进入的数据小于Min栈的站定数据,就将这时的数据即存进Num栈中又存进Min栈,遇到连续相等的数据,两个栈都要入,最后Min栈的栈顶元素就是最先的数据。

根据上述方法将组数据 “9 2 2 6 3 3 1”入栈可得到下面的栈模型:

实现一个出栈,入栈,返回最小值的操作的时间复杂度为O(1)的栈


template<class T>
class Stack
{
public:
    stack<T> Num;
    stack<T> Min;
    //入栈
    void Push(const T& x)
    {
        if (Min.empty() || x <= Min.top())
        {
            //cout << "Min.push(" << x << ")" << endl;
            Min.push(x);
        }
        //cout << "Num.push(" << x << ")" << endl;
        Num.push(x);
    }
    //出栈
    void Pop()
    {
        if (Min.top() == Num.top())
        {
            //cout << "Min.pop(" << Min.top() << ")" << endl;
            Min.pop();
        }
        //cout << "Num.pop(" << Num.top() << ")" << endl;
        Num.pop();
    }
    //返回最小值
    T& MinNum()
    {
        return Min.top();
    }
    //打印栈
    void Print()
    {
        cout << "Num: ";
        while (!Num.empty())
        {
            cout << Num.top() << " ";
            Num.pop();
        }
        cout << endl;

        cout << "Min: ";
        while (!Min.empty())
        {
            cout << Min.top() << " ";
            Min.pop();
        }
        cout << endl;
    }
    size_t Size()
    {
        return Num.size();
    }
};
//测试代码
int main()
{
    Stack<int> S;
    S.Push(9);
    S.Push(2);
    S.Push(2);
    S.Push(6);
    S.Push(3);
    S.Push(3);
    S.Push(1);
    cout << S.MinNum() << endl;
    S.Print();

    //S.Pop();
    //S.Pop();
    //S.Pop();
    //S.Pop();
    //S.Pop();
    //S.Pop();
    //S.Pop();
    system("pause");
}

实现一个出栈,入栈,返回最小值的操作的时间复杂度为O(1)的栈

相关标签: