模拟队列 与 单调队列

发表于 更新于 分类于 ，
本文字数： 1.4k

使用数组实现队列与单调队列的功能

qu[N]为队列数组 tt为队尾指针，hh为队头指针 (队头队尾指针初始化为0)

1.模拟队列

向队尾插入一个元素（push）

1
qu[++tt] = x;

返回队头元素（front）

1
cout << qu[hh + 1];

弹出队头元素（pop）

1
hh++;

返回队列大小（size）

1
cout << tt - hh;

检查队列是否为空（empty）

1
2
3
4
if (tt - hh)
    cout << "NO";
else
    cout << "YES";

2.单调队列 （滑动窗口问题）

给定一个数组，有一个大小为k的滑动窗口，它从数组的最左边移动到最右边，您只能在窗口中看到k个数字，每次滑动窗口向右移动一个位置。

输入格式

输入包含两行。 第一行包含两个整数n和k，分别代表数组长度和滑动窗口的长度。 第二行有n个整数，代表数组的具体数值。 同行数据之间用空格隔开。

输出格式

输出包含两个。 第一行输出，从左至右，每个位置滑动窗口中的最小值。 第二行输出，从左至右，每个位置滑动窗口中的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int a[N], q[N], tt = -1, hh = 0;

int n, k;

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (int i = 0; i < n; i++)
    {
        if (hh <= tt && q[hh] < i - k + 1)
            hh++;
        while (hh <= tt && a[q[tt]] >= a[i])
            tt--;
        q[++tt] = i;
        if (i >= k - 1)
            cout << a[q[hh]] << " ";
    }
    puts("");
    tt = -1, hh = 0;
    for (int i = 0; i < n; i++)
    {
        if (hh <= tt && q[hh] < i - k + 1)
            hh++;
        while (hh <= tt && a[q[tt]] <= a[i])
            tt--;
        q[++tt] = i;
        if (i >= k - 1)
            cout << a[q[hh]] << " ";
    }
    puts("");
    return 0;
}

思想：

具体思想类似于单调栈，维护大小为窗口大小的一个队列，以求窗口最小值为例，按序检查每一个数字，如果当前队尾元素大于等于当前元素则弹出队尾元素并且检查新的队尾元素，直到队尾元素小于当前数或者队列无元素，之后把当前数插入队尾，求窗口最大值同理 (队列元素具有严格单调性)

注：

  • q数组储存的是元素地址
  • 循环至第k个元素开始输出
  • 要检查队头元素是否滑出窗口，如果滑出则须hh++;