1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

template<typename T,int maxnode,bool comp(const T&,const T&) >
struct upQUE
{
	T ary[maxnode+1];
	int f,t;
	int cnt=0;
	upQUE(){f=t=cnt=0;}
	void clear(){f=t=cnt=0;}
	bool empty(){return cnt==0;}
	T front(){return ary[f];}
	T tail(){return t==0?ary[maxnode]:ary[t-1];}
	void push(const T& w)
	{
		while(t!=f&&comp(w,tail()))
		{
			--t;
			if(t==-1)t=maxnode;
		}
		ary[t++]=w;
		if(t==maxnode+1)t=0;
		++cnt;
	}

	void pop()
	{
		++f;
		if(f==maxnode+1)f=0;
		--cnt;
	}
};