栈与队列--refresh的停车场

我会带着你远行 2022-07-19 00:11 122阅读 0赞

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

## 提示 ##

## 这道题要注意最后的输出，是全部都输入完成后再输出，而不是没操作一次输出一次！ ##

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<malloc.h>
    #define maxsize 10000050
    int n;
    int i;
    int flag;
    typedef struct
    {
        long long int *top;//注意要定义长整型，不管是栈还是队列
        long long int *base;
        int stacksize;
    }qstack;
    
    typedef struct
    {
       long long int *base;
        int front;
        int rear;
        int length;
    }squeue;
    
    //初始化栈
    int Initstack(qstack &s)
    {
        s.base=(long long int *)malloc(maxsize*sizeof(long long int));
        s.top=s.base;
        s.stacksize=maxsize;
        return 0;
    }
    //初始化队列
    int Initqueue(squeue &Q)
    {
        Q.base=(long long int  *)malloc(maxsize*sizeof(long long int ));
        Q.front=Q.rear=0;
        Q.length=0;
    }
    //进栈且判断
    void Pushstack(qstack &s,squeue &Q,char q[])
    {
        long long int num;
        if(q[0]=='A')
        {
            scanf("%lld",&num);
            if(i>=n)
            {
                Q.base[Q.rear]=num;
                Q.rear++;
                Q.length++;
            }
            else
            {
                *(++s.top)=num;
                i++;
            }
        }
        else if(q[0]=='D')
        {
            if(s.top==s.base)
            {
                flag++;
               return;
            }
            s.top--;
            i--;
            if(Q.length>0)//要注意这个地方对队列长度的判断
            {
                *(++s.top)=Q.base[Q.front];//括号内是Q.front而不是Q.rear
                i++;//i++不要忘了
                Q.length--;
                //移位操作
                for(int j=0;j<Q.length;j++)
                {
                    Q.base[j]=Q.base[j+1];
    
                }
            }
        }
        else if(q[0]=='O')
        {
            if(Q.length==0)
            {
                flag++;//不合法的操作判断
                return ;
            }
            Q.length--;
            Q.rear--;//Q.rear--不要忽略
            if(Q.length>0)//只有在长度大于零时才进行移位操作
            {   for(int j=0;j<Q.length;j++)
                {
                    Q.base[j]=Q.base[j+1];
                }
            }
        }
    }
    //出栈
    void Putstack(qstack &s,squeue &Q)
    {
        if(flag>0)
        {
            printf("Error\n");
            return ;
        }
        while(s.top>s.base)
        {
            printf("%lld\n",*(s.top--));
        }
    }
    int main()
    {
        int m;
        char a[4];
        qstack s;
        squeue Q;
        while(~scanf("%d %d",&n,&m))
        {
            flag=0;
            i=0;
            Initstack(s);
            Initqueue(Q);
            for(int j=0;j<m;j++)
            {
                scanf("%s",&a);
                Pushstack(s,Q,a);
            }
            Putstack(s,Q);
        }
        return 0;
    }