Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
数组模拟链式队列,成功AC。#include<iostream> #include<string> using namespace std; int belong[1000000]; int pos[1005]; struct node { int x; int next; }r[200010]; //少写一个0,Wrong了七八次! int main() { int x,t,i,j,n,No=0; int front,back,used; //队首和队尾指针,新置入结点的地址。 string com; while(cin>>t&&t) { front=-1; back=-1; used=-1; for(i=0;i<t;++i) { cin>>n; //每组的人数。 for(j=0;j<n;++j) { cin>>x; belong[x]=i; //x属于第i组。 } pos[i]=-1; //pos[i]代表第i组最后一个组员所在的位置,初始化为-1,代表队列中暂时没有同组人。 } cout<<"Scenario #"<<++No<<endl; while(cin>>com&&com!="STOP") { if(com=="ENQUEUE") //入队。 { used++; cin>>x; if(pos[belong[x]]==-1) //队列中没有同组元素。 { if(front==-1&&back==-1) //第一个入队元素。 { front=used; back=used; r[used].x=x; r[used].next=-1; pos[belong[x]]=used; } else //非第一个入队元素。 { r[used].x=x; r[used].next=-1; r[back].next=used; back=used; pos[belong[x]]=used; } } else //队列中有同组元素,站在同组元素之后。 { if(pos[belong[x]]==back) back=used; r[used].x=x; r[used].next=r[pos[belong[x]]].next; r[pos[belong[x]]].next=used; pos[belong[x]]=used; } } else if(com=="DEQUEUE") //出队。 { cout<<r[front].x<<endl; if(pos[belong[r[front].x]]==front) pos[belong[r[front].x]]=-1; front=r[front].next; if(front==-1) back=-1; } } cout<<endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator