实现一个出栈,入栈,返回最小值的操作的时间复杂度为O(1)的栈
程序员文章站
2022-06-03 13:33:15
...
栈的特点的是先进后出,这里实现的栈是在这个基础上加以特定的功能。
用一个原生栈实现
这种方法需要_min来记录栈顶元素到栈底元素的最小值,每次入栈之前需要先比较入栈元素和_min的值,接着将它两依次入栈;出栈的时候需要每次Pop两次,并记录第二次的值,即为新栈出栈的元素顺序。
根据上述方法将组数据 “9 2 2 6 3 3 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");
}
用两个原有的栈实现一个有特定功能的栈
一个原生栈用来存所有进栈数据,另一个用来存相比较小的数据。比较的方法是:如果Num栈进入的数据小于Min栈的站定数据,就将这时的数据即存进Num栈中又存进Min栈,遇到连续相等的数据,两个栈都要入,最后Min栈的栈顶元素就是最先的数据。
根据上述方法将组数据 “9 2 2 6 3 3 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");
}
推荐阅读
-
算法————双栈实现队列、双队列实现栈、实现一个栈Push(出栈)Pop(入栈)Min(返回最小值的操作)的时间复杂度为O(1)
-
算法1---实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作。
-
【每日一题】实现一个栈Stack,要求实现Push(出栈)、Pop(入栈)、Min(返回最小值的操作)的时间复杂度为O(1)
-
实现一个栈,要求实现Push(入栈)、Pop(出栈)、Min(返回最小值)的时间 复杂度为O(1)
-
O1的时间复杂度内实现栈的Push、Pop和min
-
实现一个出栈,入栈,返回最小值的操作的时间复杂度为O(1)的栈
-
实现一个栈,要求实现Push(出栈)、Pop(入栈)、Min(返回最小值)的时间复杂度为O(1)
-
实现一个栈,要求实现出栈,入栈,返回最小值的操作,时间复杂度为O(1)
-
实现一个栈,push、pop、求栈中最小值min的时间复杂度为O(1)
-
实现一个栈:取栈中的最小值的时间复杂度为O(1)