UsualStructure/Structure/自定义单调栈模板.cpp

#include <stack>
#include <vector>class monstk_std {
public:
    //std::stack version
    //compare function : from the bottom to the top
    template<typename _T, typename _U>
    static std::vector<_T> ins(_T x, std::stack<_T>& stk, bool (*comp)(_U, _U)) {
        std::vector<_T> vec;
        while ((!stk.empty()) && (!((*comp)(stk.top(), x))))
            vec.push_back(stk.top()),
            stk.pop();
        stk.push(x);
        return vec;
    }
    //compare function : from the bottom to the top
    template<typename _T, typename _U>
    static void ins(std::vector<_T>& vec, _T x, std::stack<_T>& stk, bool (*comp)(_U, _U)) {
        while ((!stk.empty()) && (!((*comp)(stk.top(), x))))
            vec.push_back(stk.top()),
            stk.pop();
        stk.push(x);
    }
    template<typename _T>
    static void ext(std::vector<_T>& vec, std::stack<_T>& stk) {
        while (!stk.empty()) {
            vec.push_back(stk.top());
            stk.pop();
        }
    }
    template<typename _T>
    static std::vector<_T> ext(std::stack<_T>& stk) {
        std::vector<_T> vec;
        while (!stk.empty())
            vec.push_back(stk.top()),
            stk.pop();
        return vec;
    }
};



//-----------------------------------------------------------------------------//
class monstk_pnt {
    //pointer(list) version



    //compare function : from the bottom to the top
    template<typename _T, typename _U>
    static void ins(std::vector<_T>& vec, _T x, int& siz, _T* stk, bool (*comp)(_U, _U)) {
        while ((siz > 0) && (!((*comp)(stk[siz], x)))) {
            vec.push_back(stk[siz]);
            siz--;
        }
        siz++;
        stk[siz] = x;
    }
    //compare function : from the bottom to the top
    template<typename _T, typename _U>
    staticstd::vector<_T> ins(_T x, int& siz, _T* stk, bool (*comp)(_U, _U)) {
        std::vector<_T> vec;
        while ((siz > 0) && (!((*comp)(stk[siz], x)))) {
            vec.push_back(stk[siz]);
            siz--;
        }
        siz++;
        stk[siz] = x;
        return vec;
    }
    template<typename _T>
    static std::vector<_T> ext(int& siz, _T* stk) {
        std::vector<_T> vec;
        while (siz > 0) {
            vec.push_back(stk[siz]);
            siz--;
        }
        return vec;
    }
    template<typename _T>
    static void ext(std::vector<_T>& vec, int& siz, _T* stk) {
        while (siz > 0) {
            vec.push_back(stk[siz]);
            siz--;
        }
    }
};