实现一个栈，并且实现一个min函数用来找当前栈中最小的元素-创新互联

题目描述：实现一个栈，并且实现一个min函数用来找当前栈中最小的元素

创新互联主要从事网站制作、成都做网站、网页设计、企业做网站、公司建网站等业务。立足成都服务梁溪,十年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18980820575

分析：要找到栈中最小的元素，需要借助一个辅助栈，来存放当前栈中最小的元素。

入栈的时候，第一个入栈的元素，也给辅助栈入栈，此后每次入栈的元素先与辅助栈的栈顶元素比较，如果小于或等于辅助栈的栈顶元素，则同时将该元素给辅助栈入栈。

如下图所示：

出栈的时候，如果栈顶元素与辅助栈栈顶的元素相等，则同时对辅助栈进行出栈操作

如下图所示：

这样就可以保证，辅助栈中的栈顶元素始终是当前栈中最小的元素了

代码如下：

#include
#include
using namespace std;


template
class Stack
{
public:
	Stack()
	{}

	~Stack()
	{}

	void Push(const T& x)
	{
		_stack.push(x);

		if (_minstack.empty())  //最小栈为空时
		{
			_minstack.push(x);
		}
		else
		{
			if (x <= _minstack.top())
			{
				_minstack.push(x);
			}
		}
	}

	void Pop()
	{
		T cur = _stack.top();
		_stack.pop();
		if (cur == _minstack.top())
		{
			_minstack.pop();
		}
	}

	T GetMin()
	{
		if (!_minstack.empty())
		{
			return _minstack.top();
		}
	}

private:
	stack _stack;
	stack _minstack;
};

void Test1()
{
	Stack s1;
	s1.Push(3);
	s1.Push(2);
	s1.Push(1);
	s1.Push(4);
	s1.Push(1);
	s1.Push(5);
	s1.Pop();
	s1.Pop();
	s1.Pop();
	s1.Pop();
	s1.Pop();
	s1.Pop();
}

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。

本文标题：实现一个栈，并且实现一个min函数用来找当前栈中最小的元素-创新互联
路径分享：http://bzwzjz.com/article/pdodd.html