NO.1 模拟队列
实现一个队列，队列初始为空，支持四种操作：
-
push x– 向队尾插入一个数 x； -
pop– 从队头弹出一个数； -
empty– 判断队列是否为空； -
query– 查询队头元素。
现在要对队列进行 M个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。
输入格式
第一行包含整数 M ，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。
输出格式
对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。
其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示队头元素的值。
数据范围
1≤M≤100000,1≤x≤10^9,
所有操作保证合法。
输入样例：
10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6
输出样例：
NO
6
YES
4
代码：
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e5 + 10;
int t;
int main(){
scanf("%d",&t);
queue<int> a;
while(t --){
string str;
cin >> str;
if(str == "push"){
int x;
cin >> x;
a.push(x);
}else if(str == "pop"){
a.pop();
}else if(str == "empty"){
if(a.empty()) cout << "YES" << endl;
else cout << "NO" << endl;
}else {
cout << a.front() << endl;
}
}
return 0;
}
NO.2 滑动窗口
题目：
给定一个大小为 n≤10^6的数组。
有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到 k 个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。
| 窗口位置 | 最小值 | 最大值 |
|---|---|---|
| [1 3 -1] -3 5 3 6 7 | -1 | 3 |
| 1 [3 -1 -3] 5 3 6 7 | -3 | 3 |
| 1 3 [-1 -3 5] 3 6 7 | -3 | 5 |
| 1 3 -1 [-3 5 3] 6 7 | -3 | 5 |
| 1 3 -1 -3 [5 3 6] 7 | 3 | 6 |
| 1 3 -1 -3 5 [3 6 7] | 3 | 7 |
你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
输入格式
输入包含两行。
第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。
第二行有 n个整数，代表数组的具体数值。
同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。
输入样例：
8 3
1 3 -1 -3 5 3 6 7
输出样例：
-1 -3 -3 -3 3 3
3 3 5 5 6 7
代码：
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e6 + 10;
int n,k;
int a[N];
deque<int> q;
int main(){
cin >> n >> k;
for(int i = 1;i <= n;i ++)
cin >> a[i];
for(int i = 1;i <= n;i ++){
if(i-k >= 1 && q.front() == a[i-k]) q.pop_front(); //是否划出窗口
while(q.size() && q.back() > a[i]) q.pop_back(); //新进来的比队尾小，队尾元素出队
q.push_back(a[i]);
if(i >= k) cout << q.front() << ' ';//窗口形成
}
cout << endl;
q.clear();
for(int i = 1;i <= n;i ++){
if(i - k >= 1 && q.front() == a[i-k]) q.pop_front();
while(q.size() && q.back() < a[i]) q.pop_back();
q.push_back(a[i]);
if(i >= k) cout << q.front() << " ";
}
return 0;
}补充知识：deque(双端队列）
双端队列可以在两端进行扩展或收缩的序列化容器。
d.begin()：指向deque首个元素。
d.end()：指向deque尾元素的下一个位置。
size():元素个数
max_size():最多能容纳元素个数
resize(n):改变deque的size，改成n
empty():判断是否为空，为空->true；
shrink_to_fit():要求deque减小容量已适应元素个数
at(索引):访问deque元素
front():返回第一个元素
back():返回最后一个元素
push_back():添加元素（deque尾部）
push_front():添加元素（deque头部）
pop_back():移除尾部元素
pop_front():删除头部元素
insert( , ):添加元素
erase():删除任意位置元素
clear():清空元素
swap():交换两个deque的元素