数据结构实验之栈与队列十一：refresh的停车场

Description

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

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

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

Input

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

Output

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

Sample

Input

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

Output

18353365558
18353364208

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #define MAXN 200004
 5 #define MAXN1 1000004
 6 typedef struct node
 7 {
 8     char num[24];
 9 }st;//输入的一串数字，用字符串输入，因为它可能是栈也可能是队，所以用一个结构体，连接；
10 st stack[MAXN], link[MAXN1]; //定义的栈和队，中括号里面是尺寸大小；
11 int top, front, rear, n, m, flag;
12 void Add()
13 {
14     if(top < n - 1)//栈不满时，放在栈里，满了，放在队里；
15         scanf("%s",stack[++top].num);//++tio先加后用。
16     else
17         scanf("%s",link[rear++].num);//rear++先用后加；
18 }
19 void Del()
20 {
21     if(top == -1)//如果栈空，标记一下；
22         flag = 0;
23     else
24     {
25         if(rear > front)//如果队里有数，让队的第一个数赋给栈的最后一个，覆盖掉，然后front++，表示原来的front下的数被抛弃；
26         {
27             stack[top] = link[front];
28             front++;
29         }
30         else//如果队里没数，直接栈里减减；
31             top--;
32     }
33 }
34 void Out()
35 {
36     if(rear > front)//如果队里有数，第一个数被抛弃；
37         front++;
38     else//如果队里没数，标记一下
39         flag = 0;
40 }
41 void Pri()
42 {
43     for(; top >= 0; top--)//top从当前值开始倒序输出；
44         printf("%s
",stack[top].num);
45 }
46 int main()
47 {
48     char s[9];
49     while(~scanf("%d%d",&n,&m))
50     {
51         top = -1, flag = 1, front = rear = 0;//top是先加后用，front是先用后加，赋初始值不一样；
52         while(m--)
53         {
54             scanf("%s",s);
55             {
56                 if(!strcmp(s,"Add"))
57                     Add();
58                 else
59                     if(!strcmp(s,"Del"))
60                     Del();
61                 else
62                     if(!strcmp(s,"Out"))
63                     Out();
64             }
65         }
66         if(flag)
67             Pri();//如果flag = 1，可以输出；
68         else
69             printf("Error
");//如果flag =0；表示有错误命令，直接输出Error；
70     }
71     return 0;
72 }
73