STL初步——双端队列Deque

『写在前面的一些基础语法』

1.双端队列的特性

• ¨deque 的大小是动态的。支持在头部或尾部快速插入/删除、 快速随机访问、在任意位置的插入/删除等操作。
• 和Vector十分相似,当需要频繁在队头和队尾操作时选用双端队列。
• 有队列的特性，同时也支持迭代器

2.定义 和 赋值

deque<int > a;          deque<int> q=a;  //

deque<int> d(3);//定 义 一 个 类 型 为 int 、 初 始 大 小 为 3 的 deque ， 每 个 元 素 都 是 0

3.一些基础操作

• a.front();//返回队首元素,但不删除该元素
• a.back();//返回队尾元素,但不删除该元素

 

• a.push_back();//向尾部添加一个元素
• a.pop_back();//删除最后一个元素
• a.size();//读取大小
• a.resize();//改变大小
• a.clear();//清空
• a.empty();//检查是否为空
• 迭代器(iterator):    一种检查容器内元素并遍历元素的数据类型

•         a.begin();//返回首个元素的迭代器

          a.end();//返回末尾元素向后一位的迭代器

• a.insert(p,x);//在迭代器p所指向的元素前面插入1个值为x的新元素。返回指向新添加元素的迭代器。
• a.c.erase(p);//删除迭代器p所指的元素

 

• a. push_back (x); // 在队尾插入元素x
• a. push_front(x); // 在队头插入元素x
• a. pop_back(); // 删除队尾的元素
• a. pop_front(); // 删除队首的元素

『上题上题』

【滑动窗口(最大值)】

给出一个长度为n的数组(n<=1000)，有一个可移动的长度为k的窗口，从最左端开始每个时刻向右移动一格，你的任务是输出每个时刻窗口内最大及最小的数字。

  Window position                          Maxvalue

    [1 3 -1] -3 5 3 6 7                             3

    1 [3 -1 -3] 5 3 6 7                             3

    1 3 [-1 -3 5] 3 6 7                             5

    1 3 -1 [-3 5 3] 6 7                             5

    1 3 -1 -3 [5 3 6] 7                             6

    1 3 -1 -3 5 [3 6 7]                             7

【输入要求】

   第一行包含四个整数n,k

   第二行为n个整数

【输出要求】

    一个数值，表示每个时刻窗口内最大值的和。

【输入样例】

 8 3

 1 3 -1 -3 5 3 6 7

【输出样例】

 3 3 5 5 6 7

『代码代码』

#include<iostream>
#include<queue>
#include<set>
using namespace std;
int main(){
	int n,k;
	cin>>n>>k; 
	int a[n+1];
	for(int i=1;i<=n;i++)
		cin>>a[i];
	deque<int> q;
	int ans[n];
	for(int i=1;i<=n;++i){
		while(!q.empty() && a[i] > a[q.back()])//队列存的是元素位置 
			q.pop_back();//删去队尾比起小的数
		q.push_back(i);//把当前位置插入队尾
		while(q.front() <= i-k)
			q.pop_front();//删去窗口外的数 
		ans[i] = a[q.front()];//队首即是最大元素的位置,将最大值存入ans
	}
	for(int i=k;i<=n;i++){
		cout<<ans[i]<<" ";
	}
	return 0; 
} 

『感悟』