deque容器:
为一个给定类型的元素进行线性处理,像向量一样,它能够快速地随机访问任一个元素,并且能够高效地插入和删除容器的尾部元素。但它又与vector不同,deque支持高效插入和删除容器的头部元素,因此也叫做双端队列

  1. 构造函数

deque():创建一个空deque

deque(int nSize):创建一个deque,元素个数为nSize

deque(int nSize,const T& t):创建一个deque,元素个数为nSize,且值均为t

deque(const deque &):复制构造函数

(2) 增加函数

void push_front(const T& x):双端队列头部增加一个元素X

void push_back(const T& x):双端队列尾部增加一个元素x

iterator insert(iterator it,const T& x):双端队列中某一元素前增加一个元素x

void insert(iterator it,int n,const T& x):双端队列中某一元素前增加n个相同的元素x

void insert(iterator it,const_iterator first,const_iteratorlast):双端队列中某一元素前插入另一个相同类型向量的[forst,last)间的数据

(3) 删除函数

Iterator erase(iterator it):删除双端队列中的某一个元素

Iterator erase(iterator first,iterator last):删除双端队列中[first,last)中的元素

void pop_front():删除双端队列中最前一个元素

void pop_back():删除双端队列中最后一个元素

void clear():清空双端队列

reference at(int pos):返回pos位置元素的引用

reference front():返回首元素的引用

reference back():返回尾元素的引用

iterator begin():返回向量头指针,指向第一个元素

iterator end():返回指向向量中最后一个元素下一个元素的指针(不包含在向量中)

reverse_iterator rbegin():反向迭代器,指向最后一个元素

reverse_iterator rend():反向迭代器,指向第一个元素的前一个元素

(5) 判断函数

bool empty() const:向量是否为空,若true,则向量中无元素

(6) 大小函数

Int size() const:返回向量中元素的个数

int max_size() const:返回最大可允许的双端对了元素数量值

(7) 其他函数

void swap(deque&):交换两个同类型向量的数据

void assign(int n,const T& x):向量中第n个元素的值设置为x

那么接下来我们来看一个题

题目描述
一个含有n项的数列(n<=2000000),求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始,若前面没有数则输出0。

输入格式
第一行两个数n,m。

第二行,n个正整数,为所给定的数列。

输出格式
n行,第i行的一个数ai,为所求序列中第i个数前m个数的最小值。

输入输出样例
输入 #1
6 2
7 8 1 4 3 2
输出 #1
0
7
7
1
1
3

数据规模
m≤n≤2000000

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
	int num,id;
}e;
deque <node> q;
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
		int a;
		scanf("%d",&a);
		e.num=a; e.id=i;
		if (i==1) //第一个特判 表示前面没有数 
        {
			q.push_back(e);
			printf("0\n");
			continue;
		}
		while (!q.empty()&&q.front().id<=i-m-1) q.pop_front(); //先把不符合条件的弹出去 
		printf("%d\n",q.front().num); //再输出队头 
		while (!q.empty()&&q.back().num>=a) q.pop_back(); //再入队 
		q.push_back(e);
	}
	return 0;
}