栈（stack）和队列（ queue ）

1.栈的定义：栈是限定仅在表头进行插入和删除操作的线性表（先进后出）

2.队列的定义：队列是一种特殊的线性表，特殊之处在于
它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，
和栈一样，队列是一种操作受限制的线性表。

进行插入操作的端称为队尾，进行删除操作的端称为队头。（先进先出）

poj 2823 单调队列

给定一个长度为n的数列，求长度为k的定长连续子区间
｛a1,a2,a3,a4,…,ak-1,ak｝{a2,a3,…,ak,ak+1}……中每个区间的最大值。

基于STL 双端队列deque的单调队列

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
int a[N]; 
//int maxq[N],minq[N];
int n,k;
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	
	//int f=0,r=1;
	deque<int> dq;
	
		dq.clear();
		for(int i=1;i<=n;i++)
		{
			while(!dq.empty()&&(a[dq.back()]>a[i]||i-dq.back()+1>k))
			dq.pop_back();
			
			while(!dq.empty()&&i-dq.front()+1>k)
			dq.pop_front();
			
			dq.push_back(i);
			if(i>=k)	{
			cout<<a[dq.front()];
			if(i!=n)	cout<<" ";
			}
		}
		cout<<endl;
		
		dq.clear();
	for(int i=1;i<=n;i++)
	{
			while(!dq.empty()&&(a[dq.back()]<a[i]||i-dq.back()+1>k))
			dq.pop_back();
		
			while(!dq.empty()&&i-dq.front()+1>k)
			dq.pop_front();
			
			dq.push_back(i);
			if(i>=k)	{
			cout<<a[dq.front()];
			if(i!=n)	cout<<" ";
			}
		}
		cout<<endl;
	return 0;
} 

用数组模拟单调队列

//poj 2823 单调队列
#include<bits/stdc++.h>
using namespace std;
const int N=100005; 
int a[N];
int du[N];//单调队列 
int main()
{
	ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	//求区间最大值，建立从队头到队尾单调递减队列 
	int l=0,r=1;
	fill(du,du+N,0);
	du[0]=1;
	if(m==1)	printf("%d ",a[1]);
	for(int i=2;i<=n;i++)
	{
		while(i-du[l]>=m&&(l<r))
		l++;
		while(r>l&&a[du[r-1]]>=a[i])
		r--;
		du[r++]=i;
		if(i>=m)
		printf("%d ",a[du[l]]);
	}
	return 0;
}  

hdu 5033 单调栈+计算几何

题意：

将城市看做二维平面，建筑看做x轴上某个位置为端点的竖着的线段，

(xi,hi)表示在x轴xi位置有个高为hi的建筑（线段）。

有多次询问，每次问人在某个平地上（x,0)能看到天空的角度

单调栈的性质：

1.若是单调递增栈，则元素从栈顶到栈底是递增的
若是单调递减栈，则元素从栈顶到栈底是递减的

2.越靠近栈顶的元素越后进栈 

#include<bits/stdc++.h>
using namespace std;
#define eps 1e-8
#define LL long long
#define pi acos(-1.0)

const int Max=1e5+20;

struct Node{
    double high;
    double x;
    int id;
    Node(){};
    Node(double high,double x,int id):high(high),x(x),id(id){};
    bool operator <(const Node &b)const{
        return x<b.x;
    }
    Node operator -(const Node &b)const{
        return Node(high-b.high,x-b.x,0);
    }
};
Node tp[2*Max];
Node a[2*Max];

double ans[2*Max];

//判断在c处的视野中，a建筑物是否能够在c处没有被b建筑物挡住
int cross(const struct Node &a,const struct Node &b){
    return a.high*b.x-b.high*a.x>0;
}
int judge(Node &a,Node &b,Node &c){
    return cross(a-c,c-b);
}
//求a建筑物与b处人所成角的大小
double angle(Node a,Node b){
    return atan((b.x-a.x)/(a.high)) ;
}
int n;
int all;//包括询问的点数

void solve(){
    int top=0;
    for(int i=0;i<all;i++){
        if(a[i].high==0){//是人的位置
            while(top>=2&&judge(tp[top-1],tp[top],a[i])) top--;//去掉凹处
            ans[a[i].id]+=angle(tp[top],a[i]);
            //cout<<angle(tp[top-1],a[i])<<endl;
        }
        else{
            while(top&&tp[top].high<=a[i].high) top--;//比当前还要矮的不要
            while(top>=2&&judge(tp[top-1],tp[top],a[i])) top--;//去掉凹处
            tp[++top]=a[i];
        }
    }
}
int main(){
    int t;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%lf %lf",&a[i].x,&a[i].high);
        }
        all=n;
        int q;
        scanf("%d",&q);
        for(int i=0;i<q;i++){
            scanf("%lf",&a[all].x);
            a[all].high=0;
            a[all].id=i;
            all++;
        }

        sort(a,a+all);
        memset(ans,0,sizeof(ans));
        solve();
        reverse(a,a+all); //翻转，倒回来计算右边的角度
        for(int i=0;i<all;i++) a[i].x=10000000-a[i].x ; //最大的x，变最小
        solve();

        printf("Case #%d:\n",cas);
        for(int i=0;i<q;i++){
            printf("%.10f\n",ans[i]*180/pi);//角度与弧度的转化
        }
    }
    return 0;
}

以下是大神的代码片段：