c++:入スタック、出スタック関数、および戻り最小値を含むスタックを実現し、要求時間の複雑さはO(1)である.
MinStakc.cpp
#include<iostream>
using namespace std;
#include<stack>
template<class T>
class Stack{
public:
void Push(const T& x){ //
_stack.push(x);
if (_minstack.empty())
_minstack.push(x);
else{
_minstack.push((_minstack.top() > x )? x : _minstack.top());
}
}
void Pop(){ //
_stack.pop();
_minstack.pop();
}
T GetMin(){ //
cout << _minstack.top() << endl;
return _minstack.top();
}
private:
stack<T> _stack;
stack<T> _minstack;
};
void test(){
Stack<int> s;
s.Push(1);
s.Push(2);
s.Push(5);
s.Push(7);
s.Push(8);
s.GetMin();
s.Pop();
s.GetMin();
s.Pop();
s.GetMin();
s.Pop();
}
int main(){
test();
return 0;
}