颠倒栈(栈和队列)

颠倒栈(栈和队列)

时间: 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;
}

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

点赞