| ||||||||||
| 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