实验三 栈和队列的应用_3栈和队列实验应用
实验三 栈和队列的应用由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“3栈和队列实验应用”。
一、实验目的掌握栈的数据类型描述及栈的特点；掌握栈的顺序存储结构的特点及算法描述；掌握队列的数据类型描述及链式存储结构的特点和算法描述。
二、实验内容
停车场管理。设有一个可以停放n辆汽车的狭长停车场（先进后出），它只有一个大门可以供车辆进出。车辆按到达停车场时间的先后依次从停车场最里面向大95E8口处停放（最先到达的第一辆车停放在停车场的最里面）。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车离开，则排在便道上的第一辆车就可以进入停车场。停车场内如有某辆车要离开，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车再按原来的次序进停车场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车没进停车场就要离开，允许其离开，不收停车费，并且仍然保持在便道上的车辆次序。试编程模拟停车场管理。
三、算法描述
提示：可以将停车场定义成一个顺序栈s1，便道定义成一个链队列q，而停车场中的某辆车要离开，则在它后面进停车场的车必须让道，让其离开，故还必须有一个临时的顺序栈s2，存放让道的车辆。
当有车辆进停车场时，直接进入s1栈，若s1栈满，则进入便道（链队列q）。若有s1中车辆x离开时，先让在x后面进栈的车从s1退栈并进栈到s2中，让x离开并收取停车费，然后，再把s2中的所有车辆退栈并重新进入s1栈，最后，将链队列q的队头车辆进栈到s1中并删除队头车辆。若有链队列q（便道）中的车辆y离开时，从链队列中删除该车辆即可，不收停车费。
车辆的数据可以表示为（车辆编号，到达/离开时间）。
四.程序清单: #include using namespace std;const int StackSize=5;cla SeqStack { public:
SeqStack(){top=-1;} ~SeqStack(){};void Push(int x);void Push2(int x);int *Return();int Pop(int y);int Count();void PrintStack();private: int data[StackSize];int top;};//入栈
void SeqStack::Push(int x){ if(top>=StackSize-1)throw“上溢”;for(int i=0;i
if(data[i]==x)
{
cout
i=-1;
cin>>x;
} } top++;data[top]=x;} //返回数组地址
int *SeqStack::Return(){ return data;} //临时栈
void SeqStack::Push2(int x){ top++;data[top]=x;
} //输出函数
void SeqStack::PrintStack(){ for(int i=0;i
cout
int SeqStack::Pop(int y){ if(top==-1)throw“下溢”;int x;x=data[top--];if(y==top+2)data[top+1]=123456789;if(top==-1)data[top+1]=123456789;return x;} //数数
int SeqStack::Count(){ return top;}
//队列
struct Node { int data;Node *next;};cla LinkQueue { public: LinkQueue();void EnQueue(int x,int *q);void xzDeQueue(int x);int Count();int DeQueue();
private: Node *front,*rear;};//构造函数
LinkQueue::LinkQueue(){ Node *s=new Node;s->next=NULL;front=rear=s;} //入队
void LinkQueue::EnQueue(int x,int *q){ Node *s=new Node;Node *p=new Node;p=front;while(p){
if(p->data ==x)
{
cout
cin>>x;
for(int i=0;i
{
if(x==q[i])
{
cout
cin>>x;
i=-1;
}
}
p=front;} p=p->next;} s->data =x;s->next =NULL;
rear->next =s;rear=s;} //出队
int LinkQueue::DeQueue(){ if(front==rear)throw“便道无车辆”;Node *p=new Node;int x;p=front->next;x=p->data;front->next =p->next;if(p->next ==NULL)rear=front;delete p;return x;} //计算结点数
int LinkQueue::Count(){ Node *p=new Node;p=front;int i=0;while(p&&p->next!=NULL){
p=p->next;
i++;} return i;} //选择性出队
void LinkQueue::xzDeQueue(int x){ if(rear==front)throw“便道无车辆”;Node *p=new Node;p=front;int y;int i=0;for(;p->next!=NULL;p=p->next)
{
if(p->next->data ==x)
if(p->next->next!=NULL)
{
Node *q=new Node;
q=p->next;
y=q->data;
p->next =q->next;
i=1;
delete q;
cout
break;
}
else
{
Node *q=new Node;
q=p->next;
y=q->data;
p->next =NULL;
i=1;
delete q;
if(front->next==NULL)rear=front;
cout
break;
}
} if(i==0)cout
SeqStack b;//b是作为临时存放车辆的栈
LinkQueue c;//c是作为便道的队列
cout
cout
int xh1=1;//xh1为菜单最外层的循环控制变量
int time[100];//记录各车辆进入停车场的时间
int t1=0;//作为车辆对应的时间编号
int money=1;while(xh1==1){
cout
cin>>zl;
switch(zl)
{
case 1:
try{
int n1=a.Count();
int n;
cout
cin>>n;
if(n1==4)
{
int *Num=a.Return();
for(int i=0;i
if(Num[i]==n)
{
cout
cin>>n;
i=-1;
}
int *CarNum=a.Return();
c.EnQueue(n,CarNum);
cout
break;
}
a.Push(n);
cout
cin>>time[t1];
while(time[t1]=24)
{
cout
cin>>time[t1];
}
t1++;
}
catch(char*s){cout
break;
case 2:
try{int n2;//离开车辆的编号
cout
cin>>n2;
if(a.Count()+1==0)
{
cout
break;
}
else
while(n2a.Count()+1)
{
cout
cin>>n2;
}
int j=a.Count();
for(int i=0;i
b.Push2(a.Pop(n2));
a.Pop(n2);
int j2=b.Count();
for(int i1=0;i1
a.Push(b.Pop(n2));
int j3=c.Count();
int time1;
cout
cin>>time1;
while(time123)
{
cout
cin>>time1;
}
int day=0;
if(time1
{
cout
cin>>day;
while(day
{
cout
cin>>day;
}
}
cout
for(int i2=0;i2
time[n2-1+i2]=time[n2+i2];
t1--;
if(j3!=0)
{
a.Push(c.DeQueue());
cout
cout
cin>>time[t1];
while(time[t1]=24)
{
cout
cin>>time[t1];
}
t1++;
}
}catch(char *s){cout
break;
case 3:
a.PrintStack();break;
case 4:
int n3;
cout
cin>>n3;try{
c.xzDeQueue(n3);}catch(char*s){cout
break;
case 5:
cout
cin>>money;
cout
cout
break;
case 6:
xh1=0;
break;
} } system(“pause”);}
心得体会:
完成时间:2010-10-30
