数据结构C语言实现系列[2]——栈

#include  < stdio.h > #include  < stdlib.h > typedef  int  elemType; /* ********************************************************************** */ /*                       以下是关于栈顺序存储操作的6种算法                             */ /* ********************************************************************** */ struct  stack{    elemType  * stack;         /*  存储栈元素的数组指针  */      int  top;                 /*  存储栈顶元素的下标位置  */      int  maxSize;             /*  存储stack数组的长度  */ }; void  againMalloc( struct  stack  * s){     /*  空间扩展为原来的2倍，原内容被自动拷贝到p所指向的存储空间中  */     elemType  * p;    p  =  realloc(s -> stack,  2   *  s -> maxSize  *   sizeof (elemType));     if ( ! p){        printf( " 内在分配失败！ " );        exit( 1 );    }    s -> stack  =  p;         /*  使stack指向新的栈空间  */     s -> maxSize  =   2   *  s -> maxSize;         /*  把栈空间的大小修改新的长度  */      return ;} /*  1.初始化栈s为空  */ void  initStack( struct  stack  * s,  int  ms){     if (ms  <= 0 ){        printf( " ms的值非法！ " );        exit( 1 );    }    s -> maxSize  =  ms;    s -> stack  =  malloc(ms  *  ( sizeof (elemType)));     if ( ! s -> stack){        printf( " 内在分配失败！ " );        exit( 1 );    }    s -> top  =   - 1 ;         /*  初始置栈为空  */      return ;} /*  2.新元素进栈，即把它插入到栈顶  */ void  push( struct  stack  * s, elemType x){     /*  若栈空间用尽则重新分配更大的存储空间  */      if (s -> top  ==  s -> maxSize  -   1 ){        againMalloc(s);    }    s -> top ++ ;         /*  栈顶指针后移一个位置  */     s -> stack[s -> top]  =  x;         /*  将新元素插入到栈顶  */      return ;} /*  3.删除(弹出)栈顶元素并返回其值  */ elemType pop( struct  stack  * s){     /*  若栈空则退出运行  */      if (s -> top  ==   - 1 ){        printf( " 栈空，无元素出栈！ " );        exit( 1 );    }    s -> top -- ;         /*  栈顶指针减1表示出栈  */      return  s -> stack[s -> top + 1 ];         /*  返回原栈顶元素的值  */ } /*  4.读取栈顶元素的值  */ elemType peek( struct  stack  * s){     /*  若栈空则退出运行  */      if (s -> top  ==   - 1 ){        printf( " 栈空，无元素可读取！ " );        exit( 1 );    }     return  s -> stack[s -> top];         /*  返回原栈顶元素的值  */  } /*  5.判断s是否为空，若是则返回1表示真，否则返回0表示假  */ int  emptyStack( struct  stack  * s){     if (s -> top  ==   - 1 ){         return   1 ;    } else {         return   0 ;    }} /*  6.清除栈s中的所有元素，释放动态存储空间  */ void  clearStack( struct  stack  * s){     if (s -> stack){        free(s -> stack);        s -> stack  =  NULL;        s -> top  =   - 1 ;        s -> maxSize  =   0 ;    }     return ;} /* ********************************************************************** */ int  main(){     struct  stack s;     int  a[ 8 ]  =  { 3 ,  8 ,  5 ,  17 ,  9 ,  30 ,  15 ,  22 };     int  i;    initStack( & s,  5 );     for (i  =   0 ; i  <   8 ; i ++ ){        push( & s, a[i]);    }    printf( " %d  " , pop( & s)); printf( " %d  " , pop( & s));    push( & s,  68 );    printf( " %d  " , peek( & s));    printf( " %d  " , pop( & s));     while ( ! emptyStack( & s)){        printf( " %d  " , pop( & s));    }    printf( " " );    clearStack( & s);    system( " pause " );     return   0 ;}

 

 

/* ********************************************************************** */ /*                       以下是关于栈链接存储操作的6种算法                  */ /* ********************************************************************** */ struct  sNode{    elemType data;     struct  sNode  * next;}; /*  1.初始化链栈为空  */ void  initStack( struct  sNode *   * hs){     * hs  =  NULL;         return ;} /*  2.向链中插入一个元素（入栈）  */ void  push( struct  sNode *   * hs, elemType x){     struct  sNode  * newP;    newP  =  malloc( sizeof ( struct  sNode));     if (newP  ==  NULL){        printf( " 内在空间分配失败！ " );        exit( 1 );    }    newP -> data  =  x;         /*  给新分配的结点赋值  */      /*  向栈顶插入新结点  */     newP -> next  =   * hs;     * hs  =  newP;     return ;} /*  3.从链栈中删除一个元素并返回它（出栈）  */ elemType pop( struct  sNode *   * hs){     struct  sNode  * p;    elemType temp;     if ( * hs  ==  NULL){        printf( " 栈空无法删除！ " );        exit( 1 );    }     /*  暂存栈顶结点指针，并使栈顶指针指向下一个结点  */     p  =   * hs;     * hs  =  p -> next;     /*  暂存原栈顶元素以便返回，同时回收原栈顶结点  */     temp  =  p -> data;    free(p);     return  temp;         /*  返回原栈顶元素  */ } /*  4.读取栈顶元素  */ elemType peek( struct  sNode *   * hs){     /*  对于空栈则退出运行  */      if ( * hs  ==  NULL){        printf( " 栈空，无栈顶元素！ " );        exit( 1 );    }     return  ( * hs) -> data;         /*  返回栈顶结点的值  */ } /*  5.判断链栈是否为空，为空返回1，否则返回0  */ int  emptyStack( struct  sNode *   * hs){     if ( * hs  ==  NULL){         return   1 ;    } else {         return   0 ;    }} /*  6.清除链栈为空  */ void  clearStack( struct  sNode *   * hs){     struct  sNode  * cp,  * np;    cp  =   * hs;         /*  使cp指向栈顶结点  */      /*  从栈底依次删除每个结点  */      while (cp  !=  NULL){        np  =  cp -> next;        free(cp);        cp  =  np;    }     * hs  =  NULL;         /*  置链栈为空  */      return ;}