队列即是一个特殊的数组，这个数组最前面的元素称为 队头 尾部元素称为 队尾

队列

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
#include <iostream>
using namespace std;
const int N = 100010;
int q[N];

//[hh, tt] 之间为队列（左闭右闭）
int hh = 0;//队头位置
int tt = -1;//队尾位置
//操作次数
int m;
//操作方式
string s;

//入队：队尾先往后移动一格，再放入要插入的数据
void push(int x){
    q[++tt] = x;
}
//出队：队头往后移动一格
void pop(){
    hh++;
}
//[hh, tt]表示队列区间，当tt >= hh时，区间为空
void empty(){
    if(tt >= hh) cout << "NO" << endl;
    else cout << "YES" << endl;
} 
//hh指向队头，q[hh]代表队头元素
void query (){
    cout << q[hh] << endl;
}


以及一道和单调栈类似的模板题
QQ截图20221004211239.png

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;
//q[]作为双端队列(滑动窗口)
int p[N],q[N],n,k,hh,tt=-1;


int main(){
    
    scanf("%d%d",&n,&k);
    
    for(int i=0;i<n;i++) scanf("%d",&p[i]);
    
    for(int i=0;i<n;i++){
	//判断队头是否已滑出窗口 (注意p[]存储的是下标)
        if(hh<=tt&&q[hh]<i-k+1) hh++;
	//判断队尾是否大于当前元素,如果大于,说明p[i]比p[tt]更合适,将队尾弹出
        while(hh<=tt&&p[q[tt]]>=p[i]) tt--;
	//将当前元素加入窗口
        q[++tt] = i;
	//处理完之后队列为单调递增,队头即是当前窗口的最小元素
        if(i>=k-1) cout << p[q[hh]] << " ";
    }
    
    cout << endl;
    
    hh=0,tt=-1;
    
    //窗口内最大元素只需对齐做
    for(int i=0;i<n;i++){
        if(hh<=tt&&q[hh]<i-k+1) hh++;
        while(hh<=tt&&p[q[tt]]<=p[i]) tt--;
        q[++tt] = i;
        if(i>=k-1) cout << p[q[hh]] << " ";
    }
    
    return 0;
}

最近工作有点忙，有时间再来补充详细吧hh