refresh的停车场

refresh的停车场

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

 refresh最近发了一笔横财，开了一家停车场。由于土地有限，停车场内停车数量有限，但是要求进停车场的车辆过多。当停车场满时，要进入的车辆会进入便道等待，最先进入便道的车辆会优先

进入停车场，而且停车场的结构要求只出去的车辆必须是停车场中最后进去的车辆。现告诉你停车场容量N以及命令数M，以及一些命令（Add num 表示车牌号为num的车辆要进入停车场或便道，

Del 表示停车场中出去了一辆车，Out 表示便道最前面的车辆不再等待，放弃进入停车场）。假设便道内的车辆不超过1000000.

输入

 输入为多组数据，每组数据首先输入N和M（0＜　ｎ，ｍ　＜200000），接下来输入M条命令。

输出

 输入结束后，如果出现停车场内无车辆而出现Del或者便道内无车辆而出现Out,则输出Error,否则输出停车场内的车辆，最后进入的最先输出，无车辆不输出。

示例输入

2 6
Add 18353364208
Add 18353365550
Add 18353365558
Add 18353365559
Del
Out

示例输出

18353365558
18353364208

这个题目气死我了，一开始读错了题目要求，结果多花了一个小时找错误，所以说要认真读题啊，题目要求是在所有输入后判断Del和Out的操作是否正确，如果正确就输出车站内车牌号，否则输出Error；

简单的讲一下这个题：这是一个栈与队列都考到的题目；但是不是太难；

有几个需要注意的点：

1、定义long long int 类型；

2、把握好什么时候进栈，什么时候进队列；

3、注意只要队列（便道）里有车，栈（停车场）内除最后一辆进的车，其他车都出不去（太坑爹了！！！），所以每当出现Del时都要判断站内是否有车，然后队列里先进的车进入栈，队列里所有车前移；

以下是代码：

#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#define maxsize 1000000  
  
typedef long long int element;  
typedef struct  
{  
    element *top,*base;  
    int lenstack;  
} Sqstack;  
typedef struct  
{  
    element *front, *rear;  
    int lenqueue;  
} Sqqueue;  
int initstack(Sqstack &L,int n)  
{  
    L.base=new element[n];  
    if(!L.base)  
        exit(-1);  
    L.top=L.base;  
    L.lenstack=n;  
    return 1;  
}  
int initqueue(Sqqueue &Q)  
{  
    Q.front=new element[maxsize];  
    if(!Q.front)  
        exit(-1);  
    Q.rear=Q.front;  
    Q.lenqueue=maxsize;  
}  
int pushstack(Sqstack &L,element x)  
{  
    if(L.top-L.base>L.lenstack)  
        return -1;  
    *(++L.top)=x;  
    return 0;  
}  
int pushqueue(Sqqueue &Q,element x)  
{  
    if(Q.rear-Q.front>Q.lenqueue)  
        return -1;  
    *(++Q.rear)=x;  
    return 0;  
}  
int popstack(Sqstack &L)  
{  
    if(L.top<=L.base)  
        return -1;  
    L.top--;  
    return 0;  
}  
long long int popqueue(Sqqueue &Q)  
{  
    if(Q.rear==Q.front)  
        return -1;  
    Q.front++;  
    return *(Q.front);  
}  
int main()  
{  
    int n,m;  
    char s[5];  
    element x;  
    Sqstack L;  
    Sqqueue Q;  
    while(~scanf("%d%d",&n,&m))  
    {  
        initstack(L,n);  
        initqueue(Q);  
        int t=0;  
        while(m--)  
        {  
            scanf("%s",s);  
            if(!strcmp(s,"Add"))  
            {  
                scanf("%lld",&x);  
                if(L.top-L.base<L.lenstack)  
                {  
                    pushstack(L,x);  
                }  
                else  
                {  
                    pushqueue(Q,x);  
                }  
            }  
            else if(!strcmp(s,"Del"))  
            {  
                if(L.top==L.base)  
                    t=1;  
                else if(Q.front<Q.rear)  
                {  
                    element e;  
                    e=*(Q.front+1);  
                    popqueue(Q);  
                    popstack(L);  
                    pushstack(L,e);  
                }  
                else  
                {  
                    popstack(L);  
                }  
            }  
            else  
            {  
                if(Q.front==Q.rear)  
                    t=1;  
                else  
                {  
                    popqueue(Q);  
                }  
            }  
        }  
        if(t==0)  
        while(L.top>L.base)  
        {  
            printf("%lld\n",*(L.top--));  
        }  
        else  
            printf("Error\n");  
    }  
  
    return 0;  
}