数据结构实验之栈与队列十一：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

#include<bits/stdc++.h>using namespace std;#define intsize 10000 #define addsize 10000 typedef long long int selemtype; typedef long long int qelemtype;typedef struct {selemtype *base;selemtype *top;int stacksize; } Sqstack;typedef struct Queue {qelemtype data;struct Queue *next; } Queue, *queueptr;typedef struct {queueptr fron;//队头指针queueptr rear;//队尾指针 } linkqueue;int initstack(Sqstack &s, int n) //建立空栈 {s.base = (selemtype *)malloc(n * sizeof(selemtype));if(!s.base)return -1;s.top = s.base;return 1; }int push(Sqstack &s, selemtype e) {if(s.top - s.base >= s.stacksize){s.base = (selemtype *)realloc(s.base, (s.stacksize + addsize) * sizeof(selemtype));if(!s.base)return -1;s.top = s.base + s.stacksize;s.stacksize += addsize;}*s.top++ = e;return 1; } int pop(Sqstack &s, selemtype &e) {if(s.base == s.top)return 0;e = *--s.top;return 1; } int isempty(Sqstack s)//这里注意一下不能写成Sqstack &s {if(s.base == s.top)return 1;elsereturn 0; }int initqueue(linkqueue &q) {q.fron = q.rear = new Queue;if(!q.fron)return -1;q.fron->next = NULL;return 1; } int enqueue(linkqueue &q, qelemtype e) {queueptr p = new Queue;if(!p)return -1;p->data = e;p->next = NULL;q.rear->next = p;q.rear = p;return 1; } int dequeue(linkqueue &q, qelemtype &e) {if(q.fron == q.rear)return 0;queueptr p = q.fron->next;e = p->data;q.fron->next = p->next;if(q.rear == p)//如果是最后一个元素被删除，队尾指针也丢失q.rear = q.fron;free(p);return 1; } int qempty(linkqueue q) {if(q.rear == q.fron)return 1;elsereturn 0; } int main() {int m, n;//n是栈的容量while(~scanf("%d%d", &n, &m)){Sqstack s;initstack(s, n);//n是栈的容量，栈的容量是固定的linkqueue q;initqueue(q);int flag = 0;selemtype e;char c[10];long long int num;while(m--){scanf("%s", c);//空格就是结束此字符串的输入if(strcmp(c, "Add") == 0){scanf("%lld" ,&num);if(s.top - s.base < n)//有剩余车位，判断栈满。n为栈的容量{push(s, num);}else{enqueue(q, num);}} else if(strcmp(c, "Del") == 0){if(isempty(s)){flag = 1;}else{pop(s, e);if(!qempty(q)){qelemtype temp;dequeue(q, temp);push(s, temp);}}} else if(strcmp(c, "Out") == 0){if(qempty(q)){flag = 1;}qelemtype temp;dequeue(q, temp);}}if(flag)printf("Error\n");else{while(!isempty(s)){pop(s, e);printf("%lld\n", e);}}} }

总结

以上是生活随笔为你收集整理的数据结构实验之栈与队列十一：refresh的停车场的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。