스 택 Stack 을 실현 하고 Push (스 택 에 들 어가 기), Pop (스 택 에서 나 오기), Min (최소 값 으로 돌아 가 는 작업) 을 실현 하 는 시간 복잡 도 는 O (1) 입 니 다.

2375 단어 데이터 구조
#include
#include
using namespace std;
template<typename T>
class Stack
{
public:
    Stack()
    {}
    ~Stack()
    {}
    void Push(const T& val)
    {
        if (s1.empty() && s2.empty())
        {
            s1.push(val);
            s2.push(val);
        }
        else
        {
            if (s2.top() > val)
                s2.push(val);
            s1.push(val);
        }
    }
    void Pop()
    {
        if (s1.top() <= s2.top())
            s2.pop();
        s1.pop();       
    }
    T Min()
    {
        return s2.top();
    }
private:
    stack s1;//s1      
    stack s2;//s2         
};
int main()
{
    Stack<int> s;
    s.Push(4);
    s.Push(7);
    s.Push(3);
    s.Push(5);
    s.Push(2);
    s.Push(8);
    s.Push(9);
    s.Push(1);
    cout << s.Min() << endl;
    s.Pop();
    s.Pop();
    s.Pop();
    cout << s.Min() << endl;
    system("pause");
    return 0;
}

좋은 웹페이지 즐겨찾기