【练习】实现一个栈

实现一个栈，要求实现Push（出栈）、Pop（入栈）、Min（返回最小值的操作）的时间复杂度为O(1)

使用两个栈s1和s2，s2做为辅助栈（每次压入s2的都是s1的最小值）。元素x入栈时，将x和s2栈顶元素做比较，如果x小于等于s2.top（），将x分别push到s1和s2，否则x只push到s1；元素出栈时，将s1栈顶元素和s2栈顶元素做比较，如果s1.top（）等于s2.top（），s1和s2都执行pop操作，否则只执行s1.pop（）

代码实现：

#include <iostream>
#include <stack>
using namespace std;

template <class T>
class Stack
{
private:
    stack<T> _s1, _s2;
    
public:
    void Push(const T& data)
    {
        _s1.push(data);
        if (_s2.empty() || data < _s2.top())
        {
            _s2.push(data);
        }
    }

    void Pop()
    {
        if (!_s1.empty())
        {
            if (_s1.top() == _s2.top())
            {
                _s2.pop();
            }
            T& tmp = _s1.top();
            _s1.pop();
            cout << tmp << " ";
        }
    }

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

    int GetCount()
    {
        return _s1.size();
    }

};

void test_Stack()
{
    Stack<int> s;
    s.Push(1);
    s.Push(3);
    s.Push(7);
    s.Push(5);
    s.Push(9);
    int count = s.GetCount();
    cout << "count: "<< count << endl;

    int min = s.GetMin();
    cout << "min: " << min << endl;

    s.Pop();
    s.Pop();
    s.Pop();
    s.Pop();
    count = s.GetCount();
    cout << "count: " << count << endl;

    s.Pop();
    s.Pop();
    count = s.GetCount();
    cout << "count: " << count << endl;

}