/*利用一个栈逆置一个带头结点的单链表*/
#include <stdio.h>

#include <malloc.h>
#define maxsize 100
typedef int datatype;
typedef struct node
{datatype data;
struct node *next;
}linklist;
linklist *head;
typedef struct seqstack
{datatype d[maxsize];
int top;
}seqstack;
seqstack s;

linklist *creatlist()
{
linklist *q,*p;
int n=0;
p=q=(struct node *)malloc(sizeof(linklist));
head=p;
p->next=0;
p=(struct node *)malloc(sizeof(linklist));
scanf("%d",&p->data);
while(p->data!=-1)
{
n+=1;
q->next=p;
p=(struct node *)malloc(sizeof(linklist));
scanf("%d",&p->data);
}
q->next=0;
return (head);
}

void print(linklist *head)
{
linklist*p;
p=head->next;
if (p==0) printf("this ia an empty list.\n");
else
{do {printf("%6d",p->data);
p=p->next;
}while(p!=0);
printf("\n");
}
}

seqstack initstack()
{
s.top=-1;
return s;
}

int push(seqstack *s,datatype x)
{
if((*s).top==maxsize-1)
{printf("栈已满，不能入栈！\n");
return 0;
}
else {
(*s).top++;
(*s).d[(*s).top]=x;
return x;
}
}

datatype pop(seqstack *s)
{
datatype y;
if((*s).top==-1)
{
printf("栈已满，无法出栈！\n");
return 0;
}
else {
y=(*s).d[(*s).top];
(*s).top--;
return y;
}
}

int stackempty(seqstack s)
{
return s.top==-1;
}

int stackfull(seqstack s)
{
return s.top==maxsize-1;
}

linklist *backlinklist(linklist *head)
{
linklist *p;
p=head->next;
initstack();
while(p)
{
push(&s,p->data);
p=p->next;
}
p=head->next;
while(!stackempty(s))
{
p->data=pop(&s);
p=p->next;
}
return (head);
}

void main()
{
linklist *head;
head=creatlist();
print(head);
head=backlinklist(head);
print(head);
}