队列

限定在一端进行插入，另一端进行删除特殊线性表。就像排队买东西，排在前面的人买完东西后离开队伍（删除），而后来的人总是排在队伍未尾（插入）。通常把队列的删除和插入分别称为出队和入队。允许出队的一端称为队头，允许入队的一端称为队尾。所有需要进队的数据项，只能从队尾进入，队列中的数据项只能从队头离去。由于总是先入队的元素先出队（先排队的人先买完东西），这种表也称为先进先出（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;
 }