#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 5
typedef struct s //队节点
{
char c[8];
struct s *next;
}ss;
typedef struct //指针节点
{
ss *front;
ss *rear;
}queue;
typedef struct //栈节点
{
char data[N][8];
int top;
}stack;
stack *init1(stack *s)
{
s=(stack*)malloc(sizeof(stack));
s->top=-1;
return s;
}
void push(stack *s,char m[]) //入栈
{
s->top=s->top+1;
strcpy(s->data[s->top],m);
}
char *pop(stack *s) //出栈
{
return (s->data[s->top--]);
}
void init2(queue *Q) //初始化队列
{
ss *node;
node = (ss*)malloc(sizeof(ss)); //分配一个头节点
node->next = NULL;
Q->front=Q->rear=node; //分配一个头节点,头节点里啥也没有
}
void enqueue(queue *Q , char m[]) //入队
{
ss *node;
node = (ss*)malloc(sizeof(ss));
strcpy(node->c,m);
node->next = NULL;
Q->rear->next = node;
Q->rear = node;
printf("\t\t 停车场已满，车%s在便道上排队等候!",m);
}
void dequeue(queue *Q,stack *s1) //出队
{
ss *node;
node = Q->front->next;
push(s1,node->c); //出队入栈
printf("\t车%s进停车场!",node->c);
Q->front->next = node->next; // 注意有个头节点，当还不错后一个元素出队时，记得更新尾指针
if (Q->rear == node)
Q->rear = Q->front; //若只剩头结点，尾指针更新；若不更新，则要被free了
free(node);


}
void out(stack *s1,stack *s2,queue *Q,char m[])//出车函数
{
char n[8];
int i = 0;
strcpy(n,pop(s1)); //暂存pop(s1)的值到数组n中
while(strcmp(n,m)!=0) //循环找到要出车的车牌号
{
push(s2,n);
strcpy(n,pop(s1));
i++;
}
printf("\t\t 车%s离开停车场!",m);
if(i == 0) //while没有循环，出的较好的辆车就是要出的车
{
if(Q->rear != Q->front) //若有在等候的车，则进停车场
dequeue(Q,s1);
}
else
{
while(i--) //临时栈中的车再按照原来的次序进入停车场
push(s1,pop(s2));

if(Q->rear != Q->front) //若有在等候的车，则进停车场
dequeue(Q,s1);
}

}
int check(stack *s1 , char m[]) //查错函数 ,找不到相应车牌号，则返回1，反之，返回0
{
int k=s1->top; //暂存s1->top的值到k中
while(s1->top != -1)
if(strcmp(s1->data[s1->top--],m) == 0)
{
s1->top = k; //复原s1->top原来的值
return 0;
}
s1->top = k;
return 1;
}
void print(stack *s1 , queue *Q) //显示停车场和便道情况的函数
{
ss *p;
int k=s1->top; //暂存s1->top的值到k中
printf("\t\t 停车场内："); //显示停车场内的情况
if(s1->top == -1)
printf("停车场内没有车!\n");
else
{
while(s1->top != -1)
printf(" %s ",s1->data[s1->top--]);
}
s1->top=k; //复原s1->top原来的值
printf("\n\t\t 便道上面："); //显示便道上的情况
if(Q->rear == Q->front)
printf("便道上面没有车!");
else
{
for(p=Q->front->next ; p ; p=p->next)
printf(" %s ",p->c);
}
}
void destory(queue *Q) //销毁队列，释放内存
{
while(Q->front)
{
Q->rear = Q->front->next;
free(Q->front);
Q->front = Q->rear;
}
}
main()
{
int a;
char m[8];
queue Q;
stack *s1,*s2;
init2(&Q);
s1=init1(s1);
s2=init1(s2);
printf("\t\t\t #***停车场管理程序***#\n");
while(1)
{
printf("\n\t ********************************************************\n");
printf("\t 菜单:1.进车 2.出车 3.场内和便道上的情况 4.退出程序\n");
printf("\t ********************************************************\n");
printf("请输入选择： ");
scanf("%d",&a);
switch(a)
{
case 1:
printf("请输入车牌号: ");
scanf("%s",m);
if(s1->top!=4 )
{
push(s1,m);
printf("\t\t\t车%s进停车场!\t",m);
}
else
enqueue(&Q,m);
break;
case 2:
printf("请输入车牌号: ");
scanf("%s",m);
if(check(s1,m))
printf("\t\t\t%s的车!\n",m);
else
out(s1,s2,&Q,m);
break;
case 3:
print(s1,&Q);
break;
case 4:
free(s1);
free(s2);
destory(&Q);
exit(0);
default:printf("\t\t\t输入错误，请重新输入!\n");
}
}
}