颠倒栈（栈和队列）

颠倒栈（栈和队列）

时间： 1ms        内存：1000M

描述：

题目：用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5}，1在栈顶。
颠倒之后的栈为{5, 4, 3, 2, 1}，5处在栈顶。

输入：

输入：

1 2 3 4 5

输出：

输出：

5 4 3 2 1

示例输入：

1 2 3 4 5 6

示例输出：

6 5 4 3 2 1

提示：

参考答案（内存最优[752]）：

#include <stdio.h>
#include <stdlib.h>
typedef struct inode
{int data;
 struct inode *next;
}listack;


void initstack(listack *st)
{st->next=NULL;
}
void push(listack *st,int e)
{listack *p=st->next;
 listack *s;
 s=(listack *)malloc(sizeof(listack));
 s->data=e;
 s->next=st->next;
 st->next=s;
}
int pop(listack *st)
{int e;
 listack *p=st->next;
 if(p==NULL)
	 return 0;
 e=p->data;
 st->next=p->next;
 free(p);
 return e;
}
void clearstack(listack *st)
{listack *p=st->next;
 while(p!=NULL)
 {free(st);
  st=p;
  p=p->next;
 }
 free(st);
}
void dispstack(listack *st)
{listack *p=st->next;
 while(p!=NULL)
 {printf("%d ",p->data);
  p=p->next;
 }
 printf("\n");
}
void chsidestack(listack *st)
{listack *p=st->next,*s;
 int e;
 if(p==NULL)
	 return ;
 else
 {e=pop(st);
  chsidestack(st);
  push(st,e);
 }
 return ;
}
int main()
{listack *st;
 int e;
 st=(listack *)malloc(sizeof(listack));
 initstack(st);
 while((scanf("%d",&e))!=EOF)
	 push(st,e);
 chsidestack(st);
 dispstack(st);
 clearstack(st);
 return 0;
}

参考答案（时间最优[0]）：

#include <stdio.h>
#include <stdlib.h>
typedef struct inode
{int data;
 struct inode *next;
}listack;


void initstack(listack *st)
{st->next=NULL;
}
void push(listack *st,int e)
{listack *p=st->next;
 listack *s;
 s=(listack *)malloc(sizeof(listack));
 s->data=e;
 s->next=st->next;
 st->next=s;
}
int pop(listack *st)
{int e;
 listack *p=st->next;
 if(p==NULL)
	 return 0;
 e=p->data;
 st->next=p->next;
 free(p);
 return e;
}
void clearstack(listack *st)
{listack *p=st->next;
 while(p!=NULL)
 {free(st);
  st=p;
  p=p->next;
 }
 free(st);
}
void dispstack(listack *st)
{listack *p=st->next;
 while(p!=NULL)
 {printf("%d ",p->data);
  p=p->next;
 }
 printf("\n");
}
void chsidestack(listack *st)
{listack *p=st->next,*s;
 int e;
 if(p==NULL)
	 return ;
 else
 {e=pop(st);
  chsidestack(st);
  push(st,e);
 }
 return ;
}
int main()
{listack *st;
 int e;
 st=(listack *)malloc(sizeof(listack));
 initstack(st);
 while((scanf("%d",&e))!=EOF)
	 push(st,e);
 chsidestack(st);
 dispstack(st);
 clearstack(st);
 return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。