题目描述：实现一个栈，并且实现一个min函数用来找当前栈中最小的元素
分析：要找到栈中最小的元素，需要借助一个辅助栈，来存放当前栈中最小的元素。
入栈的时候，第一个入栈的元素，也给辅助栈入栈，此后每次入栈的元素先与辅助栈的栈顶元素比较，如果小于或等于辅助栈的栈顶元素，则同时将该元素给辅助栈入栈。
如下图所示：
出栈的时候，如果栈顶元素与辅助栈栈顶的元素相等，则同时对辅助栈进行出栈操作
如下图所示：
这样就可以保证，辅助栈中的栈顶元素始终是当前栈中最小的元素了
代码如下：
计算
安全
数据库
网络和加速
企业服务
#include<iostream>
#include<stack>
using namespace std;
template<class T>
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<T> _stack;
stack<T> _minstack;
};
void Test1()
{
Stack<int> 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();
}亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
