模拟队列(先进先出)
(1) “push x” – 向队尾插入一个数x;
(2) “pop” – 从队头弹出一个数;
(3) “empty” – 判断队列是否为空;
(4) “query” – 查询队头元素。
输入格式
第一行包含整数M,表示操作次数。
接下来M行,每行包含一个操作命令,操作命令为”push x”,”pop”,”empty”,”query”中的一种。
输出格式
对于每个”empty”和”query”操作都要输出一个查询结果,每个结果占一行。
其中,”empty”操作的查询结果为“YES”或“NO”,”query”操作的查询结果为一个整数,表示队头元素的值。
输入样例
10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6
输出样例
NO
6
YES
4
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int str[N], tt = 1,ww=0;//tt表示队列头 ww表示队列尾
int main()
{
int n;
cin >> n;
while (n--)
{
string c;
cin >> c;
if (c == "push")
{
int x;
cin >> x;
str[++ww] = x;//向队尾插入
}
else if (c == "pop")
tt++;//从队头弹出
else if (c == "empty")
{
if (tt > ww)//判断队列是否为空
cout << "YES" << endl;
else
cout << "NO" << endl;
}
else if (c == "query")
cout << str[tt] << endl;
}
return 0;
}
单调队列(滑动窗口)
输入样例
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<algorithm>
#include<stdio.h>
using namespace std;
typedef long long LL;
const int N = 1e6+10;
int n, k, a[N], q[N];//a是原数组,,q是数组下标
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
int hh = 0, tt = -1; //tt 表示当前队列存储所用到的位置,hh表示队尾
for (int i = 0; i < n; i++)
{
if (hh <= tt && k < i - q[hh] + 1)
hh++; //弹出队头元素维持滑动窗口大小
while (hh <= tt && a[q[tt]] >= a[i]) //队尾元素大于当前元素,删去队尾元素,加入当前元素
tt--;
q[++tt] = i;
if (i + 1 >= k)
printf("%d ", a[q[hh]]); //最值在队头位置
}
printf("\n");
hh = 0, tt = -1;
for (int i = 0; i < n; i++)
{
if (hh <= tt && k < i - q[hh] + 1)
hh++;
while (hh <= tt && a[q[tt]] <= a[i]) //改变此处的符号
tt--;
q[++tt] = i;
if (i + 1 >= k)
printf("%d ", a[q[hh]]);
}
return 0;
}