题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的函数。在该栈中，调用min,push,pop的时间复杂度都为O(1)。
#include<iostream>
#include<vector>
using namespace std;
template <class T>
class Stack
{
public:
void push(T data)
{
if(_array.size()==0)
{
_array.push_back(data);
_array1.push_back(0);
}
else
{
int index=_array1.size()-1;
if(data>=_array[index])
{
_array.push_back(data);
_array1.push_back(_array1[index]);
}
else
{
_array.push_back(data);
_array1.push_back(index+1);
}
}
}
void pop()
{
int index=_array.size()-1;
_array[index]=NULL;
_array1[index]=NULL;
}
T Min()
{
int end=_array1.size()-1;
int index=_array1[end];
return _array[index];
}
private:
vector<T> _array;
vector<int> _array1;
};
void test()
{
Stack<int> s1;
s1.push(3);
s1.push(7);
s1.push(4);
s1.push(1);
s1.push(8);
s1.push(0);
cout<<s1.Min()<<endl;
}
int main()
{
test();
system("pause");
return 0;
}结果：
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
