一起talk C栗子吧（第十七回：C語言實例--棧二）

各位看官們，大家好，從今天開始，我們講大型章回體科技小說 ：C栗子，也就是C語言實例。閑話休提， 言歸正轉(zhuǎn)。讓我們一起talk C栗子吧！

看官們，上一回中咱們說的是棧和特點和基本操作，最后通過順序存儲的方式實現(xiàn)了棧，這一回咱們繼續(xù) 說棧，不過咱們這一回說的是棧的鏈式存儲方式。

在代碼中通過雙向鏈表來實現(xiàn)棧的鏈式存儲。入棧操作沿著表頭到表尾的方向進行，出棧操作與其正好相 反（就把它當作雙向鏈表的一個使用實例吧）。棧的結(jié)點可以看作是鏈表中的結(jié)點，對棧的操作，可以看 作是在鏈表中進行插入或者刪除結(jié)點操作。只不過插入或者刪除時要遵循棧“先進后出"的特點。棧的類型 中增加了一個size成員，可以通過它方便地得出棧的長度。與棧的順序存儲方式相比，多了一個銷毀棧的 功能。因為棧中的空間都是動態(tài)分配得來的，每次入棧操作都會分配一塊內(nèi)存空間，與其相反，每次出棧 操作都會把內(nèi)存空間釋放掉。但是在實際程序中入棧和出棧并不是成對出現(xiàn)的，也就是說，如果使用完棧 后，沒有通過出棧操作來釋放動態(tài)空間，那么就會造成內(nèi)存泄漏。所以我增加了銷毀棧的功能，以方便在 程序的最后檢查棧中動態(tài)分配來的空間是否被釋放。

棧的鏈式存儲與棧的順序存儲相比，最大的優(yōu)點就是不需要事先知道棧的長度，只要內(nèi)存空間足夠大就能 存放足夠多的元素到棧中。不過，它也有缺點，那就是入棧和出棧操作要復(fù)雜，而且效率低。總之，在實 際的程序中如果事先知道棧的長度，可以使用棧的順序存儲，如果與事先不知道棧的長度，那么可以使用 棧的鏈式存儲，這樣比較靈活一些。

看官們，詳細的代碼如下，大家可以參考：

     1  /* **************************
     2   * Head file of Stack
     3   * *************************/
     4  #ifndef STACK_H
     5  #define STACK_H
     6  
     7  #include<stdio.h>
     8  #include<stdlib.h>
     9  
    10  #define SUCCESS 0
    11  #define FAILE 1
    12  
    13  typedef struct _StackElmt
    14  {
    15      int data;
    16      struct _StackElmt *pre;
    17      struct _StackElmt *next;
    18  }StackElmt; //把int當作棧中元素的類型，實際中可以使用其它的類型或者自己定義一個類型
    19  
    20  typedef struct _Stack{
    21      StackElmt *base; //棧底指針
    22      StackElmt *top;  //棧頂指針，它指向的區(qū)域存放StackElmt類型的值
    23      int size;        //方便統(tǒng)計棧的長度
    24  }Stack;
    25  
    26  //聲明函數(shù)原型，這里有入棧和出棧操的函數(shù)
    27  int StackInit(Stack *s);
    28  int StackPrint(Stack *s);
    29  int StackPush(Stack *s, int e);
    30  int StackPop(Stack *s, int *e);
    31  int StackDestroy(Stack *s);
    32  
    33  #endif /*STACK_H*/

     1  /* **************************
     2   * Soure file of Stack
     3   * *************************/
     4  
     5  #include"Ex015_Stack2.h"
     6  
     7  //實現(xiàn)List的函數(shù)，為了方便,放到了主函數(shù)所在的文件中，最好是單獨建立實現(xiàn)函數(shù)的源文件
     8  //
     9  //初始化中棧
    10  int StackInit(Stack *s)
    11  {
    12      if(NULL == s)
    13          return FAILE;
    14  
    15      s->top = s->base = NULL;
    16      s->size = 0;
    17  
    18      return SUCCESS;
    19  }
    20  
    21  //輸出棧中存放的元素
    22  int StackPrint(Stack *s)
    23  {
    24      int index = 0;
    25      StackElmt *t = NULL;
    26  
    27      if(NULL == s)
    28          return FAILE;
    29  
    30      if(s->size == 0)
    31      {
    32          printf("the Stack is empty,there is not any element \n");
    33          return FAILE;
    34      }
    35  
    36      t = s->base;
    37      while(NULL != t)
    38      {
    39          printf("%d  ",t->data);
    40          t = t->next;
    41      }
    42  
    43      printf("\n ");
    44  
    45      return SUCCESS;
    46  }
    47  
    48  //入棧函數(shù),top指向棧頂,每次push操作都會分配一個空間，top永遠指向該空間
    49  int StackPush(Stack *s, int e)
    50  {
    51      StackElmt *node = NULL;
    52  
    53      if(NULL == s)
    54          return FAILE;
    55  
    56      node = (StackElmt *)malloc( sizeof(StackElmt) );
    57  
    58      if(NULL != node)
    59      {
    60          if(NULL == s->base)
    61          {
    62              s->top = s->base = node;
    63              node->pre = NULL;
    64          }
    65          else
    66          {
    67              (s->top)->next = node;
    68              node->pre = s->top;
    69              s->top = node; //相當于順序存儲中的top++
    70          }
    71  
    72          node->data = e;
    73          node->next = NULL;
    74          (s->size)++;
    75  
    76          return SUCCESS;
    77      }
    78      else
    79          return FAILE;
    80  }
    81  
    82  //出棧函數(shù),先把top指向的元素出棧，然后釋放top指向的空間
    83  int StackPop(Stack *s, int *e)
    84  {
    85      StackElmt *t = NULL;
    86  
    87      if(NULL == s)
    88          return FAILE;
    89  
    90      if(s->size == 0)
    91      {
    92          printf("the Stack is empty \n");
    93          return FAILE;
    94      }
    95  
    96      *e = (s->top)->data ;
    97      t = (s->top)->pre;
    98      free(s->top);
    99      s->top = t; //相當于top--
   100  
   101      if(s->size == 1) //最后一個元素出棧時，base和top都為NULL
   102          s->base = s->top;
   103  
   104      (s->size)--;
   105  
   106      return SUCCESS;
   107  }
   108  
   109  //棧銷毀函數(shù)，因為有動態(tài)分配的空間，如果不執(zhí)行出棧操作，要把棧destroy
   110  int StackDestroy(Stack *s)
   111  {
   112      int t = 0;
   113      int result = 0;
   114  
   115      if(NULL == s)
   116          return FAILE;
   117  
   118      while(NULL != (s->base) )
   119          result = StackPop(s,&t);
   120  
   121      return result;
   122  }
   123  
   124  int main()
   125  {
   126      int i = 0;
   127      int e = 0;
   128      Stack stack ;
   129  
   130      if( SUCCESS == StackInit(&stack) )
   131          StackPrint(&stack);
   132  
   133      StackPush(&stack,7);
   134      StackPrint(&stack);
   135  
   136      StackPop(&stack,&e);
   137      printf("%d is poped \n",e);
   138  
   139      while(i++ < 5)
   140      {
   141          if( SUCCESS == StackPush(&stack,i) )
   142              printf("%d is pushed \n",i);
   143          else
   144              printf("push failed \n");
   145      }
   146  
   147      while(i-- > 0)
   148      {
   149          if( SUCCESS == StackPop(&stack,&e) )
   150              printf("%d is poped \n",e);
   151          else
   152              printf("pop failed \n");
   153      }
   154  
   155      if( SUCCESS == StackDestroy)
   156          printf("Stack destroy successfully  \n");
   157      else
   158          printf("Stack need not to destroy  \n");
   159  
   160  }

各位看官，關(guān)于棧的例子咱們就說到這里。欲知后面還有什么例子，且聽下回分解。