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

【每日一题】实现一个栈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的栈顶元素

示意图:

【每日一题】实现一个栈Stack,要求实现Push(出栈)、Pop(入栈)、Min(返回最小值的操作)的时间复杂度为O(1)

最后插入元素后的图片:

【每日一题】实现一个栈Stack,要求实现Push(出栈)、Pop(入栈)、Min(返回最小值的操作)的时间复杂度为O(1)

此时最小值元素直接在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;
}

运行截图:

【每日一题】实现一个栈Stack,要求实现Push(出栈)、Pop(入栈)、Min(返回最小值的操作)的时间复杂度为O(1)

方法二:一个栈实现

使用一个栈。元素data入栈时,压入需要的数据data,在压入一个最小值min,min表示当前栈顶到栈底元素最小值;每一次元素出栈时连续出两次,即可达到题目要求。

但是这个方法有一个很大的麻烦,比如压入1,2,3,4,5,6,7,8,9,10。我们每次都要压入1这个元素。

此处便不再给出方法二的代码。