一、隊(duì)列是什么

隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。

總結(jié)起來兩點(diǎn)：

1. 一種線性表
2. 添加操作只能在表尾，刪除操作在表頭（先進(jìn)先出）

二、實(shí)現(xiàn)隊(duì)列的思路

1.初始化一個(gè)空隊(duì)列

初始化一個(gè)大小固定的數(shù)組，并將頭指針，尾指針都指向下表為0的位置，但其實(shí)這種初始化頭指針指向的是隊(duì)首，尾指針指向的是隊(duì)尾的后一個(gè)元素。

2.往隊(duì)列里添加元素

往隊(duì)列里添加元素，尾指針后移一位。

一直添加直到隊(duì)列滿

這個(gè)時(shí)候尾指針已經(jīng)出現(xiàn)在數(shù)組下標(biāo)外了

3.消費(fèi)隊(duì)列元素

每消費(fèi)一個(gè)隊(duì)列元素，頭指針指向的元素出隊(duì)，并且后移一位

再消費(fèi)兩個(gè)

這個(gè)時(shí)候我們想往隊(duì)列里繼續(xù)添加元素，尾指針后移，然后發(fā)現(xiàn)出現(xiàn)了假溢出的情況，因?yàn)槲仓羔槦o法再向后移動(dòng)，而隊(duì)列實(shí)際上并沒有滿，我們又無法繼續(xù)往隊(duì)列里添加數(shù)據(jù)。這個(gè)時(shí)候其實(shí)有兩種解決方案。
方案一：我們每消費(fèi)一個(gè)元素，其后面的元素都整體往前移動(dòng)一位，就像我們生活中排隊(duì)打飯一樣，后面的人都往前挪一挪。但這種方案帶來的后果是，帶來的時(shí)間開銷太大，因?yàn)榛旧弦僮魉械脑?#xff0c;所以這種方案不可行。
方案二：尾指針在指向下表為最后一個(gè)元素時(shí)，再添加元素，如果還有空位，就將尾指針重新指向0，頭指針在取到下表數(shù)組末尾時(shí)，如果前面還有元素，頭指針也指向0，這就是我們說的環(huán)形隊(duì)列。

三、實(shí)現(xiàn)環(huán)形隊(duì)列

1.環(huán)形隊(duì)列示例圖

尾指針重新指向零

再添加一個(gè)元素

連續(xù)消費(fèi)三個(gè)元素，如果前面還有元素，頭指針也指向0

這個(gè)時(shí)候我們發(fā)現(xiàn)那個(gè)原來熟悉的隊(duì)列又回來了。

Acwing 829 模擬隊(duì)列

理解和感悟

用數(shù)組模擬隊(duì)列，比用數(shù)組模擬棧要麻煩一點(diǎn)，因?yàn)闂Ｊ峭贿呥M(jìn)同一邊出，而隊(duì)列是尾巴進(jìn)，腦袋出。

舉個(gè)栗子

1、先加入一個(gè)元素a，那么需要++tt, 就是tt==0, 然后要求a出隊(duì)，就是hh++, 這時(shí)，hh=1, 現(xiàn)在隊(duì)列為空，hh>tt。
2、因?yàn)閿?shù)組的特點(diǎn)，在數(shù)組后面增加元素很方便，在頭部增加元素很麻煩，所以設(shè)計(jì)了hh在左，tt在右的策略，出隊(duì)hh++, 入隊(duì)++tt
3、使用數(shù)組模擬隊(duì)列的另一個(gè)好處，就是可以遍歷隊(duì)列中的每一個(gè)數(shù)字，這和用數(shù)組模擬棧是一樣的，這也是STL比不了的。

普通隊(duì)列解法

#include <bits/stdc++.h>using namespace std;
const int N = 1e5 + 10;
int q[N], hh, tt = -1;
int main() {int n;cin >> n;while (n--) {string op;cin >> op;if (op == "push") cin >> q[++tt];else if (op == "empty")hh > tt ? cout << "YES" << endl : cout << "NO" << endl;else if (op == "query")cout << q[hh] << endl;else hh++;}return 0;
}

循環(huán)隊(duì)列解法

#include <bits/stdc++.h>using namespace std;
const int N = 1e5 + 10;
int q[N], hh, tt;
int main() {int n;cin >> n;while (n--) {string op;cin >> op;if (op == "push") {cin >> q[tt++];if (tt == N) tt = 0; // 加冒了，就回到0} else if (op == "empty")hh == tt ? cout << "YES" << endl : cout << "NO" << endl;else if (op == "query")printf("%d\n", q[hh]);else {hh++;if (hh == N) hh = 0; // 加冒了，就回到0}}return 0;
}

單調(diào)隊(duì)列

單調(diào)隊(duì)列：隊(duì)列元素之間的關(guān)系具有單調(diào)性（從隊(duì)首到隊(duì)尾單調(diào)遞增/遞減），隊(duì)首和隊(duì)尾都可以進(jìn)行入隊(duì)出隊(duì)（即插入刪除）操作

通常解決動(dòng)態(tài)小區(qū)間中尋找極值問題。

一、滑動(dòng)窗口

ACW 154 滑動(dòng)窗口

單調(diào)隊(duì)列模板題。
對(duì)于最小值來說，我們維護(hù)一個(gè)單調(diào)遞增隊(duì)列，
這是因?yàn)槲覀円岅?duì)列的頭為該區(qū)間的最小值，那么后一個(gè)數(shù)要比頭大，
因?yàn)槭菃握{(diào)的，所以每一個(gè)進(jìn)來的數(shù)，都應(yīng)該比隊(duì)列中的數(shù)大，所以是單調(diào)遞增隊(duì)列。
題目中還有一個(gè)限制條件, 那便是窗口大小為k, 所以我們要時(shí)刻維護(hù)隊(duì)列中的數(shù)的下標(biāo)大于當(dāng)前下標(biāo)減去k,
如果不滿足該條件，就從隊(duì)列頭刪去該數(shù)，可見單調(diào)隊(duì)列是個(gè)雙端隊(duì)列，這也便是為什么不用棧的原因。

具體實(shí)現(xiàn)時(shí)，我們令head=0表示隊(duì)列頭, tail=-1表示隊(duì)列尾，
那么問題來了，為什么head要為0，tail為-1呢？
試想一下，如果head不為0,那么當(dāng)head=tail時(shí)，隊(duì)列中到底是沒有數(shù)還是有1個(gè)數(shù)呢？顯然無法判斷。
所以我們令head的值+1，當(dāng)head<=tail時(shí)，隊(duì)列中便是有值的,如果head>tail，隊(duì)列便為空。

該數(shù)組為 [1 3 -1 -3 5 3 6 7]，k為3。
我們用樣例來模擬一下單調(diào)隊(duì)列，以求最小值為例：
i=0，隊(duì)列為空，1進(jìn)隊(duì)，[1]
i=1，3比1大，滿足單調(diào)性，3進(jìn)隊(duì)，[1,3]
i=2，-1比3小，破壞單調(diào)性，3出隊(duì)，-1比1小，1出隊(duì)，隊(duì)列為空，-1進(jìn)隊(duì)[-1]，此時(shí)i>=k，輸出隊(duì)頭，即-1
i=3，-3比-1小，-1出隊(duì)，隊(duì)列為空，-3進(jìn)隊(duì)[-3]，輸出-3
i=4，5比-3大，5進(jìn)隊(duì)，[-3,5]，輸出-3
i=5，3比5小，5出隊(duì)，3比-3大，3進(jìn)隊(duì)，[-3,3]，輸出-3
i=6，-3下標(biāo)為4，i-4=3，大于等于k，-3已不在區(qū)間中，-3出隊(duì)，6比3大，6進(jìn)隊(duì)，[3,6]，輸出3
i=7，7比6大，7進(jìn)隊(duì)，[3,6,7]，輸出3
-1 -3 -3 -3 3 3
這樣最小值便求完了，最大值同理，只需在判斷時(shí)改變符號(hào)即可。

#include <iostream>using namespace std;/*
求最大值時(shí)，用單調(diào)隊(duì)列存儲(chǔ)當(dāng)前窗口內(nèi)的單調(diào)遞減的元素，隊(duì)頭是窗口內(nèi)的最大值，隊(duì)尾是窗口內(nèi)的最小值。
求最小值時(shí)，用單調(diào)隊(duì)列存儲(chǔ)當(dāng)前窗口內(nèi)的單調(diào)遞增的元素，隊(duì)頭是窗口內(nèi)的最小值，隊(duì)尾是窗口內(nèi)的最大值。
*/const int N = 1000010;
int a[N], que[N];int main()
{int n, k;scanf("%d%d", &n, &k);for(int i = 0; i < n; i ++) scanf("%d", &a[i]);int head = 0, tail = -1;for(int i = 0; i < n; i ++){// 下標(biāo)為que[head] 的元素是否還在當(dāng)前窗口的最左端，若不在，則單調(diào)隊(duì)中隊(duì)頭為上個(gè)窗口中最小值的下標(biāo)// 進(jìn)行隊(duì)頭出隊(duì)，head自動(dòng)指向第一個(gè)比 a[que[head]] 小的元素下標(biāo)，且在當(dāng)前窗口內(nèi)if(head <= tail && i - k + 1 > que[head]) head ++;// 若當(dāng)前值小于等于隊(duì)尾元素時(shí)，則隊(duì)尾元素不可能稱為窗口最小值// 則將隊(duì)尾元素出隊(duì)while(head <= tail && a[que[tail]] >= a[i]) tail --;// 下標(biāo)入隊(duì)，便于隊(duì)頭出隊(duì)，方便處理下一個(gè)滑動(dòng)窗口que[++ tail] = i;// 使用隊(duì)頭中的最小值if(i >= k - 1) printf("%d ", a[que[head]]);}puts("");// 求窗口最大值情況相似head = 0, tail = -1;for (int i = 0; i < n; i ++){if (head <= tail && i - k + 1 > que[head]) head ++;while (head <= tail && a[que[tail]] <= a[i]) tail --;que[++ tail] = i;if (i >= k - 1) printf("%d ", a[que[head]]);}}