数据结构——队列

队列概念：

　　队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

　　队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

使用技巧：

　　普通的队列可以使用手写，也可以使用STL

　　我还是比较倾向于STL的

　　手写的使用不太方便。

　　在一些情况下，我们还可能用到特殊的队列

　　比如循环队列

　　队列结构的使用，很大一部分体现在广搜上。

　在使用广搜解决问题时

　　要注意空间大小，

　　可能需要一种比较好的优化

　　比如：双向广搜

　　当然这个对在下来说有点太难了

一本通例题：

周末舞会：

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int a[10001],b[10001],k1=1,k,i,f1=1,r1,f2=1,r2;
 5 int main()
 6 {
 7     int m,n;
 8     cin>>m>>n; 
 9     for(int i=1;i<=m;i++) a[i]=i;
10     for(int i=1;i<=n;i++) b[i]=i;
11     cin>>k;
12     r1=m;
13     r2=n;
14     while(k1<=k)
15     {
16         printf("%d %d
",a[f1],b[f2]);
17         r1++;a[r1]=a[f1];f1++;
18         r2++;b[r2]=b[f2];f2++;
19         k1++;
20     }
21     return 0;
22 }

这就是一个比较简单的队列使用

围圈报数：

额

又名：约瑟夫问题

循环队列解决：

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int n,m;
 5 int main()
 6 {
 7     cin>>n>>m;
 8     int a[n+1],j=n,k=1,p=0;
 9     for(int i=1;i<n;i++) a[i]=i+1;
10     a[n]=1;
11     while(p<n)
12     {
13         while(k<m)
14         {
15             j=a[j];
16             k++;
17         }
18         printf("%d ",a[j]);p++;
19         a[j]=a[a[j]];k=1;
20     }
21     return 0;
22 }

链表：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 using namespace std;
 5 struct node{
 6     int id;
 7     node *py;
 8 };
 9 node *head,*toil,*poi,*temp;
10 int main()
11 {
12     int n,m;
13     ios_base::sync_with_stdio(false);
14     cout.tie(NULL);
15     cin>>n>>m;
16     head=new node;
17     toil = head;
18     for(int i=1;i<=n;i++)
19     {
20         poi=new node;
21         poi->id = i;
22         poi->py = NULL;
23         toil->py = poi;
24         toil = poi;
25     }
26     poi=head->py ;
27     toil->py =head->py ;
28     for(int i=1;i<=n;i++)
29     {
30         for(int j=1;j<=m-2;j++)
31         poi=poi->py ;
32         
33         printf("%d ",poi->py->id );
34         temp=poi->py ;
35         poi->py =temp->py ;
36         poi=poi->py ;
37         free(temp);
38     }
39     return 0;
40 }

这个链表才90，应该是出特殊数据卡掉了一个

嗯……

后来我就屈服了

改用了循环队列

家庭问题：

欸

我就奇了怪了

这明明是一个并查集

怎么就混进了队列里面

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int py[103];
 5 int rep[103];
 6 int x,y;
 7 inline int spite(int enterprise)
 8 {
 9     if(py[enterprise]==enterprise) return enterprise;
10     return py[enterprise]=spite(py[enterprise]);
11 }
12 void join(int c1,int c2)
13 {
14     int f1=spite(c1),f2=spite(c2);
15     if(f1!=f2) py[f1]=f2;
16 }
17 int main()
18 {
19     int n,m;
20     ios_base::sync_with_stdio(false);
21     cout.tie(NULL);
22     cin>>n>>m;
23     for(int i=1;i<=n;i++) py[i]=i;
24     while(m--)
25     {
26         cin>>x>>y;
27         join(x,y);
28     }
29     int ans=0;
30     for(int i=1;i<=n;i++)
31     {
32         rep[spite(i)]++;
33     }
34     int maxn=0;
35     for(int i=1;i<=n;i++)
36     {
37         if(rep[i]!=0) ans++;
38         if(rep[i]>maxn) maxn=rep[i];
39     }
40     cout<<ans<<" "<<maxn;
41 }

这个题其实是

并查集模板题——亲戚

的魔改版

但我还是没看出来怎么用队列

接下来是全是BFS了

BFS的迷宫问题

太多了

就不多说了

奇怪的电梯：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cstring> 
 5 using namespace std;
 6 struct node{
 7     int floor;
 8     int step;
 9 }py;
10 int k[500];
11 bool f[500];
12 int n;
13 int s,e;
14 int bfs(int l)
15 {
16     if(l==e) return 0;
17     queue<node> Q;
18     py.floor=l;
19     py.step=0;
20     Q.push(py);
21     while(!Q.empty())
22     {
23         node spite;
24         spite=Q.front();
25         Q.pop();
26         for(int i=1;i<=2;i++)
27         {
28             node aux;
29             if(i==1)
30             {
31                 if(spite.floor+k[spite.floor]>n) continue;
32                 if(f[spite.floor+k[spite.floor]]==0) continue;
33                 f[spite.floor]=0;
34                 aux.floor=spite.floor+k[spite.floor];
35                 aux.step=spite.step+1;
36                 if(aux.floor == e) return aux.step;
37                 Q.push(aux);
38             }
39             if(i==2)
40             {
41                 if(spite.floor-k[spite.floor]<1) continue;
42                 if(f[spite.floor-k[spite.floor]]==0) continue;
43                 f[spite.floor]=0;
44                 aux.floor=spite.floor-k[spite.floor];
45                 aux.step=spite.step+1;
46                 if(aux.floor == e) return aux.step;
47                 Q.push(aux);
48             }
49             
50         }
51     }
52     return -1;
53 } 
54 int main()
55 {
56     ios_base::sync_with_stdio(false);
57     cout.tie(NULL);
58     cin>>n;
59     cin>>s>>e；
60     for(int i=1;i<=n;i++)
61     cin>>k[i];
62     memset(f,1,sizeof(f));
63     cout<<bfs(s);
64 }

连通块：

 1 #include<iostream>
 2 using namespace std;
 3 const int N = 110;
 4 const int flag[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
 5 int a[N][N],queue[N * N][2];
 6 int n, m, ans;
 7 bool p[N][N];
 8 void bfs(int x,int y)
 9 {
10     int front = 0,rear = 2;
11     queue[1][0] = x,queue[1][1] = y;
12     while(front < rear - 1)
13     {
14         ++front;
15         x=queue[front][0];
16         y=queue[front][1];
17         for(int i=0;i<4;++i)
18         {
19             int x1 = x+ flag[i][0];
20             int y1 = y + flag[i][1];
21             if(x1<1||y1<1||x1>n||y1>m||!a[x1][y1]||p[x1][y1]) continue;
22             p[x1][y1]=true;
23             queue[rear][0]=x1;
24             queue[rear++][1]=y1;
25         }
26     }
27 }
28 int main()
29 {
30     cin>>n>>m;
31     for(int i=1;i<=n;i++)
32     for(int j=1;j<=m;j++) 
33     cin>>a[i][j];
34     for(int i=1;i<=n;i++)
35         for(int j=1;j<=m;j++)
36             if(a[i][j]&&!p[i][j])
37             {
38                 ++ans;bfs(i,j);
39             }
40     cout<<ans<<'
';
41     return 0;
42 }

总体来说

队列算是目前比较基础的数据结构

只有基础扎实

以后做综合性大题时

才不会一脸懵

-end-