【每日一题】实现一个栈Stack,要求实现Push(出栈)、Pop(入栈)、Min(返回最小值的操作)的时间复杂度为O(1)
程序员文章站
2022-06-08 17:58:03
...
这道题有两种实现方式
方法一:用两个栈来实现
两个栈实现的主要思路是,一个栈存放数据,一个栈存放最小值。
压栈操作:
(1)我们先向S1压栈一个数据
(2)再向S1压入第二个数据,如果此时栈S2为空,并且把需要压栈的元素data和S2的栈顶元素进行比较,如果此时需要压栈的元素小于等于S2栈顶元素,把元素也压入栈2,否则不用管
出栈操作:
判断S1栈顶元素与S2栈顶元素是否相等,相等都出栈,否则出S1
选取最小值:
S2不为空,则直接选取S2的栈顶元素
示意图:
最后插入元素后的图片:
此时最小值元素直接在S2栈顶。
代码实现如下:
#include <iostream>
#include <stack>
using namespace std;
typedef int T;
class stackMin
{
public:
stackMin()
{}
~stackMin()
{}
void Push(T data)
{
cout << "s1.push(" << data << ")" << endl;
s1.push(data);
if (s2.empty() || data < s2.top())
{
cout << "s2.push(" << data << ")" << endl;
s2.push(data);
}
}
void Pop()
{
if (s1.top() == s2.top())
{
cout << "s2.pop(" << s2.top() << ")" << endl;
s2.pop();
}
cout << "s1.pop(" << s1.top() << ")" << endl;
s1.pop();
}
T Min()
{
if (!s2.empty())
{
return s2.top();
}
}
private:
stack<T> s1;
stack<T> s2;
};
int main()
{
stackMin s1;
s1.Push(3);
s1.Push(3);
s1.Push(8);
s1.Push(2);
s1.Push(1);
int x = s1.Min();
cout << "最小值为:" << x << endl;
s1.Pop();
s1.Pop();
s1.Pop();
s1.Pop();
s1.Pop();
return 0;
}
运行截图:
方法二:一个栈实现
使用一个栈。元素data入栈时,压入需要的数据data,在压入一个最小值min,min表示当前栈顶到栈底元素最小值;每一次元素出栈时连续出两次,即可达到题目要求。
但是这个方法有一个很大的麻烦,比如压入1,2,3,4,5,6,7,8,9,10。我们每次都要压入1这个元素。
此处便不再给出方法二的代码。
上一篇: C语言 实验5-9 使用函数输出水仙花数 (20分)
下一篇: Torn To Pieces-------------------------------思维(dfs+stringstream流)
推荐阅读
-
算法————双栈实现队列、双队列实现栈、实现一个栈Push(出栈)Pop(入栈)Min(返回最小值的操作)的时间复杂度为O(1)
-
【每日一题】实现一个栈Stack,要求实现Push(出栈)、Pop(入栈)、Min(返回最小值的操作)的时间复杂度为O(1)
-
实现一个栈,要求实现Push(入栈)、Pop(出栈)、Min(返回最小值)的时间 复杂度为O(1)
-
实现一个出栈,入栈,返回最小值的操作的时间复杂度为O(1)的栈
-
实现一个栈,要求实现Push(出栈)、Pop(入栈)、Min(返回最小值)的时间复杂度为O(1)
-
实现一个栈,要求实现出栈,入栈,返回最小值的操作,时间复杂度为O(1)
-
实现一个栈,push、pop、求栈中最小值min的时间复杂度为O(1)
-
实现一个栈,要求实现Push(入栈)、Pop(出栈)、Min(返回最小值)的时间复杂度为O(1)