做一个功能强大的栈.doc

一个功能强大的栈

　　　　　　　　　　做一个功能强大的栈
　　　　　　　　　　　　　　华南理工大学　Mental
　　对于一个栈来说，一般要考虑两个方面：一是上溢问题，二是出入栈的数据类型的限制。
　　对于第一个方面，如果用顺序表储存栈，空间利用率可达100%，但会产生上溢问题，如果用链表储存栈，虽然不会产生上溢问题（在内存充足的情形下），但空间利用效率会降低，所以可以综合两者来储存栈，先用顺序表储存栈，当发生上溢问题时可以建立另一个顺序表，并且将所有的顺序表再组成一个链表，实现储存的源代码如下：
　　#define bsize 10
　　typedef struct t{
　　datetype date[bsize];
　　struct t *next;
　　}tss;
　　typedef struct s{
　　 tss *stack_top;
　　 int pos;
　　 int tss_num;
　　}stack_info;
　　byte *stack_ch;int stack_i;
　　int empty(stack_info *s)
　　{
　　  if(s->pos==-1&&s->tss_num==1)return 1;
　　  return 0;
　　}
　　stack_info *creat()
　　{
　　  tss *top;
　　  stack_info *head;
　　  head=(stack_info *)malloc(sizeof(stack_info));
　　  top=(tss *)malloc(sizeof(tss));
　　  head->stack_top=top;
　　  top->next=NULL;
　　  head->pos=-1;
　　  head->tss_num=1; 
　　  return head;
　　}
　　pusha(datetype x,stack_info *head)
　　{
　　 tss *one;
　　 if(head->pos==bsize-1)
　　  {
　　   one=(tss *)malloc(sizeof(tss));
　　   one->next=head->stack_top;
　　   head->stack_top =one;
　　
　　   head->stack_top->date[0]=x;
　　   head->pos=0;
　　   head->tss_num++;
　　  }
　　  else head->stack_top->date[++head->pos]=x;
　　}
　　datetype popa(stack_info *head)
　　{  tss *one;
　　   if(empty(head)){printf("empty");return 0;}
　　   if(head->pos==-1)
　　     {
　　      one=head->stack_top;
　　      head->stack_top=one->next;
　　      free(one);
　　      head->tss_num--;
　　      head->pos=bsize-2;
　　      return head->stack_top->date[bsize-1];
　　     }
　　   else return head->stack_top->date[head->pos--];
　　}
　　对于第二个方面，因为每个变量都是由一个或多个字节连续组成，而这些字节在内存空间都是线性排列的，所以可将变量分成一个个的字节，并将这些字节压入栈，出栈则将这些字节出栈，并组成原来变量的值，这样可以实现不同类型的变量共享同一个栈。实现这样的功能关健在两个地方：第一个是建立一个char(字节)类型的栈。第二个是如何分解变量，可以这样做，首先取得变量的大小n，即所占字节的多少，还有变量的地址，然后将该变量的地址强制变为一个char类型的地址，然后在转换后的地址上读出n个字节，并将其压入栈，出栈同理，但注意顺序。在编程上可用两个宏实现push和pop功能。以下为这两个宏：
　　byte *stack_ch;int stack_i;/*为PUSH，POP两宏定义两个变量*/
　　#define PUSH(var,head) { stack_ch=( byte *)(&var);\
　　for(stack_i=0;stack_i<sizeof(var);stack_i++)\
　　pusha(stack_ch[stack_i],head);}\
　　
　　#define POP(var,head) {stack_ch=( byte *)(&var); \
　　for(stack_i=sizeof(var)-1;stack_i>=0;stack_i--)\
　　stack_ch[stack_i]=popa(head);}\
　　/*以上f是任一类型的变量，注意f必须是变量。head的类型为stack_info的指针,
　　　　　　　　　　是指向下文所建的栈的栈顶的一个头结点*/
　　结合两个方面，可以做一个功能强大的栈，这样的栈不会产生上溢问题，而且提高空间利用率，更有特色的地不同类型的变量可共享同一个栈。