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

#include <deque>
#include <vector>
class monque_inc{
	//compare function:from head to rear
	template<typename _T, typename _U>
	static std::vector<_T> ins(_T x, std::deque<_T>&que, bool (*comp)(_U, _U)) {
		std::vector<_T> vec;
		while (!((*comp)(que.back(), x)))
			vec.push_back(que.back()),
			que.pop_back();
		que.push_back(x);
		return vec;
	}
	//compare function:from head to rear
	template<typename _T, typename _U>
	static void ins(_T x, std::deque<_T>& que, bool (*comp)(_U, _U), std::vector<_T>& vec){
		while (!((*comp)(que.back(), x)))
			vec.push_back(que.back()),
			que.pop_back();
		que.push_back(x);
	}
	template<typename _T>
	static std::vector<_T> fiton(int siz, std::deque<_T>& que) {
		std::vector<_T> vec;
		while (siz > que.size())
			vec.push_back(que.front()),
			que.pop_front();
		return vec;
	}
	template<typename _T>
	static void fiton(int siz, std::deque<_T>& que, std::vector<_T>& vec) {
		while (siz > que.size())
			vec.push_back(que.front()),
			que.pop_front();
	}
};