7-3 停车场管理 (20point(s))

设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的先后次序依次从停车场最里面向大门口处停放 (即最先到达的第一辆车停放在停车场的最里面) 。如果停车场已放满n辆车，则以后到达的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车可以进入停车场。停车场内如有某辆车要开走，则在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费，停留在便道上的车不收停车费。编写程序对该停车场进行管理。

输入格式:

先输入一个整数n(n<=10)，再输入若干组数据，每组数据包括三个数据项：汽车到达或离开的信息（A表示到达、D表示离开、E表示结束）、汽车号码、汽车到达或离开的时刻。

输出格式:

若有车辆到达，则输出该汽车的停车位置；若有车辆离开，则输出该汽车在停车场内停留的时间。如果汔车号码不存在，输出the car not in park

输入样例:

输出样例:

car#1 in parking space #1
car#2 in parking space #2
car#3 in parking space #3
car#1 out,parking time 3
car#4 in parking space #3
car#5 waiting
car#4 out,parking time 2
car#5 in parking space #3
car#5 out,parking time 1

用到队列和栈

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define MAXVAL  10

typedef struct _item {
    int num;
    int time;
} Item;

typedef struct _stack {
    Item val[MAXVAL];
    int p;
} Stack;

Stack* createStack(void);
void push(Stack *pstack, const Item pitem);
Item pop(Stack *pstack);
bool isEmpty(Stack *pstack);
bool isFull(Stack *pstack);

int n;

int main()
{
    char flag;
    int a, b, h, t;
    Item queue[100];
    Stack *stop = NULL;
    scanf("%d", &n);

    stop = createStack();
    h = 0;
    t = 0;

    while (true)
    {
        Item item;
        scanf("%c %d %d", &flag, &a, &b);
        // printf("读到了：%c %d %d
", flag, a, b);
        if (flag == 'E') {
            break;
        }
        item.num = a;
        item.time = b;
        if (flag == 'A') {
            if (!isFull(stop)) {
                push(stop, item);
                // printf("item.num = %d
", item.num);
                printf("car#%d in parking space #%d
", item.num, stop->p);
            } else {
                queue[t = (t+1) % 100] = item;
                printf("car#%d waiting
", item.num);
            }
        } else if (flag == 'D') {
            if (!isEmpty(stop)) {
                Stack *st = createStack();
                int found = 0;
                while (!isEmpty(stop))
                {
                    Item tmp = pop(stop);
                    if (tmp.num == item.num) {
                        printf("car#%d out,parking time %d
", tmp.num, b - tmp.time );
                        found = 1;
                    } else {
                        push(st, tmp);
                    }
                }
                if (!found) {
                    printf("the car not in park
");
                }
                // 还原车位
                while (!isEmpty(st)) {
                    push(stop, pop(st));
                }

                if (!isFull(stop) && t != h) {
                    Item tmp = queue[h = (h+1) % 100];
                    tmp.time -= t - h - 1;
                    push(stop, tmp);
                    
                    printf("car#%d in parking space #%d
", tmp.num, stop->p);
                }
            } else {
                printf("the car not in park
");
            }
        }
    }

    free(stop);
    return 0;
}

Stack* createStack(void)
{
    Stack *p = malloc(sizeof(Stack));
    return p;
}

void push(Stack *pstack, const Item pitem)
{
    int *p = &(pstack->p);
    if (*p < n) {
        pstack->val[(*p)++] = pitem;
    }
}

Item pop(Stack *pstack)
{
    return pstack->val[--(pstack->p)];
}

bool isEmpty(Stack *pstack)
{
    return pstack->p == 0;
}

bool isFull(Stack *pstack)
{
    return pstack->p == n;
}