队列
队列
限定在一端进行插入，另一端进行删除特殊线性表。就像排队买东西，排在前面的人买完东西后离开队伍（删除），而后来的人总是排在队伍未尾（插入）。通常把队列的删除和插入分别称为出队和入队。允许出队的一端称为队头，允许入队的一端称为队尾。所有需要进队的数据项，只能从队尾进入，队列中的数据项只能从队头离去。由于总是先入队的元素先出队（先排队的人先买完东西），这种表也称为先进先出（FIFO）表。
队列可以用数组Q[m+1]来存储，数组的上界ｍ即是队列所容许的最大容量。在队列的运算中需设两个指针：
head：队头指针，指向实际队头元素的前一个位置
tail：队尾指针，指向实际队尾元素所在的位置
一般情况下，两个指针的初值设为０，这时队列为空，没有元素。图1 (a)画出了一个由６个元素构成的队列，数组定义Q[11]。
Q[i] i=3,4,5,6,7,8 头指针head＝2，尾指针tail＝8。
队列中拥有的元素个数为:L=tail-head现要让排头的元素出队，则需将头指针加１。即head=head+1这时头指针向上移动一个位置，指向Q[3]，表示Q[3]已出队。见图1 (b)。
如果想让一个新元素入队，则需尾指针向上移动一个位置。即tail=tail+1这时Q[9]入队，见图1 (c)。
当队尾已经处理在最上面时，即tail=10，见图1 (d)，如果还要执行入队操作，则要发生“上溢”，但实际上队列中还有三个空位置，所以这种溢出称为“假溢出”。
克服假溢出的方法有两种。一种是将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到n地址后，下一个地址就"翻转"为１。在结构上采用这种技巧来存储的队列称为循环队列
循环队的入队算法如下：
1、若head=（tail+1)%MaxSize，表示元素已装满队列， 则作上溢出错处理； 2、否则，tail=(tail+1) %maxsize;Q[tail]=x，结束（x为新入出元素）。
在循环队列中，当队列为空时，有head=tail，而当所有队列空间全占满时，也有head=tail。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时head=tail，而队列判满的条件时head=（tail+1)%MaxSize。
【例1】周末舞会
http://ybt.ssoier.cn:8088/problem_show.php?pid=1332
假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。
输入： 第一行两队的人数
第二行舞曲的数目
【分析】： 设计两个队列分别存放男士和女士。每对跳舞的人一旦跳完后就回到队尾等待下次被选。如m=4 n=3 k=6
【参考程序】
#include<cstdio>
#include<iostream>
using namespace std;
int a[10001],b[10001],k1=1,k,i,f1=0,r1,f2=0,r2;
main()
{
int m,n;
cin>>m>>n;
for (i=1;i<=m;i++) a[i]=i;
for (i=1;i<=n;i++) b[i]=i;
cin>>k;
r1=m; r2=n;
while (k1<=k)
{
printf("%d %d\n",a[f1+1],b[f2+1]);
r1++; a[r1]=a[++f1]; //第一次a[m+1]=a[1]=1,第二次a[m+2]=a[2]=2,如此循环
r2++; b[r2]=b[++f2]; //第一次b[n+1]=b[1]=1,第二次b[n+2]=b[2]=2,如此循环。
k1++;
}
return 0;
}
【例2】Blah数集【3.4数据结构之队列2729】http://ybt.ssoier.cn:8088/problem_show.php?pid=1333
大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah，对于以a为基的集合Ba定义如下：
(1)a是集合Ba的基，且a是Ba的第一个元素；
(2)如果x在集合Ba中，则2x+1和3x+1也都在集合Ba中；
(3)没有其他元素在集合Ba中了。
现在小高斯想知道如果将集合Ba中元素按照升序排列，第N个元素会是多少？
输入:
输入包括很多行，每行输入包括两个数字，集合的基a(1<=a<=50))以及所求元素序号n(1<=n<=1000000)
输出:
对于每个输入，输出集合Ba的第n个元素值
样例输入:
1 100
28 5437样例输出:
418
900585算法分析：
维护三个数组q1,q2,q3;
取q2、q3队首元素的较小者k，加入q1，相应队列的队首位置后移，
2k+1、3k+1分别加入q2、q3;
直到q1中的元素个数达到n个。
实际上，q2、q3中的元素都来自于q1，只要维护two、three两个位置，表示q2中的下一个数由q1[two]2+1得到，q3中的下一个数由q1[three]3+1得到，这样就不需要q2、q3这两个数组了。
特殊情况的处理：q2、q3的队首元素相同。
【参考程序】
#include<iostream>
#include<cstdio>
using namespace std;
long long q[1000010];
long long a,n,head2,head3,tail;
void work(){
head2=0;//2*x+1;
head3=0;//3*x+1;
tail=1;
q[1]=a;
while(tail<n){
long long t1=2*q[head2+1]+1,
t2=3*q[head3+1]+1;
if(t1<t2){
q[++tail]=t1;
head2++;
}
else{
if(t1>t2){
q[++tail]=t2;
head3++;
}
else{//相等，重复的数，只进一次队
q[++tail]=t1;
head3++;
head2++;
}
}
}
printf("%d\n",q[tail]);
}
int main(){
while(scanf("%d%d",&a,&n)>0)
work();
return 0;
}
例3 P1540 机器翻译
https://www.luogu.com.cn/problem/P1540
题目背景 Background
小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。
这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。
假设内存中有M个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过M-1，软件会将新单词存入一个未使用的内存单元；若内存中已存入M个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。
假设一篇英语文章的长度为N个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。
输入输出格式 Input/output
输入格式：
输入文件共2行。每行中两个数之间用一个空格隔开。 第一行为两个正整数M和N，代表内存容量和文章的长度。
第二行为N个非负整数，按照文章的顺序，每个数（大小不超过1000）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。
输出格式：
包含一个整数，为软件需要查词典的次数。
样例测试点#1
输入样例
3 7
1 2 1 5 4 4 1输出样例：
5说明：每个测试点1s
对于10%的数据有M=1，N≤5。
对于100%的数据有0<=M<=100，0<=N<=1000。
整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况：
空：内存初始状态为空。
1． 1：查找单词1并调入内存。
2． 1 2：查找单词2并调入内存。
3． 1 2：在内存中找到单词1。
4． 1 2 5：查找单词5并调入内存。
5． 2 5 4：查找单词4并调入内存替代单词1。
6． 2 5 4：在内存中找到单词4。
7． 5 4 1：查找单词1并调入内存替代单词2。
共计查了5次词典。
算法分析：
维护内存单元中的单词：状态数组 + 队列。
需要查询一个单词时，如果已在队列中，跳过；
否则，存入新单词(如果队列满，先清空最早进入的单词)。
M <= 100，N <=1000。
队列中最多有M个元素，但大小须定义到N，存在空间的浪费。
改进：使用循环队列
普通队列 循环队列
出队： head++; head = (head + 1) % M
入队： tail++; tail = (tail + 1) % M
#include <cstdio>
const int maxm=110;const int maxn=1010;
int m,n,p[maxn],k,ans;
int q[maxm],head,tail; //循环队列
int main(){
scanf("%d%d",&m,&n);
for(int i=0;i<maxn;i++) p[i]=-1;
scanf("%d",&k);
head=0; tail=1; q[1]=k;
p[k]=0; ans=1;
for(int i=1;i<n;i++){
scanf("%d",&k);
if(p[k]==-1){
ans++;
if(head==tail){ //队列满
head=(head+1)%m;
p[q[head]]=-1; //队首出队
}
tail=(tail+1)%m;
q[tail]=k; p[k]=tail;//k入队
}
}
printf("%d\n",ans); return 0;
}
例4 P1996 约瑟夫问题
https://www.luogu.com.cn/problem/P1996
http://ybt.ssoier.cn:8088/problem_show.php?pid=1334
洛谷https://www.luogu.com.cn/problem/P1996
设有ｎ个人依次围成一圈，从第１个人开始报数，数到第ｍ个人出列，然后从出列的下一个人开始报数，数到第ｍ个人又出列，…，如此反复到所有的人全部出列为止。设ｎ个人的编号分别为1，2，…，n，打印出列的顺序。
【算法分析】
本题我们可以用数组建立标志位等方法求解，但如果用上数据结构中循环链的思想，则更贴切题意，解题效率更高。ｎ人围成一圈，把一人看成一个结点，ｎ人之间的关系采用链接方式，即每一结点有一个前继结点和一个后继结点，每一个结点有一个指针指向下一个结点，最后一个结点指针指向第一个结点。这就是单循环链的数据结构。当ｍ人出列时，将ｍ结点的前继结点指针指向ｍ结点的后继结点指针，即把ｍ结点驱出循环链。
1、建立循环链表。
当用数组实现本题链式结构时，数组a[i]作为"指针"变量来使用，a[i]存放下一个结点的位置。设立指针j指向当前结点，则移动结点过程为j=a[j]，当数到m时，m结点出链，则a[j]=a[a[j]]。 当直接用链来实现时，则比较直观，每个结点有两个域：一个数值域，一个指针域，当数到m时，m出链，将m结点的前继结点指针指向其后继结点；
2、设立指针，指向当前结点，设立计数器，计数数到多少人；
3、沿链移动指针，每移动一个结点，计数器值加１，当计数器值为ｍ时， 则ｍ结点出链，计数器值置为１。
4、重复３，直到n个结点均出链为止。
【参考程序】用数组实现链式结构
#include <bits/stdc++.h>
using namespace std;
int n,m; //设有n人,报到m人出列
int a[110],j,k=1,p=0;
int main()
{ cin>>n>>m; j=n;
for (int i=1;i<n;i++) a[i]=i+1; //建立链表
a[n]=1; //第n人指向第1人，形成一个环
while (p<n) //n个人均出队为止
{
while(k<m) //报数,计数器加1
{ k++; j=a[j]; }
printf("%d ",a[j]); p++; //数到m,此人出队,计数器置1
a[j]=a[a[j]]; k=1;
}
return 0;
}//样例输入4 17输出1 3 4 2
【例5】连通块
http://ybt.ssoier.cn:8088/problem_show.php?pid=1335
描述:
一个n * m的方格图，一些格子被涂成了黑色，在方格图中被标为1，白色格子标为0。问有多少个四连通的黑色格子连通块。四连通的黑色格子连通块指的是一片由黑色格子组成的区域，其中的每个黑色格子能通过四连通的走法（上下左右），只走黑色格子，到达该联通块中的其它黑色格子。
输入:
第一行两个整数n,m(1<=n,m<=100)，表示一个n * m的方格图。
接下来n行，每行m个整数，分别为0或1，表示这个格子是黑色还是白色。
输出:
一行一个整数ans，表示图中有ans个黑色格子连通块。
样例输入
3 3
1 1 1
0 1 0
1 0 1样例输出
3分析：
我们可以枚举每个格子，若它是被涂黑的，且它不属于已经搜索过的联通块，则由它开始，扩展搜索它所在的联通块，并把联通块里的所有黑色格子标记为已搜索过。
如何扩展搜索一个联通块呢？我们用一个搜索队列，存储要搜索的格子。每次取出队首的格子，对其进行四连通扩展，若有黑格子，将其加入队尾,扩展完就把该格子删除。当队列为空时，一个联通块就搜索完了。
【参考程序】
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
const int flag[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int a[N][N],queue1[N * N][2];
int n, m, ans;
void bfs(int x,int y)
{
int front =0, rear =1;
queue1[1][0] = x,queue1[1][1] = y;
while (front < rear)
{
++ front;
x = queue1[front][0];
y = queue1[front][1];
for (int i = 0;i < 4;++ i)
{
int x1 = x + flag[i][0];
int y1 = y + flag[i][1];
if (x1 < 1 || y1 < 1 || x1 > n || y1 > m || !a[x1][y1])
continue;
a[x1][y1] = 0;
queue1[++rear][0] = x1;
queue1[rear][1] = y1;
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= m; ++ j) cin >> a[i][j];
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= m; ++ j)
if (a[i][j])
{
++ ans; bfs(i,j);
}
cout << ans << endl;
return 0;
}
例5：洛谷P1886滑动窗口
【题目描述】
现在有一堆数字共N个数字（N<=10^6），以及一个大小为k的窗口。现在这个窗口从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
【输入格式】
输入文件名为window.in。
输入文件一共有两行，第一行为n,k。
第二行为n个数，在[2^-31，2^31)范围内。
【输出格式】
输出文件名为window.out。
输出文件名共两行，第一行为每次窗口滑动的最小值，
第二行为每次窗口滑动的最大值。
【输入样例】
8 3
1 3 -1 -3 5 3 6 7【输出样例】
-1 -3 -3 -3 3 3
3 3 5 5 6 7【数据约定】
50%的数据，n<=10^5；
100%的数据，n<=10^6。
算法分析（朴素的算法）：
对于每个大小为k的区间，都要计算最大值和最小值
时间复杂度：O(n * k)
观察队列中元素离开队列的情况：
1.元素Vi从队尾离开队列：
i < j 且 Vi >= Vj，Vi没有参与求min的必要
2.元素Vi从队首离开队列：
Vi超出了当前窗口的范围。
单调队列。
#include <bits/stdc++.h>
using namespace std;
const int maxn=5000001;
intn,k,a[maxn],q[maxn],tail=0,head=0;
int main()
{ cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<k;i++)
{
while(a[i]<=a[q[tail]]&&tail>head)
tail--;
q[++tail]=i;
}
for(int i=k;i<=n;i++)
{
while(a[i]<=a[q[tail]]&&tail>head)
tail--;
q[++tail]=i;
if(i-q[head+1]>=k) head++;
cout<<a[q[head+1]]<<" ";
}
cout<<endl;
tail=0,head=0;
for(int i=1;i<k;i++)
{
while(a[i]>=a[q[tail]]&&tail>head)
tail--;
q[++tail]=i;
}
for(int i=k;i<=n;i++)
{
while(a[i]>=a[q[tail]]&&tail>head)
tail--;
q[++tail]=i;
if(i-q[head+1]>=k) head++;
cout<<a[q[head+1]]<<" ";
}
cout<<endl;
return 0;
}