Problem Description
refresh 最近发了一笔横财, 开了一家停车场. 由于土地有限, 停车场内停车数量有限, 但是要求进停车场的车辆过多. 当停车场满时, 要进入的车辆会进入便道等待, 最先进入便道的车辆会优先
进入停车场, 而且停车场的结构要求只出去的车辆必须是停车场中最后进去的车辆. 现告诉你停车场容量 N 以及命令数 M, 以及一些命令 (Add num 表示车牌号为 num 的车辆要进入停车场或便道,
Del 表示停车场中出去了一辆车, Out 表示便道最前面的车辆不再等待, 放弃进入停车场). 假设便道内的车辆不超过 1000000.
Input
输入为多组数据, 每组数据首先输入 N 和 M(0< n,m <200000), 接下来输入 M 条命令.
Output
输入结束后, 如果出现停车场内无车辆而出现 Del 或者便道内无车辆而出现 Out, 则输出 Error, 否则输出停车场内的车辆, 最后进入的最先输出, 无车辆不输出.
- Sample Input
- 2 6
- Add 18353364208
- Add 18353365550
- Add 18353365558
- Add 18353365559
- Del
- Out
- Sample Output
- 18353365558
- 18353364208
- Hint
- Source
注: 原来做的时候, 栈没有用 base 指针, 一直错误, 还没有找到出现问题的原因
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- typedef struct node
- {
- char num[25];
- struct node *next;
- } Node;
- typedef struct
- {
- Node *top;
- Node *base;
- int len;
- } SeqStack;
- typedef struct
- {
- Node *front;
- Node *rear;
- int len;
- } SeqQueue;
- Node* NewNode()
- {
- Node *p;
- p = (Node*)malloc(sizeof(Node));
- p->next = NULL;
- return p;
- }
- // 接下来是对栈的操作
- SeqStack* CreateStack()
- {
- SeqStack *t;
- t = (SeqStack*)malloc(sizeof(SeqStack));
- t ->top =NewNode();
- t->base = t->top;
- t->len = 0;
- return t;
- }
- int IsEmptyS(SeqStack *s)
- {
- if (s->top->next == NULL)
- return 1;
- return 0;
- }
- void PushS(SeqStack *s, char num[])
- {
- Node *p = NewNode();
- strcpy(p->num,num);
- p->next = s->top->next;
- s->top->next = p;
- s->base = p;
- s->len++;
- }
- void PopS(SeqStack *s)
- {
- Node *t;
- t = s->top->next;
- s->top->next = s->top->next->next;
- free(t);
- s->len--;
- }
- void ClearS(SeqStack* s)
- {
- while(!IsEmptyS(s))
- {
- PopS(s);
- }
- }
- // 接下来是对队列的操作
- SeqQueue* CreateQueue()
- {
- SeqQueue *q;
- q = (SeqQueue*)malloc(sizeof(SeqQueue));
- q->front = NewNode();
- q->rear = q->front;
- q->len = 0;
- return q;
- }
- int IsEmptyQ(SeqQueue *q)
- {
- if (q->front->next == NULL)
- return 1;
- return 0;
- }
- void PushQ(SeqQueue *q, char num[])
- {
- Node *t = NewNode();
- strcpy(t->num, num);
- q->rear->next = t;
- q->rear = t;
- q->len++;
- }
- void PopQ(SeqQueue *q)
- {
- Node *t = q->front->nexxt;
- q->front->next = q->front->next->next;
- free(t);
- q->len--;
- }
- void show(Node *t)
- {
- Node *p = t->next;
- while(p)
- {
- printf("%s\n", p->num);
- p = p->next;
- }
- }
- void ClearQ(SeqQueue *q)
- {
- if(!IsEmptyQ(q))
- {
- PopQ(q);
- }
- }
- int main()
- {
- int n, m;
- char str[25];
- char num[25];
- SeqQueue *q;
- SeqStack *s;
- s = CreateStack();
- q = CreateQueue();
- while(~scanf("%d%d", &n, &m))
- {
- int flag = 1;
- ClearS(s);
- ClearQ(q);
- while(m--)
- {
- scanf("%s", str);
- if (strcmp(str, "Add") == 0) // 如果栈没满, 入栈, 否则入队
- {
- scanf("%s", num);
- if (s->len>= n)
- {
- PushQ(q, num);
- }
- else
- {
- PushS(s, num);
- }
- }
- else if (strcmp(str, "Del") == 0) // 如果栈没空, 则出栈, 同时后面的车出队入栈
- {
- if (!IsEmptyS(s))
- {
- PopS(s);
- if (!IsEmptyQ(q))
- {
- strcpy(num,q->front->next->num);
- PopQ(q);
- PushS(s, num);
- }
- }
- else
- {
- flag = 0;
- }
- }
- else if (strcmp(str, "Out") == 0) // 不排队, 出队
- {
- if (!IsEmptyQ(q))
- {
- PopQ(q);
- }
- else
- {
- flag = 0;
- }
- }
- }
- if (flag == 0)
- {
- printf("Error\n");
- }
- else
- {
- show(s->top);
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3207088.html