【算法竞赛】队列

队列相关概念

队列中的数据存取方式是“先进先出”,只能向队尾插入数据,从队头移出数据.

队列的原型在生活中很常见,如食堂打饭的队伍,先到先服务.队列有两种实现方式:链队列和循环队列,如图1.2所示.
在这里插入图片描述
链队列可以看作单链表的一种特殊情况,用指针把各个节点连接起来.

循环队列是一种顺序表,使用一组连续的存储单元依次存放队列元素,用两个指针head和tail分别指示队头元素和队尾元素,当head和tail走到底时,下一步回到开始的位置,从而在这组连续空间内循环.

循环队列能解决溢出问题.如果不循环,head和tail都一直往前走,可能会走到存储空间之外,导致溢出.

队列和栈的主要问题是查找较慢，需要从头到尾一个个查找，在某些情况下可以用优先队列,让优先级最高(最大的数或最小的数)先出队列.

竞赛中一般用STLqueue或手写静态数组实现队列.

STL queue

STLqueue的主要操作如下:

(1)queue< Type >q: 定义队列,Type为数据类型,如int、float、char等.
(2)q.push(item): 把item放进队列.
(3)q.front(): 返回队首元素,但不会删除.
(4)q.pop(): 删除队首元素.
(5)q.back(): 返回队尾元素.
(6)q.size(): 返回元素个数.
(7)q.empty():检查队列是否为空.

例1.2 机器翻译
在这里插入图片描述

下面是STLqueue的代码,由于不用自己管理队列,代码很简洁.
注意检查内存中是否有单词的方法.如果一个一个地暴力搜索,太慢;如果用哈希算法,不仅很快,而且代码简单.

#include<bits/stdc++.h>
using namespace std;int main() {int m, n;scanf("%d %d", &m, &n);queue<int> mem;int Hash[1003] = {0};int cnt = 0;while (n--) {int en;scanf("%d", &en);if (!Hash[en]) {++cnt;mem.push(en);Hash[en] = 1;while (mem.size() > m) {Hash[mem.front()] = 0;mem.pop();}}}printf("%d\n", cnt);return 0;
}

手写循环队列

下面是循环队列的手写模板.

代码中给出了静态分配空间和动态分配空间两种方式(动态分配实现放在注释中).

竞赛中一般用静态分配.

#include<bits/stdc++.h>
// 定义队列大小
#define N 1003 
// 用哈希检查内存中有没有单词
int Hash[N]={0}; // 定义循环队列结构体
struct myqueue
{int data[N];// 如果动态分配，可以这样写: int * data;int head;int rear;// 初始化队列bool init(){// 如果动态分配，这样写: Q.data=(int*) malloc(N * sizeof(int));data = new int[N];if (!data) return false;head = rear = 0;return true;}// 返回队列长度int size() {return (rear - head + N) % N;//重点}// 判断队列是否为空bool empty() {return size() == 0;}// 队尾插入新元素bool push(int e) {if ((rear + 1) % N == head) return false;data[rear] = e;rear = (rear + 1) % N;return true;}// 删除队头元素，并返回它bool pop(int &e) {if (head == rear) return false;e = data[head];head = (head + 1) % N;//重点-循环链表的表征return true;}// 返回队首，但不删除int front() {return data[head];}
};int main() {Queue Q;Q.init();int m, n;std::cin >> m >> n;int cnt = 0;while (n--) {int en;std::cin >> en;if (!Hash[en]) {// 如果内存中没有这个单词++cnt;Q.push(en);Hash[en] = 1;while (Q.size() > m) {int tmp;Q.pop(tmp);Hash[tmp] = 0;}}}std::cout << cnt << std::endl;return 0;
}

双端队列和单调队列

概念

前面的队列很“规矩”,队列的元素都是“先进先出”,队头只能弹出,队尾只能进入.

有没有不那么规矩的队列呢?

这就是双端队列:双端队列是一种具有队列和栈性质的数据结构,它能在两端进行插入和删除,而且也只能在两端插入和删除.

更可靠的编码可以用STL的双端队列deque,它的用法如下。

(1)dq[i]:返回队列中下标为i的元素。
(2)dq.front():返回队头。
(3)dq.back():返回队尾。
(4)dq.pop_back():删除队尾,不返回值。
(5)dq.pop_front():删除队头,不返回值。
(6)dq.push_back(e):在队尾添加一个元素e。
(7)dq.push_front(e):在队头添加一个元素e。

双端队列的经典应用是单调队列。
单调队列中的元素是单单调有序的,且元素在队列中的顺序和原来在序列中的顺序一致;单调队列的队头和队尾都能入队和出队。

提示：
灵活运用单调队列能够使很多问题的求解获得优化。

其原理可以简单地概括为:
序列中的几个元素,用单调队列处理时,每个元素只需要进出队列一次,复杂度为O(n)。

单调队列与滑动窗口

下面介绍单调队列的基本应用,了解如何通过单调队列获得优化。
注意队列中"删头、去尾、窗口"的操作。

例1.3 滑动窗口

在这里插入图片描述
本题用暴力法很容易编程:从头到尾扫描,每次检查处个数,一共检查O(nk)次。
暴力法显然会超时。

下面用单调队列求解,它的复杂度为O(n)。

在本题中,单调队列有以下特征：
(1)队头的元素始终是队列中最小的。根据需要输出队头,但是不一定弹出。
(2)元素只能从队尾进入队列,从队头、队尾都可以弹出。
(3)序列中的每个元素都必须进入队列。
例如,x进入队尾时,和原队尾y比较,如果x<=y,就从队尾弹出y;一直到弹出队尾所有比x大的元素,最后x进入队尾。这个入队操作保证了队头元素是队列中最小的。

单调队列的时间复杂度:每个元素最多入队一次、出队一次,且出入队时间都为O(1),
因此总时间为O(n)。
因为题中需要逐一处理所有几个数,所以O(n)已经是能达到的最优复杂度。

从以上过程可以看出,单调队列有两个重要操作:删头、去尾。
(1)删头:如果队头的元素脱离了窗口,这个元素就没用了,弹出它。
(2)去尾:如果新元素进队尾时,原队尾的存在破坏了队列的单调性,就弹出它。
在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;int main() {int n, m;scanf("%d%d", &n, &m);int a[N];deque<int> q;// 读取序列元素for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);}// 输出每个窗口中的最小值for (int i = 1; i <= n; i++){// 去尾操作，保持队列中的元素对应的值单调递减while (!q.empty() && a[q.back()] > a[i]) q.pop_back();q.push_back(i);if (i >= m) {// 输出当前窗口中的最小值while (!q.empty() && q.front() <= i - m) q.pop_front();printf("%d ", a[q.front()]);}}printf("\n");// 清空队列，准备用于求最大值while (!q.empty()) q.pop_front();// 输出每个窗口中的最大值for (int i = 1; i <= n; i++) {// 去尾操作，保持队列中的元素对应的值单调递增while (!q.empty() && a[q.back()] < a[i]) q.pop_back();q.push_back(i);if (i >= m) {// 输出当前窗口中的最大值while (!q.empty() && q.front() <= i - m) q.pop_front();printf("%d ", a[q.front()]);}}printf("\n");return 0;
}

单调队列与最大子序和问题

首先说明什么是子序和：
给定长度为n的整数序列A,它的"子序列"定义为A中非空的一段连续的元素。
例如：
序列(6,-1,5,4,一7),前4个元素的子序和为6+(-1)+5+4=14。

最大子序和问题按子序列有无长度限制分为两种：

问题(1):不限制子序列的长度。
在所有可能的子序列中找到一个子序列,该子序列和最大。

问题(2):限制子序列的长度。
给定一个限制长度m,找出一段长度不超过m的连续子序列,使它的子序和最大。

问题(1)比较简单,用贪心法或动态规划(Dynamie Programming,DP)算法,复杂度都为O(n)。
问题(2)用单调队列,复杂度也为O(n)。通过这个例子,读者可以理解为什么单调队列能用于DP优化。

问题(1)不是本节的内容,不过为了参照,下面也给出是题解：

问题(1)的求解

用贪心法或DP,在O(n)时间内求解。下面是例题。
在这里插入图片描述
题解1: 贪心法
逐个扫描序列中的元素并累加。加一个正数时,子序和会增加;加一个负数时,子序和会减小。
如果当前得到的和变成了负数,这个负数在接下来的累加中会减少后面的求和,所以抛弃它,从下一位置开始重新求和。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x7fffffff;int main() 
{int t;cin >> t;// 处理每个测试用例for (int i = 1; i <= t; i++) {int n;cin >> n;// 最大子序和，初始化为极小负数int maxsum = -INF;// 起点、终点、扫描位置int start = 1, end = 1, p = 1;int sum = 0;// 遍历输入的序列for (int j = 1; j <= n; j++) {int a;cin >> a;sum += a;// 如果当前子序和大于最大子序和，更新最大子序和及起点和终点位置if (sum > maxsum) {maxsum = sum;start = p;end = j;}// 如果当前子序和小于 0，从下一个位置重新开始求和if (sum < 0) {sum = 0;p = j + 1;}}// 输出当前测试用例的结果printf("Case %d:\n", i);printf("%d %d %d\n", maxsum, start, end);// 如果不是最后一个测试用例，输出一个空行if (i!= t) cout << endl;}return 0;
}

题解2:动态规划
定义状态dp[i],表示以a[i]为结尾的最大子序和.

dp[i]的计算有两种情况:
(1)dp[i]只包括一个元素,就是a[i];
(2)dp[i]包括多个元素,从前面某个a[v]开始,v<i,到a[i]结束,即dp[i-1]+a[i]。
取两者的最大值,得到状态转移方程dp[i]=max(dp[i-1]+a[i]，a[i])。
在所有dp[i]中,最大值就是题目的解。

#include <bits/stdc++.h>
using namespace std;int main() 
{int t;cin >> t;for (int k = 1; k <= t; k++) {int n;cin >> n;int dp[100005];for (int i = 1; i <= n; i++) {cin >> dp[i];}//重点--------int start = 1, end = 1, p = 1;int maxsum = dp[1];for (int i = 2; i <= n; i++){// 状态转移方程：dp[i]=max(dp[i-1]+a[i], a[i])if (dp[i - 1] + dp[i] >= dp[i]) {dp[i] = dp[i - 1] + dp[i];} else {p = i;}if (dp[i] > maxsum) {maxsum = dp[i];start = p;end = i;}}//重点--------printf("Case %d:\n", k);printf("%d %d %d\n", maxsum, start, end);if (k!= t) cout << endl;}return 0;
}