数据结构：设停车场是一个可停放n辆车的狭长通道

Question

设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。在停车场内，汽车按到达的先后次序，由北向南依次排列（假设大门在最南端）。若停车场内已停满n辆车，则后来的汽车需要在门外的便道上等候，当有车开走时，便道上的第一辆车即可进入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门后，其它车辆再按原次序返回停车场。每辆车离开停车场时，应按其停留时间的长短交费（在便道上停留的时间不收费）。试编写程序，模拟上述管理过程。要求以顺序栈模拟停车场，以链队列模拟便道。从终端读入汽车到达或离去的数据，每组数据包括三项：（1）是“到达”还是“离去”；（2）汽车牌照号码；（3）“到达”或“离去”的时间。与每组输入信息相对应的输出信息为：如果是到达的车辆，则输出其在停车场中或便道上的位置；如果是离去的车辆，则输出其在停车场中停留的时间和应交的费用。（提示：需另设一个栈，临时停放为让路而从车场退出的车）

Answer 1

C语言：建立2个顺序栈，1个链表队列，模拟车辆停放。
运行结果如下：

代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//定义车辆信息
typedef struct _carinfo
{
    char id[10]; //车牌号
    int hourCome; //到达时间，时，为了简便，这里只处理同一天内的时间
    int minCome; //到达时间，分钟
    int hourLeave; //离开时间，时
    int minLeave; //离开时间，分钟
}Carinfo;

/*****************************************************定义顺序栈，栈，先进后出xqls*********************************/

typedef struct _Stack
{
    Carinfo* pcar;
    int maxlen;
    int front;
}Stack;

//初始化栈
void Stackinit(Stack* s,int size)
{
    s->maxlen = size;
    s->pcar = (Carinfo*)malloc(size * sizeof(Carinfo));
    s->front = 0;
}
//入栈
int Stackpush(Stack* s, Carinfo c)
{
    if (s->front >= s->maxlen)
        return 0;
    else
    {
        s->pcar[s->front] = c;
        s->front++;
        return s->front;
    }
}
//出栈
int Stackpop(Stack* s, Carinfo* e)
{
    if (s->front <= 0)
        return 0;
    else
    {
        s->front--;
        *e = s->pcar[s->front];
        return 1;
    }
}

//判断是否为空
int Stackempty(Stack s)
{
    if (s.front <= 0)
        return 1;
    else
        return 0;
}


//判断栈是否满
int StackFull(Stack s)
{
    if (s.front == s.maxlen)
        return 1;
    else
        return 0;
}

/*****************************************************定义链式队列，先进先出xqls*********************************/
typedef struct _node
{
    Carinfo car;
    struct _node* next;
}QueueNode,*Queue;
//初始化队列
Queue Queueinit()
{
    Queue head = (Queue)malloc(sizeof(QueueNode));
    head->next = 0;
    return head;
}
//入队
int Queuepush(Queue q, Carinfo c)
{
    Queue p = q;
    QueueNode* t = (QueueNode*)malloc(sizeof(QueueNode));
    int pos = 1;

    t->car = c;
    t->next = 0;
    while (p->next)
    {
        p = p->next;
        pos++;
    }
        
    p->next = t;
    return pos;
}
//出队
int Queuepop(Queue q, Carinfo* e)
{
    Queue p = q->next;
    if (q->next == 0)
        return 0;
    else
    {
        *e = p->car;
        q->next = p->next;
        free(p);
        p = 0;
        return 1;
    }
}
//判断是否为空
int Queueempty(Queue q)
{
    if (q->next == 0)
        return 1;
    else
        return 0;
}


//计算停车费xqls
double pay(int h1, int m1, int h2, int m2,double p)
{
    int s1 = h1 * 60 + m1;
    int s2 = h2 * 60 + m2;
    double out = (s2 - s1) / 60.0 * p;
    return out;
}



int main()
{
    Stack parking; //停车场栈 xqls
    Stack tmp;   //临时栈 xqls
    Queue waiting; //等候队列 xqls

    int n; //停车场最多停放的车辆数目
    int op; //操作
    int h, m;
    int pos = 0;
    char id[10] = { 0 };

    double pay_perhour = 2; //每小时的停车费

    printf("请输入停车场最大的停车数量n：");
    scanf("%d", &n);

    //初始化
    Stackinit(&parking,n);
    Stackinit(&tmp,n);
    waiting = Queueinit();



    while (1)
    {
        printf("请输入操作：1.到达；2.离开；3.退出程序 : ");
        scanf("%d", &op);
        if (op == 2 && Stackempty(parking))
        {
            printf("停车场目前暂无车辆\n");
            continue;
        }
        printf("请输入车牌号：");
        scanf("%s", id);
        //到达
        if (op == 1)
        {
            printf("请输入到达时间(HH:MM)：");
            scanf("%d:%d", &h, &m);
            Carinfo cc;
            strcpy(cc.id, id);
            cc.hourCome = h;
            cc.minCome = m;
            if (StackFull(parking))
            {
                pos = Queuepush(waiting, cc);
                printf("便道位置：%d\n", pos);
            }
            else
            {
                pos = Stackpush(&parking, cc);
                printf("停车场位置：%d\n", pos);
            }
                
        }
        else if (op == 2)
        {
            while (1)
            {
                //该车之后的先出栈，入临时栈
                Carinfo cc;
                Stackpop(&parking, &cc);
                if (strcmp(cc.id, id) == 0)
                {
                    printf("请输入离开时间(HH:MM)：");
                    scanf("%d:%d", &cc.hourLeave, &cc.minLeave);
                    printf("缴费：%.1f\n",pay(cc.hourCome, cc.minCome, cc.hourLeave, cc.minLeave, pay_perhour));
                    break;
                }
                else
                {
                    Stackpush(&tmp, cc);
                    printf("    %s入临时栈\n", cc.id);
                }
            }
            //临时栈车辆返回
            while (!Stackempty(tmp))
            {
                Carinfo cc;
                Stackpop(&tmp, &cc);
                Stackpush(&parking, cc);
                printf("    %s返回停车场\n", cc.id);
            }
            
            //等待队列入栈
            if (!Queueempty(waiting))
            {
                Carinfo cc;
                Queuepop(waiting, &cc);
                pos = Stackpush(&parking, cc);
                printf("%s驶入停车场，位置：%d\n", cc.id,pos);
            }


        }
        else if (op == 3)
            break;
    }
    return 0;

}