目录一.前言二.队列1.队列的认识2.对队列的优化2.循环队列代码实现三.单调队列四.相关练习五.感言一.前言队列是与栈一同学习的线性表下的数据结构本文章将介绍队列的基本知识以及相关技巧——单调队列。当然队列的应用远不止于此像是各种搜索算法等等以后我会在相关算法中提到。二.队列1.队列的认识队列是线性表中的一个重要数据结构核心特征是先进先出只允许对头与尾部的元素进行操作实现思路定义一个结构体里面有一个数组和head与tail两个指针数组容量最大设为Maxsize关键是head队头与tail队尾的定义可以将head定义为指向队头元素位置的指针tail定义为执行队尾元素下一个位置的指针也可以将head定义为指向队头元素前一个位置的指针tail定义为执行队尾元素位置的指针出队时head向后移动并返回元素入队时tail向后移动并传入元素q-headq-tail时队列为空当q-tailMaxsize-1物理存储时则满2.对队列的优化循环队列按照上述的队列实现思路我们会发现当队列的headtail指针不断向后移动时两指针可能都到达Maxsize-1,这时会出现假满的情况明明数组前面还有很多空间结果全部被浪费了为了能够利用我们利用取模操作形成逻辑上的圆环当然也可以让head与tail重新指向头部但这样写就麻烦了我们专门留出一个空间来判断满还是空当tail1%Maxsizehead时为满当tailhead时为空双端队列有时队列需要对队首和队尾都进行入队出队操作比如单调队列解决滑动窗口问题)这就是双端队列双端队列可以退化为普通队列与栈双端队列是在普通循环队列上做了head与tail指针可以前后移动的改变注意继续取模运算2.循环队列代码实现#include Queue.h //struct Queue{ //我们建立一个循环队列这里是循环队列 // int data[Maxsize]; // int head,tail; //}; //下面队列是创建销毁判空判满增加删除查询元素个数的相关代码 void ini_queue(Queue * p){//这里我们规定head指向队首的前一个元素,tail指向队尾最后一个元素 //也可以将head定义为指向队首元素tail定义为指向队尾元素的下一个位置 pnew Queue; p-headp-tail0; //这里容易踩坑如果初始化为-1会导致越界 } void del_queue(Queue * p){ delete p; pnullptr; } bool full(Queue * p){ return ((p-tail1)%Maxsizep-head); } bool empty(Queue * p){ return (p-tailp-head); } bool enqueue(Queue * p,int x){ //传入元素并添加 if(full(p)) return false; p-tail(p-tail1)%Maxsize; p-data[p-tail]x; return true; } bool dequeue(Queue *p ,int x){ //同时给出删除元素 if(empty(p)) return false; p-head(p-head1)%Maxsize; xp-data[p-head]; return true; } int ele_num(Queue * p){ return (p-tail-p-headMaxsize)%Maxsize; }三.单调队列单调队列主要解决滑动窗口求解最值问题与用滑动窗口进行DP优化问题借助双端队列来实现单调栈通过在队列中维护一个单调递增或单调递减的序列使得队首元素始终是当前窗口的最值其实就是人为定制了特殊的入队出队与查询最值的操作以下是寻找窗口中的最大元素的模板代码vectorint maxSlidingWindow(vectorint nums, int k) { dequeint dq; // 存下标 vectorint res; for (int i 0; i nums.size(); i) { // 1. 队尾弹出维护单调递减 while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); } // 2. 入队 dq.push_back(i); // 3. 队首弹出超出窗口范围 if (dq.front() i - k) { dq.pop_front(); } // 4. 记录答案窗口形成后 if (i k - 1) { res.push_back(nums[dq.front()]); } } return res; }如果想要求解最小元素只需要将 nums[dq.back()] nums[i]改为 nums[dq.back()] nums[i]即可四.相关练习下面是关于单调队列的习题这道题简单应用模板就好#include iostream #include deque #include vector using namespace std; const int N1e610; long long arr[N]; int main(){ int n,k; dequelong longq; cinnk; for(int i0;in;i ){ cinarr[i]; } for(int i0;in;i){ if(!q.empty()q.front()i-k){ q.pop_front(); } while(!q.empty()arr[q.back()]arr[i]){ q.pop_back(); } q.push_back(i); if(ik-1){ coutarr[q.front()] ; } } coutendl; q.clear(); for(int i0;in;i){ if(!q.empty()q.front()i-k){ q.pop_front(); } while(!q.empty()arr[q.back()]arr[i]){ q.pop_back(); } q.push_back(i); if(ik-1){ coutarr[q.front()] ; } } return 0; }这道题注意前缀和与单调队列结合需要去对前缀和做出转化化为在滑动窗口中寻找最小值下面是代码#include iostream #include algorithm #include deque #include climits using namespace std; const int N 5e5 10; long long s[N]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; for (int i 1; i n; i) { int x; cin x; s[i] s[i - 1] x; } dequeint q; q.push_back(0); long long ans LLONG_MIN; for (int r 1; r n; r) { //去掉过期下标 while (!q.empty() q.front() r - m) q.pop_front(); //此时队列里只有 [r-m, r-1] 的候选 if (!q.empty()) ans max(ans, s[r] - s[q.front()]); //入队 j r供后面的 r 使用 while (!q.empty() s[q.back()] s[r]) q.pop_back(); q.push_back(r); } cout ans \n; return 0; }五.感言虽然算法无穷尽但我们能通过掌握一些技巧与模板来解决大部分问题。每次做算法题时头疼是不可避免时间也会被消耗不少但收获和喜悦是很多的 目录一.前言二.队列1.队列的认识2.对队列的优化2.循环队列代码实现三.单调队列四.相关练习五.感言一.前言队列是与栈一同学习的线性表下的数据结构本文章将介绍队列的基本知识以及相关技巧——单调队列。当然队列的应用远不止于此像是各种搜索算法等等以后我会在相关算法中提到。二.队列1.队列的认识队列是线性表中的一个重要数据结构核心特征是先进先出只允许对头与尾部的元素进行操作实现思路定义一个结构体里面有一个数组和head与tail两个指针数组容量最大设为Maxsize关键是head队头与tail队尾的定义可以将head定义为指向队头元素位置的指针tail定义为执行队尾元素下一个位置的指针也可以将head定义为指向队头元素前一个位置的指针tail定义为执行队尾元素位置的指针出队时head向后移动并返回元素入队时tail向后移动并传入元素q-headq-tail时队列为空当q-tailMaxsize-1物理存储时则满2.对队列的优化循环队列按照上述的队列实现思路我们会发现当队列的headtail指针不断向后移动时两指针可能都到达Maxsize-1,这时会出现假满的情况明明数组前面还有很多空间结果全部被浪费了为了能够利用我们利用取模操作形成逻辑上的圆环当然也可以让head与tail重新指向头部但这样写就麻烦了我们专门留出一个空间来判断满还是空当tail1%Maxsizehead时为满当tailhead时为空双端队列有时队列需要对队首和队尾都进行入队出队操作比如单调队列解决滑动窗口问题)这就是双端队列双端队列可以退化为普通队列与栈双端队列是在普通循环队列上做了head与tail指针可以前后移动的改变注意继续取模运算2.循环队列代码实现#include Queue.h //struct Queue{ //我们建立一个循环队列这里是循环队列 // int data[Maxsize]; // int head,tail; //}; //下面队列是创建销毁判空判满增加删除查询元素个数的相关代码 void ini_queue(Queue * p){//这里我们规定head指向队首的前一个元素,tail指向队尾最后一个元素 //也可以将head定义为指向队首元素tail定义为指向队尾元素的下一个位置 pnew Queue; p-headp-tail0; //这里容易踩坑如果初始化为-1会导致越界 } void del_queue(Queue * p){ delete p; pnullptr; } bool full(Queue * p){ return ((p-tail1)%Maxsizep-head); } bool empty(Queue * p){ return (p-tailp-head); } bool enqueue(Queue * p,int x){ //传入元素并添加 if(full(p)) return false; p-tail(p-tail1)%Maxsize; p-data[p-tail]x; return true; } bool dequeue(Queue *p ,int x){ //同时给出删除元素 if(empty(p)) return false; p-head(p-head1)%Maxsize; xp-data[p-head]; return true; } int ele_num(Queue * p){ return (p-tail-p-headMaxsize)%Maxsize; }三.单调队列单调队列主要解决滑动窗口求解最值问题与用滑动窗口进行DP优化问题借助双端队列来实现单调栈通过在队列中维护一个单调递增或单调递减的序列使得队首元素始终是当前窗口的最值其实就是人为定制了特殊的入队出队与查询最值的操作以下是寻找窗口中的最大元素的模板代码vectorint maxSlidingWindow(vectorint nums, int k) { dequeint dq; // 存下标 vectorint res; for (int i 0; i nums.size(); i) { // 1. 队尾弹出维护单调递减 while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); } // 2. 入队 dq.push_back(i); // 3. 队首弹出超出窗口范围 if (dq.front() i - k) { dq.pop_front(); } // 4. 记录答案窗口形成后 if (i k - 1) { res.push_back(nums[dq.front()]); } } return res; }如果想要求解最小元素只需要将 nums[dq.back()] nums[i]改为 nums[dq.back()] nums[i]即可四.相关练习下面是关于单调队列的习题这道题简单应用模板就好#include iostream #include deque #include vector using namespace std; const int N1e610; long long arr[N]; int main(){ int n,k; dequelong longq; cinnk; for(int i0;in;i ){ cinarr[i]; } for(int i0;in;i){ if(!q.empty()q.front()i-k){ q.pop_front(); } while(!q.empty()arr[q.back()]arr[i]){ q.pop_back(); } q.push_back(i); if(ik-1){ coutarr[q.front()] ; } } coutendl; q.clear(); for(int i0;in;i){ if(!q.empty()q.front()i-k){ q.pop_front(); } while(!q.empty()arr[q.back()]arr[i]){ q.pop_back(); } q.push_back(i); if(ik-1){ coutarr[q.front()] ; } } return 0; }这道题注意前缀和与单调队列结合需要去对前缀和做出转化化为在滑动窗口中寻找最小值下面是代码#include iostream #include algorithm #include deque #include climits using namespace std; const int N 5e5 10; long long s[N]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; for (int i 1; i n; i) { int x; cin x; s[i] s[i - 1] x; } dequeint q; q.push_back(0); long long ans LLONG_MIN; for (int r 1; r n; r) { //去掉过期下标 while (!q.empty() q.front() r - m) q.pop_front(); //此时队列里只有 [r-m, r-1] 的候选 if (!q.empty()) ans max(ans, s[r] - s[q.front()]); //入队 j r供后面的 r 使用 while (!q.empty() s[q.back()] s[r]) q.pop_back(); q.push_back(r); } cout ans \n; return 0; }五.感言虽然算法无穷尽但我们能通过掌握一些技巧与模板来解决大部分问题。每次做算法题时头疼是不可避免时间也会被消耗不少但收获和喜悦是很多的