基本数据结构：队列、单调队列与优先队列_优先队列和单调队列

队列的思想

队列是一种先进先出（FIFO）的线性表，只允许在队头进行删除操作，在队尾进行插入操作。

先进先出的顺序符合我们日程生活中的事件调度过程，例如排队等等。队列就非常适合模拟这些过程，它的结构示意图如下：

                   

值得注意的是，在前面的元素出队以后其占用的空间就不再被利用，造成了浪费，于是我们在队列存储到允许的最大空间时（但其实这时队列并未真正存满），继续添加的元素将会被放入这些已经出队了的元素原来的位置上，让其重复利用，优化了空间效率，这种特殊的队列叫做：循环队列。按理说只要将现在队列的首尾相连，改造成一个环状结构就能实现循环队列，如图：

                            

但在实际实现上我们通常是采取数组下标取模的方法，让下标循环移动，例如：我允许的队列容量最大为5，而我存放满后又出队了2个元素，这时我们想要再添加元素就必须放在队列第一个位置(即队首)上，这时按下标来说我们存放的是第六个元素，将其与5(容量)取模即可得到它的正确存放位置：1。

队列与栈相同，在STL中有着它的模板：queue

#include<cstdio>
//使用stl的队列必须包含头文件“queue”
#include<queue>
using namespace std;
queue<int> q; //定义格式queue<数据类型> 变量名
int main(){
	for(int i=1;i<=5;++i) 
		q.push(i);//入队 
	printf("%d\n", q.front() );//返回队首元素
	printf("%d\n", q.back() ); //返回队尾元素 
	q.pop();      //出队
	printf("%d\n", q.size() ); //返回元素个数 
	printf("%d\n", q.empty() );//判断是否非空 
	return 0;
} 

但有时只在一端插入一段删除无法满足题目的要求，这个时候我们需要用到队列的一个改进版本：双端队列，即在两头都允许插入删除操作。

                     

这部分STL也提供了相应模板：deque

#include<cstdio>
#include<deque>
using namespace std;
deque<int> q;
int main(){
	for(int i=4;i<=5;++i) 
		q.push_back(i); //入队尾
	for(int i=3;i>=1;--i)
		q.push_front(i);//入队首 
	printf("%d", q.front() );//返回队首元素
	printf("%d", q.back() ); //返回队尾元素  
	q.pop_back();     //出队尾
	q.pop_front();    //出队首 
	printf("%d", q.size() ); //返回元素个数 
	printf("%d", q.empty() );//判断是否非空 
	return 0;
} 

尽管没有专门用队列来解决的题型，但是它经常作为一种辅助数据结构去实现或者优化其它的算法，典型如广度优先搜索算法、队列优化的bellman-ford算法等。

单调队列

和单调栈类似，单调队列也必须维护其内元素的有序性。如：

                              

若要入队一个元素11，就会打破现在的单调性，此时只能将大于11的元素全部出队。但仔细观察就会发现，如果这是一个普通队列，无论怎样出队入队，都不可能实现在保留比11小的元素基础上去除比11大的元素，因为普通队列只能在队首出队、队尾入队，而现在很明显我们需要在队尾出队。所以这里告诉我们，单调队列是使用双端队列实现的。

在单调队列的应用上，它经常用来解决定长连续子区间的最值问题：

滑动窗口，大意：给定长为N的序列以及一个长为k的窗口，窗口从序列最左端向最右端依次移动，每次移动一格，询问每次窗口内的最大最小值。

依照惯例，先来看最简单但是几乎不能过题的解法——暴力：每次移动都扫描一遍窗口内的全部数，这样肯定能找到最大最小值，遍历窗口的开销为k，共移动n次，所以总时间复杂度为O(nk)，timelimit。不过熟悉RMQ问题的同学可能立刻能看出此题能用st算法来解，时间复杂度为O(nlogn)，足够过掉此题。但此处我们用单调队列来解，并且能取得更快的时间复杂度：      

由于要同时求最大最小值，我们需要两个单调性的单调队列，求最大值使用单调递减队列，求最小值使用单调递增队列。根据性质，将k个数据存入后，在队首将取得最值。在窗口移动时，会出现两种情形：

1.最值在窗口首位，移动后不继续存在于当前窗口中；

2.最值不在窗口首位，移动后继续存在于当前窗口中。

根据单调队列的性质，不满足单调性的元素将会出队，而如果新入队的元素小于上一轮的最大值（或大于上一轮的最小值)，该最值将不会被出队，但窗口的移动会导致它不在队列中，于是这里需要我们判断后手动出队。也就是当队首元素不在当前窗口时，将其出队后再将新元素入队，以此保证算法的正确性。每个元素最多出队入队一次，时间复杂度为O(n)。

#include<cstdio>
#include<deque>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1000005;
deque<int> q;
int num[N], Max[N], Min[N];
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)
		scanf("%d",&num[i]);
	for(int i=1;i<=n;++i){ //求解最大值
		if(q.empty() || num[q.back()]>num[i]) //维护单调递减队列
			q.push_back(i);
		else{
			while(!q.empty() && num[q.back()]<=num[i])
				q.pop_back(); 
			q.push_back(i);			
		}
		Max[i]=num[q.front()];
		if(q.front() == i-k+1) q.pop_front(); //处理最值在窗口首位的情况
	}
	q.clear();
	for(int i=1;i<=n;++i){ //求解最小值
		if(q.empty() || num[q.back()]<num[i])
			q.push_back(i);
		else{
			while(!q.empty() && num[q.back()]>=num[i])
				q.pop_back();
			q.push_back(i);
		}
		Min[i]=num[q.front()];
		if(q.front() == i-k+1) q.pop_front();
	}
	for(int i=k;i<=n;++i)
		printf("%d ",Min[i]);
	putchar('\n');
	for(int i=k;i<=n;++i)
		printf("%d ",Max[i]);	
	return 0;
}

最后提一下，这同时也是一种用来优化动态规划的算法，称作单调队列优化的DP，这部分将在后续博客中介绍。

优先队列

优先队列在普通队列的基础上给每个元素增加了优先级，这样每次出队的元素不再是队首的元素，而是队列中优先级最高的元素，而具体的优先级可以自行定义，典型的就是按元素从大到小或从小到大的顺序定义优先级。

在STL中也提供了优先队列模板：priority_queue

#include<cstdio>
//优先队列包含在“queue”头文件中
#include<queue>
using namespace std; //定义格式与普通队列相同
priority_queue<int> q;
int main(){
	for(int i=1;i<=5;++i) 
		q.push(i);//入队 
	printf("%d\n", q.top() );  //优先队列不再返回队列队尾，而是返回优先级最高的元素   
	q.pop();      //出队
	printf("%d\n", q.size() ); //返回元素个数 
	printf("%d\n", q.empty() );//判断是否非空 
	return 0;
} 

优先队列一般采用二叉堆来实现，二叉堆的实现可以参考博主的另一篇文章： 二叉堆的实现，这里直接来看优先队列的实际应用，由于优先队列的性质，它常常被用来解决多次维护最大最小值的问题，下面是一道典型例题：

合并果子

大意：将n个数合并成一个数，合并花费的代价为两个数字之和，问合并所需的最小代价是多少？

题解：一道很经典的贪心题，贪心策略也很简单，即每次合并最小的两个数。但是该题的重点并不在策略，而是在实现上。我们每次要找到序列中最小的两个数，而它们合并后序列的最小值同时会发生变化，需要我们重新维护，常见的想法就是每次合并后都重新排序，可想而知时间复杂度我们无法承受（然而事实是加上快读我们能非常极限的在时限内跑完程序），此时我们可以考虑优先队列优化。将所有数据放入优先队列中，提取两次优先队列中优先级最高的元素，将其合并，并把合并后的数据重新放回优先队列中，根据优先队列的性质，它会自动维护序列的优先级，因此无需我们做任何处理，只要不断重复此过程直到队列中只剩下一个数据为止即可，优先队列的原理为二叉堆，所以最终的时间复杂度为对数级。

#include<bits/stdc++.h>
using namespace std;
priority_queue< int, vector<int>, greater<int> > q;
int num[10010];
int main(){
    int n,ans=0;
    cin>>n;
    for(int i = 0; i < n; ++i){
        cin >> num[i];
        q.push(num[i]);
    }
    while( q.size() > 1 ){
        int a = q.top();
        q.pop();
        int b = q.top();
        q.pop();
        int c = a + b;
        q.push(c);
        ans += c;
    }   
    cout<< ans << endl;
    return 0;
}